Реализация Haskell-MaybeMonad в F # - как мы можем получить это ленивый? - PullRequest
Новая
       37

Реализация Haskell-MaybeMonad в F # - как мы можем получить это ленивый?

5 голосов
/ 01 июля 2010

мы пытаемся построить образец Haskell-MaybeMonad из http://www.haskell.org/all_about_monads/html/maybemonad.html в F #.

Идея состоит в том, чтобы искать почтовый адрес в двух словарях. Если один из обоих поисков возвращает результат, мы смотрим на третий. 

let bindM x k =
    match x with
    | Some value -> k value
    | None   -> None

let returnM x = Some x

type MaybeBuilder() =
     member this.Bind(x, k) = bindM x k
     member this.Return(x)  = returnM x
     member this.ReturnFrom(x) = x
     member this.Delay(f)   = f()

let maybe = MaybeBuilder()

//Sample dictionaries
let fullNamesDb = 
    [("Bill Gates", "billg@microsoft.com")    
     ("Bill Clinton", "bill@hope.ar.us")
     ("Michael Jackson", "mj@wonderland.org")
     ("No Pref Guy", "guy@nopref.org")]
       |> Map.ofList

let nickNamesDb =
    [("billy", "billg@microsoft.com")
     ("slick willy", "bill@hope.ar.us")
     ("jacko", "mj@wonderland.org") ]
        |> Map.ofList

let prefsDb =
    [("billg@microsoft.com", "HTML")
     ("bill@hope.ar.us", "Plain")
     ("mj@wonderland.org", "HTML")]
        |> Map.ofList


let mplus m1 m2 = if m1 <> None then m1 else m2
let (+) = mplus

let lookUp name = maybe {
    let! combined = fullNamesDb.TryFind name + nickNamesDb.TryFind name
    return! prefsDb.TryFind combined
}

let billGatesPref = lookUp "Bill Gates" |> printfn "%A" // Some "HTML"
let billyPref = lookUp "billy" |> printfn "%A" // Some "HTML"
let billClintonPref = lookUp "Bill Clinton" |> printfn "%A" // Some "Plain"
let steffenPref = lookUp "Steffen" |> printfn "%A" // None
let noPref = lookUp "No Pref Guy" |> printfn "%A" // None

System.Console.ReadKey() |> ignore

Проблема в том, что мы выполняем второй поиск, даже если первый возвращает результат. Хорошая вещь о Haskell в том, что он оценивает ленивый. Сейчас мы ищем что-то похожее в F #. Мы попробовали следующее, но это выглядит уродливо и, кажется, нарушает идею инкапсуляции логики возможно в сборщике: 

let mplus m1 m2 = if m1 <> None then m1 else m2()
let (+) = mplus

let lookUp name = maybe {
    let! combined = fullNamesDb.TryFind name + fun _ -> nickNamesDb.TryFind name
    return! prefsDb.TryFind combined
}

Есть ли лучшее решение?

С уважением, forki

Ответы [ 2 ]

8 голосов
/ 01 июля 2010

Вы можете реализовать дополнительные методы Run / Combine в MaybeBuilder, поэтому результат будет следующим: 

let bindM x k =
match x with
| Some value -> k value
| None   -> None

let returnM x = Some x

type MaybeBuilder() =
    member this.Bind(x, k) = bindM x k
    member this.Return(x)  = returnM x
    member this.ReturnFrom(x) = x
    member this.Delay(f)   = f
    member this.Combine(a, b) = if Option.isSome a then a else b()
    member this.Run(f) = f()

let maybe = MaybeBuilder()

//Sample dictionaries (the same with original sample)
let fullNamesDb = ... 
let nickNamesDb = ...
let prefsDb = ....

let lookUp name = 
    let findName m = maybe {
        let! v = Map.tryFind name m
        return! prefsDb.TryFind v 
        }

    maybe {
        return! findName fullNamesDb
        return! findName nickNamesDb 
    }


let billGatesPref = lookUp "Bill Gates" |> printfn "%A" // Some "HTML"
let billyPref = lookUp "billy" |> printfn "%A" // Some "HTML"
let billClintonPref = lookUp "Bill Clinton" |> printfn "%A" // Some "Plain"
let steffenPref = lookUp "Steffen" |> printfn "%A" // None
let noPref = lookUp "No Pref Guy" |> printfn "%A" // None
1 голос
/ 01 июля 2010

Всегда есть Lazy, что фактически является тем, что у вас есть, но с другим синтаксисом: 

let mplus m1 (m2 : Lazy<'a option>) =
    match m1 with
    | Some _ as m -> m
    | None -> m2.Force()

let (+) = mplus

let lookUp name = maybe {
    let! combined = fullNamesDb.TryFind name + lazy (nickNamesDb.TryFind name)
    return! prefsDb.TryFind combined
}
...