Recursive implementation of a zip function in F#

Question

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)?

Answer 1

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
}

Answer 2

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.