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

Ответ 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).

Ответ 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, i. е. не запускаться до тех пор, пока аргументы в bind не будут связаны сами.

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

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