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."

- I consider Node to be an implementation detail and ideally would like to make it a private nested class if possible
- The constructor still allows for invalid data combinations (but will throw)
- Ex: ImmutableStack None ImmutableStack.Empty()
- Can I get ImmutableStack.Empty to be a property instead of a function?
- 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

PingBack from http://hubsfunnywallpaper.cn/?p=829

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()

}

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?

@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.

@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.

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;

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

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.

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()))

@MichaelGG

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