# Recursive implementation of a zip function in F#

I'm learning F# from Tomas Petricek's "Real-World Functional Programming" book. As suggested at one point in the book, I started implementing a zip function using a recursive sequence expression. I'm not very happy with my implementation and I would like to know how F# devs would refactor my implementation. I know that the original zip function is implemented using map2 but I want to stick with the recursive sequence expression. Any suggestion would expand my horizon.

// Create the zip function
let zipRec first second =
let rec loop r xs ys = seq {
if Seq.isEmpty xs || Seq.isEmpty ys then yield r
else
let r = Seq.append r (Seq.singleton((Seq.item 0 xs, Seq.item 0 ys)))
yield! loop r (Seq.tail xs) (Seq.tail ys) }
loop Seq.empty first second

// test
zipRec [1;2;3;4] [|"one"; "two" |] |> List.ofSeq |> printfn "%A"


What I don't like about my code:

• It feels too imperative
• I'm using a lot of the functions in the Seq module. Can this be written more F# idiomatic (short, concise, using more functional programming style)?
• Does the code perform fast enough for real world scenarios? (I've used tail recursion)
• Is the code robust enough (in regards to exceptions)?
• I think there are less then 200 questions tagged F# on codereview. Just wanted to say that maybe it would've been better to leave this on SO, as not many people monitor codereview. As opposed to other higher traffic languages like Java or C#. – s952163 Jul 7 '16 at 14:18
• @s952163 if everyone had your attitude and posted all their Qs on SO, then CR would never have a thriving F# community. – RubberDuck Jul 7 '16 at 23:49
• @RubberDuck it's actually not such a strong opinion. And I agree that it makes sense to have similar type questions on CR. It would be nice to have CR questions also appear on SO. I just saw this question deleted from SO, and I would never have come across it otherwise. For example this (somewhat) similar question already has an answer... If for example the person who suggested the move to CR would have also answered it.... – s952163 Jul 8 '16 at 0:33
• @RubberDuck or like this question – s952163 Jul 8 '16 at 0:44

Based upon my comment on that answer I've toyed a little to make a recursive sequence expression with roughly the same performance (on my computer at least) as Seq.zip

let zipRec (s1: _ seq) (s2: _ seq) =
use e1 = s1.GetEnumerator ()
use e2 = s2.GetEnumerator ()

let rec loop hasMoved1 hasMoved2 = seq {
if hasMoved1 && hasMoved2 then
yield e1.Current, e2.Current
yield! loop (e1.MoveNext ()) (e2.MoveNext ())
}

loop (e1.MoveNext ()) (e2.MoveNext ())


without the recursive requirement it would be simpler this way

let zipRec (s1: _ seq) (s2: _ seq) = seq {
use e1 = s1.GetEnumerator ()
use e2 = s2.GetEnumerator ()

while e1.MoveNext () && e2.MoveNext () do
yield e1.Current, e2.Current
}


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 {
| 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{
| 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.

• Well… if I have payed attention on the outputted type information of my zipRec function, I could have probably spot the wrong return type: val zipRec : first:seq<'a> -> second:seq<'b> -> seq<seq<'a * 'b>>. I also liked that you introduced pattern matching instead of the ‘if’ expression. Coming from an OOP background is not always easy to figure it out where and how to change the imperative style to a more functional programming style. At least this is how I feel right now. – Homorozeanu George Jul 8 '16 at 20:41
• The performance of my version is indeed a mess, although there is one thing that I don’t understand right now. When I look at the terrorTest1 expression, I expect the zipRec function to run only 10 time. Sequences should be lazy and evaluated only as needed, this also allows for infinite sequences. I have the feeling that in my implementation the zipRec function runs first for all 1000 elements and then takes 10 elements from the result. Why this behavior? – Homorozeanu George Jul 8 '16 at 20:45
• Many thanks for your answer. I’ve learned a lot from your steps/improvements. – Homorozeanu George Jul 8 '16 at 20:47
• The "terror" tests are a bit flawed due to the lazyness of seq ; it'll only take as many elements as request, so 10 in your example. And even with taking more elements ; the printer only show (and thus evaluate) the first (3) elements (and then shows ...) ; That's easily verifiable take more elements than what really is in the seq (1000000) it won't crash because it'll only evaluate what is really needed. You should use something that traverse the whole seq to measure like Seq.length – Sehnsucht Jul 9 '16 at 22:58
• @Sehnsucht you're right. I had to add the take 10 part so the first function definition would actually give a result within a certain time, and any more that that was taking a bit of a toll on the computer. The second function works fine tho even when you use List.ofSeq or something. – asibahi Jul 10 '16 at 7:10