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

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 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 когда вы иметь расчет, который необходимо отложить - t hat: 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()