recursive merge multiple sorted sequences

gistfile1.fs

open FSharpx.Collections

let first = LazyList.ofSeq(seq { 0..3..30 } |> Seq.map (fun x -> (x, "first") ))
let second = LazyList.ofSeq(seq { 0..2..30 }  |> Seq.map (fun x -> (x, "second")))
let third = LazyList.ofSeq(seq { 0..30 }  |> Seq.map (fun x -> (x, "third")))


module LazyList =
    let takeWhileAsList pred (list:LazyList<'T>) =
        let rec inner l (r:List<'T>) =
                match l with
                | (LazyList.Cons(h,t)) -> 
                    if (pred h) then
                        inner t (h :: r)
                    else 
                        (List.rev r, l)
                | _ -> (List.rev r, l)
        inner list List.empty 

    let takeTail count (list:LazyList<'T>) =
        let rec inner l (r:List<'T>) c =
                match l with
                | (LazyList.Cons(h,t)) -> 
                    if (c < count) then
                        inner t (h :: r) (c + 1)
                    else 
                        (List.rev r, l)
                | _ -> (List.rev r, l)
        inner list List.empty 0

let contains x (list:List<'T>) = 
    let rec inner l =
        match l with
        | h :: t -> if (h = x) then true
                    else inner t
        | _ -> false
    inner list
    
let merge3 (a:LazyList<'a * string>) (b:LazyList<'a * string>) =
    let rec inner a' b' =
        LazyList.ofSeq( seq {
            match LazyList.takeTail 5 a' with
            | ([], _) -> yield! b'
            | (f, tail_a) -> 
                let (flastkey, _) = f.[f.Length - 1]
                
                let (s, tail_b) = LazyList.takeWhileAsList (fun (key, _) -> key <= flastkey) b'
                //filter s not to contain keys in f
                let fkeys = List.map (fun (k, _) -> k) f
                let s' = List.filter (fun (k, _) -> (contains k fkeys) = false) s
                
                yield! List.append f s' |> List.sortBy (fun (key, _) -> key)
                yield! inner tail_a tail_b 
            })

    inner a b
    
merge3 first <| merge3 second third
|> Seq.toList
|> (printfn "%A")