Implementing the Haskell-MaybeMonad in F# - how can we get this lazy?
we are trying to build the Haskell-MaybeMonad sample from http://www.haskell.org/all_about_monads/html/maybemonad.html in F#.
The idea is to search for a mailaddress in two dictionaries. If one of the both lookups returns a result we look into the third one.
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
The problem is that we perform the second lookup even if the first one returns a result. The nice thing about Haskell is here, that it evaluates lazy. Now we looking for something similar in F#. We tried the following but it looks ugly and seems to break the idea of encapsulating the maybe logic in the builder:
let mplus m1 m2 = if m1 <> None then m1 else m2()
let (+) = mplus
let lookUp name = maybe {
let! combined = fullNamesDb.TryFind name + fu开发者_StackOverflown _ -> nickNamesDb.TryFind name
return! prefsDb.TryFind combined
}
Is there a better solution?
Regards, forki
You can implement additional methods Run/Combine in MaybeBuilder so result shall be the following:
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
There's always Lazy
, which is effectively what you have here but with different syntax:
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
}
精彩评论