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

• Anonymous
  August 15, 2008
  PingBack from http://hubsfunnywallpaper.cn/?p=829

• Anonymous
  August 15, 2008
  The comment has been removed

• Anonymous
  August 15, 2008
  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?

• Anonymous
  August 15, 2008
  @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.

• Anonymous
  August 15, 2008
  @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.  

• Anonymous
  August 15, 2008
  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;

• Anonymous
  August 15, 2008
  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

• Anonymous
  August 15, 2008
  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.

• Anonymous
  August 16, 2008
  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()))

• Anonymous
  August 18, 2008
  @MichaelGG Thanks for the multi-tude of comments.  It's great to see so many different ways of approaching this problem.