Как реализовать задержку в построителе вычислений?

Question

Вот что у меня так далеко:

type Maybe<'a> = option<'a>

let succeed x = Some(x)

let fail = None

let bind rest p =
    match p with
        | None -> fail
        | Some r -> rest r

let rec whileLoop cond body =
    if cond() then
        match body() with
        | Some() ->
            whileLoop cond body
        | None ->
            fail
    else
        succeed()

let forLoop (xs : 'T seq) f =
    using (xs.GetEnumerator()) (fun it ->
            whileLoop
                (fun () -> it.MoveNext())
                (fun () -> it.Current |> f)
        )

whileLoop прекрасно работает для поддержки for циклы, но я не вижу, как получить, пока циклы поддерживаются. Частично проблема заключается в том, что перевод циклов while использует delay, который я не мог понять в этом случае. Очевидная реализация, приведенная ниже, вероятно, ошибочна, так как она не задерживает вычисления, а запускает их!

let delay f = f()

Не задерживает и мешает try...with а также try...finally,

Answer 1

На самом деле есть два разных способа реализации построителей продолжения в F#. Одним из них является представление отложенных вычислений с использованием монадического типа (если он поддерживает какой-либо способ представления отложенных вычислений, например Async<'T> или unit -> option<'T> введите, как показано на км.

Однако вы также можете использовать гибкость выражений вычислений F# и использовать другой тип в качестве возвращаемого значения Delay, Затем вам нужно изменить Combine операция соответственно, а также реализовать Run член, но все это работает довольно хорошо:

type OptionBuilder() = 
  member x.Bind(v, f) = Option.bind f v
  member x.Return(v) = Some v
  member x.Zero() = Some ()
  member x.Combine(v, f:unit -> _) = Option.bind f v
  member x.Delay(f : unit -> 'T) = f
  member x.Run(f) = f()
  member x.While(cond, f) =
    if cond() then x.Bind(f(), fun _ -> x.While(cond, f)) 
    else x.Zero()

let maybe = OptionBuilder()

Хитрость в том, что компилятор F# использует Delay когда у вас есть вычисления, которые нужно отложить, то есть: 1) обернуть все вычисления, 2) когда вы последовательно составляете вычисления, например, используя if внутри вычисления и 3) задержать тела while или же for,

В приведенном выше определении Delay член возвращается unit -> M<'a> вместо M<'a>, но это прекрасно, потому что Combine а также While принимать unit -> M<'a> как их второй аргумент. Кроме того, добавив Run который оценивает функцию, результат maybe { .. } блок (отложенная функция) оценивается, потому что весь блок передается Run:

// As usual, the type of 'res' is 'Option<int>'
let res = maybe { 
    // The whole body is passed to `Delay` and then to `Run`
    let! a = Some 3
    let b = ref 0
    while !b < 10 do 
      let! n = Some () // This body will be delayed & passed to While
      incr b
    if a = 3 then printfn "got 3"
    else printfn "got something else"
    // Code following `if` is delayed and passed to Combine
    return a }

Это способ определения компоновщика вычислений для типов без задержки, который, скорее всего, более эффективен, чем перенос типа внутри функции (как в решении kkm), и для него не требуется определять специальную версию типа с задержкой.

Обратите внимание, что эта проблема не возникает, например, в Haskell, потому что это ленивый язык, поэтому нет необходимости явно откладывать вычисления. Я думаю, что перевод F# довольно элегантен, поскольку позволяет работать с обоими типами, которые задерживаются (используя Delay это возвращает M<'a>) и типы, которые представляют собой только немедленный результат (используя Delay который возвращает функцию & Run).

Answer 2

Согласно монадическим тождествам, ваш delay всегда должен быть эквивалентен

let delay f = bind (return ()) f

поскольку

val bind : M<'T> -> ('T -> M<'R>) -> M<'R>
val return : 'T -> M<'T>

delay имеет подпись

val delay : (unit -> M<'R>) -> M<'R>

'T быть привязанным к типу unit, Обратите внимание, что ваш bind функция имеет свои аргументы, обратные от обычного порядка bind p rest, Технически это то же самое, но усложняет чтение кода.

Так как вы определяете монадический тип как type Maybe<'a> = option<'a>, нет никаких задержек вычислений, так как тип вообще не переносит вычислений, только значение. Таким образом, вы определение задержки как let delay f = f() теоретически правильно. Но это не подходит для цикла while: "тело" цикла будет вычислено до его "условия тестирования", на самом деле до bind связан. Чтобы избежать этого, вы переопределяете свою монаду с дополнительным уровнем задержки: вместо переноса значения вы переносите вычисление, которое берет единицу и вычисляет значение.

type Maybe<'a> = unit -> option<'a>

let return x = fun () -> Some(x)

let fail = fun() -> None

let bind p rest =
    match p() with
    | None -> fail
    | Some r -> rest r

Обратите внимание, что завернутые вычисления не выполняются, пока внутри bind функция, т.е. не запускается, пока после аргументов bind связаны сами.

С приведенным выше выражением, delay правильно упрощено до

let delay f = fun () -> f()