Thursday, July 30, 2009

F# Option orElse getOrElse functions

Consider the following function that takes a Sequence of (pairs) int * int.

let f s =
let o = Seq.tryFind (fun (_, x) -> x < 0) s
if Option.isSome o then
Option.get o |> fst
else
let p = Seq.tryFind (fun (_, x) -> x = 0) s
if Option.isSome p then Option.get p |> fst
else 10
Essentially I am looking for the first pair in the sequence where the second element in the pair satisfies a particular condition and then returning the corresponding first element or a default (i.e. 10) if no satisfactory pair was found.

That code is pretty ordinary. First of all, I would like to improve on the two calls to Seq.tryFind.
let f s =
let tf g = Seq.tryFind (fun (_,x) -> g x) s
let o = tf (fun x -> x < 0)
if Option.isSome o then
Option.get o |> fst
else
let p = tf ((=) 0)
if Option.isSome p then Option.get p |> fst
else 10
Now if the Scala Option orElse and getOrElse functions were available as well as the Haskell backquotes infix syntax then we could really make a difference.

orElse : 'T option -> 'T option -> 'T option
let orElse o p = if Option.isSome o then o else p

getOrElse : 'T option -> 'T -> 'T
let getOrElse o d = match o with | Some x -> x | _ -> d

// N.B. this is not valid F#

let f s =
let tf g = Seq.tryFind (fun (_,x) -> g x) s
tf (fun x -> x < 0) `orElse` tf ((=) 0) |> Option.map fst `getOrElse` 10
Neither orElse or getOrElse exist in the F# Option module. However the Core function defaultArg is essentially getOrElse.

Unfortunately F# doesn't have a way to use a (non-operator) function in infix form, like the backquotes in Haskell. However, we can define operators, which are essentially just infix functions.

let (|?) = orElse

let (|?|) = defaultArg
Now we can write a valid F# version.

let f s =
let tf g = Seq.tryFind (fun (_,x) -> g x) s
tf (fun x -> x < 0) |? tf ((=) 0) |> Option.map fst |?| 10

Laziness and Composability
Notice that in the original example, the second tryFind is only executed if the first one is unsuccessful because the then expression of an if statement is lazy, i.e. it is only evaluated if the condition is false.

However functions in F# are strict by default i.e. their arguments are evaluated prior to application. Consequently both tryFinds are evaluated, irrespective of their values, as they are arguments to orElse.

So here is an example where laziness is required to achieve reasonable composability. Implementing this gives the final code.

let orElse o (p:'a option Lazy) = if Option.isSome o then o else p.Force()

let (|?) = orElse

let (|?|) = defaultArg

let f s =
let tf g = Seq.tryFind (fun (_,x) -> g x) s
tf (fun x -> x < 0) |? lazy (tf ((=) 0)) |> Option.map fst |?| 10

1 comment:

Anonymous said...

Old stuff, I know, but I was intrigued by the topic. Introducing explicit laziness does not sound like a performance enhancement to me, and I also cannot find it more readable than the original code, although that is also somewhat weird. Anything wrong with the following code? (Looks like the spacing is incorrect because the blog filters out initial space.)

let f s =
let inline tf g = Seq.tryFind (fun (_, x) -> g x) s
match tf (( > ) 0) with
| Some (a, _) -> a
| None ->
match tf (( = ) 0) with
| Some (b, _) -> b
| None -> 10