lazy queue impl draft 1
unknown
fsharp
2 years ago
1.8 kB
6
Indexable
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
Editor is loading...