clojure like cond in F#

Question

I was recently taking a detour in clojure from F# and came across a macro called cond. Here is an example on the usage:

(cond
 (= target (nth arr mid)) mid  
 (< target (nth arr mid)) (search left (- mid 1))
 (> target (nth arr mid)) (search (+ mid 1) right)
 (= left right) -1)

This means the following in pseudo code:

if target == arr.[mid] then return mid
if target < arr.[mid] then return (call search(left, mid-1)) 
if target > arr.[mid] then return (call search(mid+1, right))
if left == right then return -1

This is just an example from a binary search in case you were wondering what is left right and mid, but not really important.

I have tried to find something similar in F# but I couldn't, so I decided to try and write it for myself. I ended up with something like this:

type condition = bool * int

let cond (conds: condition seq) = 
    conds |> Seq.pick(fun c -> if fst c then Some (snd c) else None)

cond [| ( (=) target arr.[mid], mid )
        ( (=) left right, -1 ) 
        ( (<) target arr.[mid], recSrch left (mid-1) )
        ( (>) target arr.[mid], recSrch (mid+1) right )
      |]

The problem here is that I want to use it in a recursive function, and because recSrch left (mid-1) are being evaluated right away so I end up in an infinite loop. I want it to be evaluated only when the condition holds. Plus the form is still not as clean as it is in Clojure.

Any ideas how could I improve this?

Answer 1

Here is a sketch using match which I think is pretty close to the clojure.

It defines Cond as a partial active pattern which takes the test function as an argument

let (|Cond|_|) f  arg = 
    if f arg then Some () else None;;

using it is pretty easy

match 1 with
|Cond ( (=) 5) _ -> printfn "unlikely"
| _ -> printfn "likely";;

Answer 2

You need a way of making the condition bodies evaluate lazily. Here's one way of doing it, by making the body a function to call as you iterate through the sequence of conditions:

type condition = bool * (unit -> int)

let cond (conds: condition seq) = 
    conds 
    |> Seq.pick(fun c -> 
        let pred, func = c
        if pred then Some (func()) else None)

cond [| ( (=) target arr.[mid], fun () -> mid )
        ( (=) left right, fun () -> -1 ) 
        ( (<) target arr.[mid], fun () -> recSrch left (mid-1) )
        ( (>) target arr.[mid], fun () -> recSrch (mid+1) right )
        |]

Note that it only makes sense to use something like this if your list of conditions is supposed to be dynamic.

For static conditions, you have pattern matching with when clauses. That gives you nice idiomatic syntax and generally checks your matches exhaustiveness at compile time, so it's well worth it.

let result = 
    match target with
    | _ when target = arr.[mid] -> mid
    | _ when left = right -> -1
    | _ when target < arr.[mid] -> recSrch left (mid-1)    
    | _ when target > arr.[mid] -> recSrch (mid+1) right
    | _ -> failwith "you need this case if the compiler can't figure if your matches are exhaustive"

Gets nicer if you wrap it as an active pattern.

Answer 3

In F#, there's a language construct for that kind of expression:

if target = arr.[mid] then mid
elif target < arr.[mid] then call (search(left, mid-1)) 
elif target > arr.[mid] then call (search(mid+1, right))
else -1

...or, in general: I view Clojure's cond macro as the equivalent of pattern matching or if/elif/else blocks. They're obviously not quite the same, because Clojure is interpreted and dynamically typed, whereas F# is compiled and statically typed.