2 people like it.

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

More information

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