在Haskell中处理嵌套列表

Question

我是Haskell的初学者，所以在严格类型方面有一些困难，想知道是否有人可以帮助我构建一个函数。基本上，它接受一个列表的列表，例如：

[[1,2,3], [7,6,8], [0,3,4]]

它将所有列表合并为一个列表，并通过其位置的数量翻译后续列表。因此，对于示例列表，它实际上会执行以下操作：

foldl (zipWith +) [] [[1,2,3],[0,7,6,8],[0,0,0,3,4]]

这是我的当前函数（会出现类型错误）：

    addLists :: [[Integer]] -> [Integer]
    addLists [[]] = []
    addLists [[x]] = [x]
    addLists [x:xs] = zipWith (+) [x] ([0]++ (addLists xs))

- Nathan Edwards

---

请明确说明您希望addLists [[1,2,3], [7,6,8], [0,3,4]]的结果是什么。从您的问题中并不明显。 - dave4420

看起来您编辑了问题以进行澄清，但恐怕我仍然不理解。addLists [[1,2,3], [7,6,8], [0,3,4]]的结果应该是什么样子？您提供的示例foldl (zipWith +) [] [[1,2,3],[0,7,6,8],[0,0,0,3,4]]无法通过类型检查，我无法弄清楚您的意图。 - mhwombat

你想要的结果是 [1, 2+7, 3+6+0, 8+4, 4] = [1,9,9,12,4] 吗？ - mhwombat

抱歉，输出应为 [1，2+7，3+6+0，8+3，4]。 - Nathan Edwards

Answer 1

请注意，([0]++)与(0:)相同，这将使其看起来更整洁，并节省我们一两个纳秒的时间。 （我是在开玩笑关于纳秒的事情 - 没有人能够感觉到某件事情快了一个纳秒，但这样做更美好。）

让我们首先考虑如何创建所需的列表。我们想要：

postponeLists [[1,2,3], [7,6,8], [10,20,30,40]] 
             = [[1,2,3], [0,7,6,8], [0,0,10,20,30,40]]
             = [1,2,3] : ones that should have zero in front of them

这就足够解释了：

postponeLists [] = []
postponeLists (l:ls) = l : map (0:) (postponeLists ls)

现在你说：

foldl (zipWith +) [] [[1,2,3],[0,7,6,8],[0,0,0,3,4]]

但是你的意思是什么？

foldl (zipWith (+)) [] [[1,2,3],[0,7,6,8],[0,0,0,3,4]]

不幸的是，这会给你[]，因为zipWith一旦其中任何一个列表用完元素就停止。

我们需要一种不停止的方法来合并它们。

解决方案1：找到最长的那个，使用take maxlength.(++ repeat 0)使它们都成为maxlength。
解决方案2：编写另一个不会停止的zipWith函数。

我更喜欢解决方案2。让我们看看zipWith的定义。

zipWith :: (a->b->c) -> [a]->[b]->[c]
zipWith f (a:as) (b:bs) = f a b : zipWith f as bs
zipWith _ _      _      = [] -- here's the problem - it stops as soon as any list is empty

好的，那我们继续吧：

好的，那我们就不停下来：

zipWithMore :: (a -> a -> a) -> [a] -> [a] -> [a]
zipWithMore f (a:as) (b:bs) = f a b : zipWithMore f as bs
zipWithMore f []      bs      = bs -- if there's more in bs, use that
zipWithMore f as      []      = as -- if there's more in as, use that

现在你可以用zipWithMore(+)替换zipWith(+)。我会留下结论给你。

- AndrewC

---

(0:) 不会比 ([0]++) 更省下任何纳秒，至少在 ghc -O2 下不会。(:) 有时候确实比 (++) 更好用，但你不应该让这种纳秒的猜测来影响你的代码。 - shachaf

当然不是！我只是开玩笑地说“节省一两个纳秒”，以此来指出这是不必要的。(0:) 更好，我想养成这种习惯。像这样的问题谁会在意纳秒呢？我已经让它更清楚了，这不是认真的意思。 - AndrewC

Answer 2

我认为这可以满足你的需求。

import Data.List (transpose)

addLists :: Num a => [[a]] -> [a]
addLists xs = map sum . transpose $ zipWith (\n x -> replicate n 0 ++ x) [0..] xs

- Chris Taylor

---

谢谢，你能详细解释一下它是如何工作的吗？我大致上能够理解，但还不太确定！ - Nathan Edwards

@npfedwards 抱歉，我本来想回来扩展这个答案的，但是出了一些事情。希望很快就能完成！ - Chris Taylor

稍微优化一下：addLists = map sum . transpose . zipWith (++) (inits (repeat 0))。有趣的部分是 transpose，它是一个值得熟悉的 Data.List 函数。由于这是一个组合函数，你可以单独尝试每个部分来理解它们的工作原理。 - shachaf