Modified map2 (without truncation of lists) in F# - how to do it idiomatically?

Question

I'd like to rewrite such function into F#:

zipWith' :: (a -> b -> c) -> (a -> c) -> (b -> c) -> [a] -> [b] -> [c]
zipWith' _ _ h []     bs     = h `map` bs
zipWith' _ g _ as     []     = g `map` as
zipWith' f g h (a:as) (b:bs) = f a b:zipWith f g h as bs

My first attempt was:

let inline private map2' (xs : seq<'T>) (ys : seq<'U>) (f : 'T -> 'U -> 'S) (g : 'T -> 'S) (h : 'U -> 'S) =
    let xenum = xs.GetEnumerator()
    let yenum = ys.GetEnumerator()
    seq {
        let rec rest (zenum : IEnumerator<'A>) (i : 'A -> 'S) =
            seq {
                yield i(zenum.Current)
                if zenum.MoveNext() then yield! (rest zenum i) else zenum.Dispose()
            }
        let rec merge () =
            seq {
                if xenum.MoveNext()
                then
                    if yenum.MoveNext()
                    then yield (f xenum.Current yenum.Current); yield! (merge ())
                    else yenum.Dispose(); yield! (rest xenum g)
                else
                    xenum.Dispose()
                    if yenum.MoveNext()
                    then yield! (rest yenum h)
                    else yenum.Dispose()
            }
        yield! (merge ())
    }

However it can hardly be considered idiomatic. I heard about LazyList but I cannot find it anywhere.

Answer 1

LazyList is in the F# PowerPack. You probably need it to write this more elegantly. Given how good your first-try code looks, I expect you'll have no trouble authoring the LazyList version.

Answer 2

As Brian mentioned, F# provides a usual Haskell-style lazy list in the PowerPack, so you can use that. Unfortunately, there is no good way to express this kind of thing using standard F# sequence expressions, because they can only express computations that read data from a single sequence using for (in your case, you'd need to read from multiple sequences).

However, it is possible to write a computation (similar to seq { .. }) for working with IEnumerator<T> - it is an imperative computation that modifies the enumerator behind the scenes, but it can be used for encoding patterns when seq isn't good enough. I'm planing to blog about it, but in the meantime, you can get it here (the code also includes the solution to your problem).

Then you can write this:

// Zip using specified functions for sequences 
let zipWithFun f g h (a:seq<_>) (b:seq<_>) = 
  // Local helper function that works with iterators (xs and ys)
  let rec zipWithFunE xs ys = iter {
    // Try to get first element from both iterators (mutates the iterators!)
    let! x = xs
    let! y = ys
    match x, y with 
    | Some(x), Some(y) -> 
        // If both produced value, then combine values using 'f' & continue
        yield f (x, y)
        yield! zipWithFunE xs ys 
    // If only one produced value, yield the value and then return the
    // remaining values projected using one of the functions
    | Some(rest), _ ->
        yield g rest
        yield! ys |> Enumerator.map g
    | _, Some(rest) ->
        yield g rest
        yield! ys |> Enumerator.map g
    | _ -> () }

  // Construct a 'seq' value from a function that processes enumerators
  Enumerator.toSeq (fun () -> 
    zipE (a.GetEnumerator()) (b.GetEnumerator()))

The core part of the code pretty much copies the structure of the original Haskell solution, which makes this approach very attractive, but you can still use sequences directly, without copying data to some other data structure.

Answer 3

I suggest :

let forever xs =
    Seq.append (Seq.map Some xs) (Seq.initInfinite (fun _ -> None))

let zipWith f g h xs ys =
    Seq.zip (forever xs) (forever ys)
    |> Seq.takeWhile (fun (x, y) -> Option.isSome x || Option.isSome y)
    |> Seq.map ( function
        | (Some x, Some y) -> f x y
        | (Some x, None  ) -> g x
        | (None  , Some y) -> h y
        | _ -> failwith "quite unexpected !" )