使用列表理解重写 zipWith 函数

Question

我已经使用递归重写了 zipWith 函数，现在我正在尝试使用列表理解重写它。我有运行很多绑定错误，我知道我的第二行不正确。这是我的函数，它像使用递归的 zipWith 一样工作：

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

这是我将其重写为列表理解的尝试：

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

我不确定如何更正第二个语句，使其像 zipWith 一样工作并允许我选择运算符。

Answer 1

您将需要 Parallel List Comprehensions 分机：

{-# LANGUAGE ParallelListComp #-}

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

Answer 2

原zipWith有三种情况：

当第一个列表为空时
当第二个列表为空时
当两个列表都不为空时

第三个案例在参数的尾部递归调用zipWith，再次进行案例分析。

在您的定义中，您只有一种情况 - 列表推导式，因此任何递归调用都将直接返回到该情况。如果没有案例分析，你可以在这里永远循环：

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

此外，因为您在递归调用中使用了 f 但要求递归输出是一对，所以您提出了 f x y 产生一对的隐含要求：

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

解决方案是不递归，而是直接考虑每一对。

你可以:

>>> :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 在列表理解合法语法中生成第二个（和后面的）垂直竖线字符 (|)，与前面的列表并行（类似 zip）遍历这些列表。

很高兴知道这与普通列表推导式有何不同，在普通列表推导式中，您用逗号分隔每个列表。使用逗号进行嵌套迭代，它在结果列表中被展平：

>>> 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，所以你可以认为这是作弊。

你也可以只依赖原来的 zip:

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

但由于 zip 被定义为 zipWith (,)，这可能也是作弊。

另一种方法是使用索引：

>>> 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]

但这将是非常低效的，因为 !! 是一个线性时间操作，使得 myZipWith 是二次的，而 zipWith 是线性的：

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

我敢肯定还有其他不好的方法可以通过列表理解创建等同于 zipWith 的方法，但我不太相信有好的方法, 即使是上面的那些。

使用列表理解重写 zipWith 函数

Rewriting zipWith function using list comprehension

zip

haskell

list-comprehension

list

winghci