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

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>, как показано в kkm.

Однако вы также можете использовать гибкость выражений вычислений 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()