Почему Haskell функция `transpose` в Data.List не использует` 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, но я тоже не эксперт. Это, как говорится, больше технических ответов и объяснений также будет высоко ценится, так как я надеюсь узнать больше о тонкостях языка в будущем (и даже если я не понимаю причину сейчас, я буду знать что я должен исследовать).

Answer 1

Для пустых списков, такие функции, как head и tail приведут к ошибке. Обратите внимание, что если вы напишите:

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

, тогда не эквивалентно map head xss. Действительно, приведенное выше понимание списка эквивалентно:

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

Так что в случае неудачного сопоставления с шаблоном мы возвращаем значение fail "". Для списка это пустой список:

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

Это важно для непрямых angular списков, которые мы хотим транспонировать, например:

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

Si это будет преобразуйте:

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

в:

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

Принимая во внимание, что если в конечном итоге использовать head и tail, в конечном итоге, когда он намеревается вычислить head и tail в третьем строка, она будет sh в списке [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