ImmutableStack in F#


When learning a new language I find it very instructive to re-code certain structures from my well used libraries into the new language.  It gives a great basis for comparison in terms of ease of implementation, expressiveness of the language and sheer ease of implementation.  So on that note I set out today to build an ImmutableStack implementation in F#.  This is based off of my C# implementation in RantPack

Below is the initial implementation.  This is my first non "hello world" data structure in F#.  I found it surprisingly easy to implement and I’m really enjoying the language.  The biggest stumbling block was getting the type union correct and dealing with my compulsion to use "null" for end of stack instead of a value. 

After playing around with it a bit I’m left with the following questions/hangups.  Most of these will just fall into the category of "I’m starting out with a new language so I’m still hung up on the syntax in places." 

  1. I consider Node to be an implementation detail and ideally would like to make it a private nested class if possible
  2. The constructor still allows for invalid data combinations (but will throw)
    1. Ex: ImmutableStack None ImmutableStack.Empty()
  3. Can I get ImmutableStack.Empty to be a property instead of a function?
  4. In All(), that can’t be the most efficient way to build up a sequence. 
#light

type Node = 
    | Empty
    | Value of int * ImmutableStack

and ImmutableStack(?v:int, ?n:ImmutableStack) = 
    let data = match (v,n) with
                | (Some v, Some n ) -> Value (v,n)
                | (Some v, None) -> Value (v,ImmutableStack.Empty())
                | (None, None) -> Empty
                | _ -> failwith "invalid combination"
    static member Empty() = ImmutableStack()
    member x.IsEmpty() = 
        match data with
            | Empty -> true
            | _ -> false
    member x.Push(y) =
        match data with 
            | Empty -> ImmutableStack(y, x)
            | Value _ -> ImmutableStack(y, x)
    member x.Peek() =
        match data with
            | Empty -> failwith "ImmutableStack is empty"
            | Value (v,_) -> v
    member x.Pop() =
        match data with 
            | Empty -> failwith "ImmutableStack is empty"
            | Value (_,n) -> n
    member x.All() =
        match data with 
            | Empty -> Seq.empty
            | Value (v,n) -> Seq.append (Seq.singleton v) (n.All())
            
let rec printStack (s:ImmutableStack) =
    match s.IsEmpty() with
        | true -> printfn "Empty"
        | false -> 
            printfn "%d" (s.Peek())
            printStack (s.Pop())

let s1 = ImmutableStack.Empty()
let s2 = s1.Push(42).Push(56).Push(62)
let s3 = ImmutableStack 42
let s4 = s3.Pop()

printStack s1
printStack s2
printStack s3
printStack s4
Comments (10)

  1. ChrSmith says:

    Nice post. In response to your questions:

    1. You can hide the union case is through an explicit accessibility annotation (type private Node) or through the use of F# Signature files (.fsi). (The prefered way is through .fsi files.)

    2. I like the use of optional parameters in the constructor, although it allows for invalid combinations it doesn’t require you to write several explicit constructors.

    3. You can make ‘Empty’ a property by just dropping the parens, e.g. ‘static member Empty = new ImmutableStack()’.

    4. Perhaps you could try a Sequence Expression, I’m not sure if it is any better or worse than the code you had written, but it certainly looks cleaner IMHO.

    member x.All() =

           match data with

               | Empty -> Seq.empty

               | Value (v,n) ->

                   seq {

                       yield v

                       yield! n.All()

                   }

  2. Jason M says:

    Two questions, since I’m interested in F# as well:

    1) This is an implementation of a stack over ints. Do we have generics, or some other (better?) concept?

    2) what does "failwith" do? I suspect it throws a CLR exception, but what details are there?

  3. jaredpar says:

    @ChrSmith

    Thanks for the feedback.  For #3 I think that is the better solution.  From my understanding, my All() method is eager and will process all nodes immediately and build a full sequence.  yield should produce a delay evaluated sequence which is safe since this is an immutable collection.

  4. jaredpar says:

    @Jason

    1) I forgot to put that in the list of items I want to fix.  I decided to learn without generics and then complicate my life later on 🙂

    2) failwith throws a F# exception.  

  5. MichaelGG says:

    One approach is to embrace the discriminated union as the actual used type. This has the added benefit of automatically allowing pattern matching. This benefit is shown in my printStack function.

    #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

       member x.All =

           let until f = Seq.generate (fun () -> ref x) f (fun _ -> ())

           until (fun cur -> match (!cur) with Stack(v, s) -> cur := s; Some v | _ -> None)

    let rec printStack = function

                         | Empty -> printfn "Empty"

                         | Stack(v, Empty) -> printfn "%A" v

                         | Stack(v, s) -> printf "%A; " v;

  6. MichaelGG says:

    Lists also can relfect a stack, so you can just wrap the F# lists:

    type ‘a stack =

       | Stack of ‘a list

       member x.IsEmpty = x = Stack []

    module Stack =

       let empty = Stack []

       let pop = function Stack l -> Stack (List.tl l)

       let push x = function Stack l -> Stack (x :: l)

       let peek = function Stack l -> Stack (List.hd l)

       let all s = function Stack l -> seq l

    let s1 = Stack.empty

    let s2 = s1 |> Stack.push 12 |> Stack.push 11 |> Stack.push 19

  7. MichaelGG says:

    Oh, I should add, the All implementation I tried only creates a single seq instead of having to create new enumerators for each item. I tried a few ways here:

    http://www.atrevido.net/blog/2008/08/16/Reference+Cells+In+F+Sequences.aspx

    But I’m not really sold. Chris’s use of sequence expressions are probably the best way.

  8. MichaelGG says:

    Sorry for posting so much; I swear I’m not spamming. To address your original question (4) about All(), yes, it is eagerly evaluated. But the fix is really simple; just create a delayed sequence on the recursive call. That way it won’t be called until enumerated:

    | Value (v,n) -> Seq.append (Seq.singleton v) (Seq.delay(fun () -> n.All()))

  9. jaredpar says:

    @MichaelGG

    Thanks for the multi-tude of comments.  It’s great to see so many different ways of approaching this problem.