ImmutableStack in F#

send flowers » ImmutableStack in F#

send flowers » ImmutableStack in F# — Fri, 15 Aug 2008 15:08:43 GMT

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

re: ImmutableStack in F#

ChrSmith — Fri, 15 Aug 2008 18:43:53 GMT

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

}

re: ImmutableStack in F#

Jason M — Fri, 15 Aug 2008 19:41:17 GMT

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?

re: ImmutableStack in F#

Jared Parsons — Fri, 15 Aug 2008 20:15:49 GMT

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

re: ImmutableStack in F#

Jared Parsons — Fri, 15 Aug 2008 20:16:57 GMT

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

re: ImmutableStack in F#

MichaelGG — Sat, 16 Aug 2008 03:08:37 GMT

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;

re: ImmutableStack in F#

MichaelGG — Sat, 16 Aug 2008 03:35:40 GMT

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

re: ImmutableStack in F#

MichaelGG — Sat, 16 Aug 2008 08:43:32 GMT

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.

re: ImmutableStack in F#

MichaelGG — Sat, 16 Aug 2008 17:48:22 GMT

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

re: ImmutableStack in F#

Jared Parsons — Mon, 18 Aug 2008 19:24:45 GMT

@MichaelGG

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