2

我已经使用递归重写了 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 一样工作，并允许我选择运算符。

4

2 回答 2

3

您将需要Parallel List Comprehensions扩展：

{-# LANGUAGE ParallelListComp #-}

zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' f xs ys = [f x y | x <- xs | y <- ys]
于 2015-11-13T01:06:13.093 回答
0

原文zipWith分三种情况：

  1. 当第一个列表为空时
  2. 当第二个列表为空时
  3. 当两个列表都不为空时

第三种情况递归调用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)]

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

您可以使用 behzad.nouri 启用ParallelListComp语言扩展的解决方案：

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

使用ParallelListComp扩展实际上只是原始的语法糖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与列表理解的等价物，但我不太相信有一个好方法，即使是上面的方法。

于 2015-11-13T01:36:42.717 回答