CODEWITHSUNDEEP
listhaskellziplist-comprehensionwinghci
T-Bird
T-Bird

Reputation: 187

Rewriting zipWith function using list comprehension

I've rewritten the zipWith function using recursion, and now I am trying to rewrite it using list comprehension. I have run into quite a few binding errors and I know that my second line is incorrect. This is the function I have that works like zipWith using recursion:

zipW :: (a -> b -> c) -> [a] -> [b] -> [c] 
zipW _ [] _ = []  
zipW _ _ [] = []  
zipW f (x:xs) (y:ys) = f x y : zipW f xs ys

And this is my attempt to rewrite it as list comprehension:

zipW2 :: (a -> b -> c) -> [a] -> [b] -> [c]
zipW2 f xs ys = [f x y | (x, y) <- zipW2 f xs ys]

I am not sure how to correct the second statement so that it works like zipWith and allows me to choose the operator.

Upvotes: 2

Views: 989

Answers (2)

rampion
rampion

Reputation: 89053

The original zipWith has three cases:

  1. when the first list is empty
  2. when the second list is empty
  3. when the neither list is empty

The third case recursively calls zipWith on the tails of the arguments, which does the case analysis again.

In your definition, you only have one case - the list comprehension, so any recursive calls are going to wrap right back to that. And without case analysis, you could loop forever here:

>>> let myZipWith f xs ys = [ f x y | (x,y) <- myZipWith f xs ys ]
>>> myZipWith (,) [] []
^CInterrupted.

Furthermore because you're using f in the recursive call but requiring that the recursive output be a pair, you're placing the implicit requirement that f x y produce a pair:

>>> :t myZipWith 
myZipWith :: (t2 -> t3 -> (t2, t3)) -> t -> t1 -> [(t2, t3)]

The solution is to not recurse, but instead to consider each pair directly.

You can use behzad.nouri's solution of enabling the ParallelListComp language extension:

>>> :set -XParallelListComp
>>> let myZipWith f xs ys = [ f x y | x <- xs | y <- ys ]
>>> myZipWith (+) [1,2,4] [0,10,20]
[1,12,24]

ParallelListComp makes the second (and later) vertical pipe characters (|) in a list comprehension legal syntax, stepping through those lists in parallel (zip-like) with earlier lists.

It's good to know how this differs from normal list comprehensions, where you separate each list you draw from with commas. Using commas does nested iteration which is flattened out in the resulting list:

>>> let notZipWith f xs ys = [ f x y | x <- xs, y <- ys ]
>>> notZipWith (+) [1,2,4] [0,10,20]
[1,11,21,2,12,22,4,14,24]

Using the ParallelListComp extension is really just syntatical sugar for the original zipWith, so you may consider it cheating.

You could also just rely on the original zip:

>>> let myZipWith f xs ys = [ f x y | (x,y) <- zip xs ys ]
>>> myZipWith (+) [1,2,4] [0,10,20]
[1,12,24]

But since zip is defined as zipWith (,), that's probably cheating too.

Another way you could go is to use indices:

>>> let myZipWith f xs ys = [ f x y | i <- [0..min (length xs) (length ys) - 1], let x = xs !! i, let y = ys !! i ]
>>> myZipWith (+) [1,2,4] [0,10,20]
[1,12,24]

But this is going to be horrendously inefficient, as !! is a linear-time operation, making myZipWith quadratic, while zipWith is linear:

>>> :set +s
>>> last $ myZipWith (+) (replicate 10000000 1) (replicate 10000000 2)
3
(4.80 secs, 3282337752 bytes)
>>> last $ zipWith (+) (replicate 10000000 1) (replicate 10000000 2)
3
(0.40 secs, 2161935928 bytes)

I'm sure there's other bad ways to create an equivalent to zipWith with a list comprehension, but I'm not terribly convinced that there's a good way, even from the ones above.

Upvotes: 2

behzad.nouri
behzad.nouri

Reputation: 77951

You will need Parallel List Comprehensions extension:

{-# LANGUAGE ParallelListComp #-}

zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' f xs ys = [f x y | x <- xs | y <- ys]

Upvotes: 3

Related Questions