lazy queue impl draft 1

mail@pastecode.io avatar
unknown
fsharp
a year ago
1.8 kB
4
Indexable
Never
module FunctionDatastructures.LazyQueue

// TODO look at LazyList from fsharp.collection

type LazyQueue<'a> = (seq<'a> * int * 'a list)

//helper func start    
let tryAppendListHeadSeq (l: 'a list) (s: seq<'a>): seq<'a> =
    match List.tryHead l with
    | Some head -> Seq.append [head] s 
    | None -> s

let tryListTail (l: 'a list): 'a list = 
    match l.Length with
    | 0 -> []
    | _ -> l.Tail

let rec rot (front: seq<'a>) (frontSize: int) (back: 'a list) (accumulation: seq<'a>): seq<'a> = 
    printfn("in rot")
    match frontSize with
    | 0 -> accumulation
    | _ -> Seq.append [Seq.head front] (Seq.delay(fun()-> 
        rot (Seq.tail front) (frontSize-1) (tryListTail back) (tryAppendListHeadSeq back accumulation))
    )

let makeq (front: seq<'a>) (frontSize: int) (back: 'a list): LazyQueue<'a> =
    if (frontSize >= back.Length) then (front, frontSize, back)
    else ((rot front frontSize back Seq.empty<'a>), frontSize+back.Length, List.empty<'a>)

//helper func end

let empty (): LazyQueue<'a> = 
    (Seq.empty, 0, [])

//should always be empty if length of seq is 0
let isEmpty (queue: LazyQueue<'a>): bool = 
    match queue with
    | _,0,_ -> true
    | _ -> false

// use homemade function to construct lazyqueue and balance
let cons (a: 'a) (queue: LazyQueue<'a>): LazyQueue<'a> = 
    match queue with
    | front, count, back -> makeq front count (a::back)

let head (queue: LazyQueue<'a>): 'a = 
    let front, _, _ = queue
    match isEmpty queue with
    | true -> invalidOp "queue is empty"
    | false -> Seq.head front

let tail (queue: LazyQueue<'a>): LazyQueue<'a> = 
    let front, sizeFront, back = queue
    match isEmpty queue with
    | true -> invalidOp "queue is empty"
    | false -> makeq (Seq.tail front) sizeFront back