7 people like it.

Yet another immutable queue implementation

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:11 years ago
Author:Eirik Tsarpalis
Tags: immutable queues