[Giagnocavo]Michael::Write() - Reference cells in F# sequences

Saturday, August 16, 2008

Reference cells in F# sequences

I saw this stack implementation (http://blogs.msdn.com/jaredpar/archive/2008/08/15/immutablestack-in-f.aspx) and wanted to see how I'd approach it:

#light
open System

type 'a ImmutableStack = 
   | Empty
   | Stack of 'a * 'a ImmutableStack
   member x.Peek() = match x with | Stack (v, _) -> Some v | _ -> None
   member x.Pop() = match x with | Stack (_, s) -> s | _ -> failwith "empty stack"
   member x.Push a = Stack(a, x)
   member x.IsEmpty = x = Empty 

(Well, I'd probably just use a list in most cases.) But interestingly, he has an All function, which returns a sequence of the entire stack. Chris suggested using sequence expressions and then recursively calling the function:

member x.All =
    match data with 
        | Empty -> Seq.empty
        | Value (v,n) -> 
            seq {
                yield v
                yield! n.All }

This is pretty nice as far as syntax goes. For some reason, I wanted to see how it'd look without the recursion (which needs to generate a new enumerator, unless the compiler is doing some wicked awesome stuff, which wouldn't surprise me). Here are some of the things I came up with:

member x.All1 = 
   let until f = Seq.generate (fun () -> ref x) f (fun _ -> ())
   until (fun cur -> match (!cur) with 
                        | Stack(v, s) -> cur := s
                                         Some v 
                        | _ -> None) 

Seq.generate continues calling the function until None is returned, so this provides the loop termination. Another similar approach:

member x.All2 = 
      let until f = Seq.generate (fun () -> ref x) f (fun _ -> ())
      until (fun cur -> try (!cur).Peek()
                        finally if not (!cur).IsEmpty then cur := (!cur).Pop())

Since Peek already returns 'a option, we can use it directly. The problem is that we need to update cur to cur.Pop and then return a value. The try/finally works, but the whole deal still doesn't seem very elegant. Sequence expressions allow us to yield:
 
member x.All3 =
      let cur = ref x
      { while not (!cur).IsEmpty do
          yield (!cur).Peek()
          do cur := (!cur).Pop() }
      |> Seq.choose(fun x -> x)

I dislike this one. Because we're not doing the pattern match ourselves, we end up yielding 'a option. But None is never valid because we guard on IsEmpty. This makes us stick a Seq.choose on with an identity function to strip off the Some. [Side note, is there no built-in identity function?] Bringing the match into the seq fixes the issue, but the code is pretty long:

member x.All4 =
      let cur = ref x
      { while not (!cur).IsEmpty do
          match (!cur).Peek() with 
                      | None -> do ()
                      | Some v -> do cur := (!cur).Pop() 
                                  yield v }

I think what bothers me the most here is that the while and match are redundant. The None case will never be matches because we guard on IsEmpty. Moving that into a separate function gives:

member x.All5 =
      let v = function Stack(vl, _) -> vl | _ -> failwith "dont call on empty"
      let cur = ref x
      { while (!cur) <> Empty do
          yield v (!cur)
          do cur := (!cur).Pop() }

I prefer All5 to All4, but still think All1 or All2 are nicer. (Chris's original is best as far as I can tell.) How else can this be done?

Edit: I lost sight of one of the principals of functional programming: Composition. Here's a simple update to All5 that, IMHO, vastly improves it:

member x.All6 =
      let cur = ref x
      let toVal = function Stack(v, _) -> v | _ -> failwith "dont call on empty"
      let next () = try toVal (!cur) finally cur := (!cur).Pop()
      { while (!cur) <> Empty do yield next () } 

Every line builds up and you don't have to keep its details "active" in your mind. This makes the sequence expression (which is the driver of the algorithm) easy to verify. And again, to clarify, in a real system I'd probably use what Chris suggested since it's the nicest syntax. The other versions are only seeing what it looks like if we toss recursion and use a reference cell.

Code | F#

Saturday, August 16, 2008 4:09:49 AM UTC

Comments [0] | Trackback

Name
E-mail
Home page

	Remember Me
Comment (HTML not allowed)
Enter the code shown (prevents robots):
Live Comment Preview