My first F#, Binary Chop

Yesterday, I really felt like trying out F#. To get some inspiration, I visited PragProgs katas, and chose Kata Two -- Karate Chop. Or, actually, I just implemented a "functional" solution. I tried to make an imperative pointer-based solution (which I might post later, when I have resolved a strange bug). Anyway, I had never coded F# before, so there might be a few places where I could have e.g. chosen a library function instead of implementing it myself. If you have any suggestions or general comments, please post them!

By the way, is there any way to program in literate F#?

#light

First, a few helper functions for triples.

let fst3 (a,b,c) = a
let snd3 (a,b,c) = b
let trd3 (a,b,c) = c

Define the middle index, for simplicity return 0 if list is empty.

let middleIndex xs = if List.is_empty xs then 0 else (List.length xs - 1)/2

Define a function that returns the middle element of a list, and two functions that returns the first/last remaining halfs. Note that there might not be a middle element, so we use the option type.

let firstHalf xs = Seq.take (middleIndex xs) xs

let middleElem xs = 
 match (xs) with
    | [] -> None
    | xs -> Some (xs.Item (middleIndex xs))

let lastHalf xs = 
 match xs with 
    | [] -> Seq.empty
    | xs2 -> Seq.skip (middleIndex xs + 1) xs2

Let us group the functions in a convenient triple.

let splitInHalf xs = (firstHalf xs, middleElem xs, lastHalf xs)

Now, define a recursive function that 1) splits the list in three parts 2) reuse some definitions 3) return "None" if middle is empty 4) otherwise we can test the middle for equality, if equal then return the current index 5) if not equal, choose appropriate half and recurse.

let rec exists x xs i = 
 let triple = splitInHalf xs in                  //1 
 let maybeMiddle = snd3 triple                   //2
 let firstPart = Seq.to_list (fst3 triple)
 let lastPart = Seq.to_list (trd3 triple)
 if Option.is_none maybeMiddle then None         //3
 else let middle = Option.get maybeMiddle in     //4
      if x.Equals middle then Some(i)            //5
      elif middle > x then exists x firstPart (middleIndex firstPart)
                    else exists x lastPart ((i+1) + middleIndex lastPart)

This is the function a user would call.

let public ex x xs = exists x xs (middleIndex xs)

Some tests, just to check, plus a helper function for equality over options.

//Tests

let eq x y = if Option.is_none x then Option.is_none y else x.Equals y

let res = [
 ex 3 [];
 ex 3 [1];
 ex 1 [1];
 
 ex 1 [1;3;5];
 ex 3 [1;3;5];
 ex 5 [1;3;5];
 ex 0 [1;3;5];
 ex 2 [1;3;5];
 ex 4 [1;3;5];
 ex 6 [1;3;5];
 
 ex 1 [1;3;5;7];
 ex 3 [1;3;5;7];
 ex 5 [1;3;5;7];
 ex 7 [1;3;5;7];
 ex 0 [1;3;5;7];
 ex 2 [1;3;5;7];
 ex 4 [1;3;5;7];
 ex 6 [1;3;5;7];
 ex 8 [1;3;5;7];
 
 ]

let answers = [None; None; Some 0;
 Some 0; Some 1; Some 2; None; None; None; None;
 Some 0; Some 1; Some 2; Some 3; None; None; None; None; None
 ]
 
let asserts = Seq.for_all2 eq res answers
asserts

Now, I must say that I had a real good time developing this! Ok, some minor things didn't went as smoothly as I'd hope for, but it was actually the first time that I tried F#. I've never had such a good experience with a language the first day of use.

I will definitly be posting more F# posts in the future!

Cheers