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

Question

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

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

不久之后，我意识到我只是想转置一个矩阵...我想"I probably lost a lot of time trying to do this, as surely Haskell has a function in its standard libraries to do such a common operation."所以我决定检查一下，不出所料我发现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，但我也不是专家。话虽这么说，更多的技术答案和解释 也将不胜感激，因为我希望了解更多关于未来语言的复杂性（即使我不明白原因现在我知道我要研究什么了）。

Answer 1

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

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

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

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

所以如果模式匹配失败，那么我们 return 一个 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

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

Why does Haskell's `transpose` function in Data.List not use `head` and `tail`?

haskell

transpose

list

definition

nested-lists