2 people like it.
Like the snippet!

Implementation of Immutable Stack

Immutable stack can be implemented via Discriminated Union Type with methods like Push and Pop. The following snippet is a simple version of it.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39:

  // Define an immutable stack
  type ImmutableStack<'T> =
    | Empty 
    | Stack of 'T * ImmutableStack<'T>

    member s.Push x = Stack(x, s)

    member s.Pop() = 
      match s with
      | Empty -> failwith "Underflow"
      | Stack(t,_) -> t

    member s.Top() = 
      match s with
      | Empty -> failwith "Contain no elements"
      | Stack(_,st) -> st

    member s.IEmpty = 
      match s with
      | Empty -> true
      | _ -> false

    member s.All() = 
      let rec loop acc = function
      | Empty -> acc
      | Stack(t,st) -> loop (t::acc) st
      loop [] s

  // Return an ImmutableStack<'a> object
  let s = ImmutableStack.Empty
  
  // Return Stack (5,Empty)
  let s' = s.Push 5

  // Return Stack (4,Stack (5,Empty))
  let s'' = s'.Push 4

  // Print out a list [5; 4]
  let printAll = s''.All()

union case ImmutableStack.Empty: ImmutableStack<'T>

union case ImmutableStack.Stack: 'T * ImmutableStack<'T> -> ImmutableStack<'T>

type ImmutableStack<'T> =
  | Empty
  | Stack of 'T * ImmutableStack<'T>
  member All : unit -> 'T list
  member Pop : unit -> 'T
  member Push : x:'T -> ImmutableStack<'T>
  member Top : unit -> ImmutableStack<'T>
  member IEmpty : bool

Full name: Script.ImmutableStack<_>

val s : ImmutableStack<'T>

member ImmutableStack.Push : x:'T -> ImmutableStack<'T>

Full name: Script.ImmutableStack`1.Push

val x : 'T

member ImmutableStack.Pop : unit -> 'T

Full name: Script.ImmutableStack`1.Pop

val failwith : message:string -> 'T

Full name: Microsoft.FSharp.Core.Operators.failwith

val t : 'T

member ImmutableStack.Top : unit -> ImmutableStack<'T>

Full name: Script.ImmutableStack`1.Top

val st : ImmutableStack<'T>

member ImmutableStack.IEmpty : bool

Full name: Script.ImmutableStack`1.IEmpty

member ImmutableStack.All : unit -> 'T list

Full name: Script.ImmutableStack`1.All

val loop : ('a list -> ImmutableStack<'a> -> 'a list)

val acc : 'a list

val t : 'a

val st : ImmutableStack<'a>

val s : ImmutableStack<'a>

Full name: Script.s

val s' : ImmutableStack<int>

Full name: Script.s'

val s'' : ImmutableStack<int>

Full name: Script.s''

member ImmutableStack.Push : x:'T -> ImmutableStack<'T>

val printAll : int list

Full name: Script.printAll

member ImmutableStack.All : unit -> 'T list

Previous Version Raw view Test code New version

More information

Link:	http://fssnip.net/er
Posted:	12 years ago
Author:	Joel Huang
Tags:	stack , immutability , discriminated union type