7 people like it.
Like the snippet!

Yet another immutable queue implementation

 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: 
40:

let (|Created|_|) (v : Lazy<'T>) =
    if v.IsValueCreated then Some v.Value else None

type Queue<'T> private (front : 'T list, back : 'T list) =
    let list = lazy (front @ List.rev back)

    static let Q(xs, ys) = Queue<'T>(xs,ys)

    static member OfList xs = Q(xs,[])
    static member Empty = Q([],[])

    member __.IsEmpty = front.IsEmpty && back.IsEmpty
    member __.Length = front.Length + back.Length

    member __.Enqueue x =
        match list with
        | Created value -> Q(value, [x])
        | _ -> Q(front, x :: back)

    member __.Dequeue() =
        match list with
        | Created [] -> failwith "Queue underflow."
        | Created (x :: xs) -> x, Q(xs,[])
        | _ ->
            match front, back with
            | [], [] -> failwith "Queue underflow."
            | [], _ -> Q(list.Value, []).Dequeue()
            | x::xs, ys -> x, Q(xs,ys)

    member __.ToList() = list.Value
    override __.ToString () = list.Value.ToString()

module Queue =
    let inline (|Q|) (q : Queue<_>) = q
    
    let empty<'T> = Queue<'T>.Empty
    let ofList ts = Queue<_>.OfList ts
    let toList (Q q) = q.ToList()
    let enqueue (Q q) x = q.Enqueue x
    let dequeue (Q q) = q.Dequeue()

val v : Lazy<'T>

Multiple items
active recognizer Lazy: Lazy<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.( |Lazy| )

--------------------
type Lazy<'T> = System.Lazy<'T>

Full name: Microsoft.FSharp.Control.Lazy<_>

property System.Lazy.IsValueCreated: bool

union case Option.Some: Value: 'T -> Option<'T>

property System.Lazy.Value: 'T

union case Option.None: Option<'T>

Multiple items
type Queue<'T> =
  private new : front:'T list * back:'T list -> Queue<'T>
  member Dequeue : unit -> 'T * Queue<'T>
  member Enqueue : x:'T -> Queue<'T>
  member ToList : unit -> 'T list
  override ToString : unit -> string
  member IsEmpty : bool
  member Length : int
  static member OfList : xs:'T list -> Queue<'T>
  static member Empty : Queue<'T>

Full name: Script.Queue<_>

--------------------
private new : front:'T list * back:'T list -> Queue<'T>

val front : 'T list

type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>

val back : 'T list

Multiple items
val list : Lazy<'T list>

--------------------
type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>

Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
  interface IEnumerable
  interface IEnumerable<'T>
  member Head : 'T
  member IsEmpty : bool
  member Item : index:int -> 'T with get
  member Length : int
  member Tail : 'T list
  static member Cons : head:'T * tail:'T list -> 'T list
  static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>

val rev : list:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.rev

val Q : ('T list * 'T list -> Queue<'T>)

val xs : 'T list

val ys : 'T list

static member Queue.OfList : xs:'T list -> Queue<'T>

Full name: Script.Queue`1.OfList

static member Queue.Empty : Queue<'T>

Full name: Script.Queue`1.Empty

member Queue.IsEmpty : bool

Full name: Script.Queue`1.IsEmpty

property List.IsEmpty: bool

val __ : Queue<'T>

member Queue.Length : int

Full name: Script.Queue`1.Length

property List.Length: int

member Queue.Enqueue : x:'T -> Queue<'T>

Full name: Script.Queue`1.Enqueue

val x : 'T

active recognizer Created: Lazy<'T> -> 'T option

Full name: Script.( |Created|_| )

val value : 'T list

member Queue.Dequeue : unit -> 'T * Queue<'T>

Full name: Script.Queue`1.Dequeue

val failwith : message:string -> 'T

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

property System.Lazy.Value: 'T list

member Queue.ToList : unit -> 'T list

Full name: Script.Queue`1.ToList

override Queue.ToString : unit -> string

Full name: Script.Queue`1.ToString

System.Object.ToString() : string

Multiple items
module Queue

from Script

--------------------
type Queue<'T> =
  private new : front:'T list * back:'T list -> Queue<'T>
  member Dequeue : unit -> 'T * Queue<'T>
  member Enqueue : x:'T -> Queue<'T>
  member ToList : unit -> 'T list
  override ToString : unit -> string
  member IsEmpty : bool
  member Length : int
  static member OfList : xs:'T list -> Queue<'T>
  static member Empty : Queue<'T>

Full name: Script.Queue<_>

active pattern result Q: unit

val q : Queue<'a>

type Queue<'T> =
  private new : front:'T list * back:'T list -> Queue<'T>
  member Dequeue : unit -> 'T * Queue<'T>
  member Enqueue : x:'T -> Queue<'T>
  member ToList : unit -> 'T list
  override ToString : unit -> string
  member IsEmpty : bool
  member Length : int
  static member OfList : xs:'T list -> Queue<'T>
  static member Empty : Queue<'T>

Full name: Script.Queue<_>

val empty<'T> : Queue<'T>

Full name: Script.Queue.empty

val ofList : ts:'a list -> Queue<'a>

Full name: Script.Queue.ofList

val ts : 'a list

val toList : Queue<'a> -> 'a list

Full name: Script.Queue.toList

active recognizer Q: Queue<'a> -> Queue<'a>

Full name: Script.Queue.( |Q| )

val enqueue : Queue<'a> -> x:'a -> Queue<'a>

Full name: Script.Queue.enqueue

val x : 'a

val dequeue : Queue<'a> -> 'a * Queue<'a>

Full name: Script.Queue.dequeue

Raw view Test code New version

More information

Link:	http://fssnip.net/f7
Posted:	12 years ago
Author:	Eirik Tsarpalis
Tags:	immutable queues