There is something wrong with your code: it doesn't return a sequence of Tuples, but rather a sequence of a sequence of tuples. Compare the output of:
zipRec [ 1; 2; 3; 4 ] [| "one"; "two" |]
|> List.ofSeq
|> printfn "%A"
// Output: [seq [(1, "one"); (2, "two")]]
with this
Seq.zip [ 1; 2; 3; 4 ] [| "one"; "two" |]
|> List.ofSeq
|> printfn "%A"
// Output: [(1, "one"); (2, "two")]
Playing around with your code a bit, I made it more "functional" (read: used pattern matching) to make the intent clearer. I also realized that the bug was writing yield r
instead of yield! r
. This is what I ended up with:
let zipRec fst snd =
let rec loop r fst snd =
seq {
match Seq.tryHead fst, Seq.tryHead snd with
| Some(x), Some(y) ->
let r = Seq.append r [(x, y)]
yield! loop r (Seq.tail fst) (Seq.tail snd)
|_ -> yield! r
}
loop Seq.empty fst snd
I am still not quite sure recursion is the good answer for this, but it seems to work. Out of curiosity, I ran both zipRec
and Seq.zip
on two large sequences:
# time "on"
let numbersSeq = seq { 0..1000 }
let reverseSeq = seq { 1000..-1..0 }
let terrorTest2 = Seq.zip numbersSeq reverseSeq |> Seq.take 10 |> printfn "%A"
// seq [(0, 1000); (1, 999); (2, 998); (3, 997); ...]
// Real: 00:00:00.003, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
let terrorTest1 = zipRec numbersSeq reverseSeq |> Seq.take 10 |> printfn "%A"
// seq [(0, 1000); (1, 999); (2, 998); (3, 997); ...]
// Real: 00:00:18.102, CPU: 00:00:17.656, GC gen0: 19, gen1: 2, gen2: 0
The good news that I didn't run into a stack overflow. The bad news is that it is horribly inefficient.
Increasing the upper limit in the tests to 10,000 rather than 1,000, in addition to using it with F# lists rather than seqs, caused a stack overflow.
Edit:
Looking through my own copy of the book, I looked at the C# implementation (code is available on GitHub btw) and tried to imitate it using a recursive call in F#. I came up with this, which seems to be efficient and fast enough (my terrorTest didnt take 18 seconds).
let rec zipRec fst snd =
seq{
match Seq.tryHead fst, Seq.tryHead snd with
| Some(x), Some(y) ->
yield (x, y)
yield! zipRec (Seq.tail fst) (Seq.tail snd)
| _ -> () // this took me too long to figure out. Obvious in hindsight
}
With sequences 10,000 elements long, these are the results
let terrorTest2 = Seq.zip numbersSeq reverseSeq |> Seq.take 10 |> printfn "%A"
// seq [(0, 10000); (1, 9999); (2, 9998); (3, 9997); ...]
// Real: 00:00:00.001, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
let terrorTest1 = zipRec numbersSeq reverseSeq |> Seq.take 10 |> printfn "%A"
// seq [(0, 10000); (1, 9999); (2, 9998); (3, 9997); ...]
// Real: 00:00:00.001, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
Thanks for the question. I actually learned a lot doing it.
Reflecting on it, put it this way: you're doing tail recursion by performing a recursion call on the tail of the provided sequences. No accumulator needed.
Edit 2:
Apparently my zipRec
is still not performant for large collections. Check out the comments.
Tomas Petricek (the author of Real World Functional Programming), answered me on twitter
Dealing with seqs is not very nice - using GetEnumerator as in the answer from Sehnsucht is the way to go (even if it means loops)
So there you go .. You should perhaps change the accepted answer.