list - 为什么 Haskell 在 Data.List 中的 `transpose` 函数不使用 `head` 和 `tail` ？

Question

我刚刚花了一些时间来解决我需要以某种方式翻译列表列表的问题。成功完成后，我想出了这个解决方案:

translate :: [[a]] -> [[a]]
translate ([]:xss) = []
translate xss      = (map head xss) : (translate $ map tail xss)

不久之后，我意识到我只是在尝试转置矩阵...我想“我可能浪费了很多时间来尝试这样做，因为 Haskell 肯定有一个函数它的标准库来执行这种常见操作。”所以我决定检查一下，不出所料，我发现 Data.List 模块包含一个 transpose 函数。

但真正令我惊讶的是它的定义方式:

transpose               :: [[a]] -> [[a]]
transpose []             = []
transpose ([]   : xss)   = transpose xss
transpose ((x:xs) : xss) = (x : [h | (h:_) <- xss]) : transpose (xs : [ t | (_:t) <- xss])

它使用列表理解而不是 head 和 tail，我认为这很有趣但无法弄清楚为什么这样做。

为什么最好使用列表理解而不是预定义的 head 和 tail 函数(使用 map)，我对函数的处理方式？跟代码效率有关系吗？

我不一定是 Haskell 的新手，但我也不是专家。话虽这么说，更多的技术答案和解释也将不胜感激，因为我希望了解更多关于 future 语言的复杂性(即使我现在不明白原因，我也会知道我必须研究什么)。

Answer 1

对于空 列表，head 和tail 等函数将出错。请注意，如果您这样写:

[h | (h:_) <- xss]

那么这不等同于map head xss。事实上，上面的列表推导等同于:

let ok (h:_) = pure h
    ok _ = fail "…"
in xss >>= ok

因此，如果模式匹配失败，我们将返回一个fail "" 值。对于列表，这是空列表:

Prelude> fail "" :: [Int]
[]

这对于我们要转置的非矩形列表很重要，例如:

Prelude Data.List> transpose [[1,4,2,5],[1,3], [1,9,5,8]]
[[1,1,1],[4,3,9],[2,5],[5,8]]

所以它会变换:

[ 1 4 2 5]
[ 1 3 ]
[ 1 9 5 8]

到:

[1 1 1]
[4 3 9]
[2 5]
[5 8]

而如果一个人最终使用 head 和 tail 来计算 head 和 tail第三行，它会在 [1,3] 列表上崩溃:

Prelude Data.List> transpose' [[1,4,2,5],[1,3], [1,9,5,8]]
[[1,1,1],[4,3,9],[2,*** Exception: Prelude.head: empty list