Почему `transpose [[]] == []` в Haskell?
Рассмотрим следующее?
ghci> transpose []
[]
ghci> transpose [[]]
[]
ghci> transpose [[[]]]
[[[]]]
ghci> transpose [[[[]]]]
[[[[]]]]
ghci> transpose [[[[[]]]]]
[[[[[]]]]]
ghci> transpose [[[[[[]]]]]]
[[[[[[]]]]]]
Одна из этих вещей не похожа на другую :p
Мне очень странно видеть что-то столь неизящное в base, но я полагаю, что есть какая-то превосходная алгебраическая или теоретическая причина, почему они решили использовать transpose [[]] == []. Может кто-нибудь пролить некоторый свет на это?
base полон частичных функций, которые гораздо менее элегантны, чем эта.
Ответы 3
transpose меняет местами строки и столбцы.
[] имеет 0 строк и не совсем четко определенное количество столбцов, которые функция воспринимает как 0. Замена 0 строк на 0 столбцов ничего не меняет.
[[[]]] и далее по 1 строке и 1 столбцу. Замена 1 строки на 1 столбец тоже ничего не меняет.
[[]] имеет 1 строку и 0 столбцов. Замена 1 строки и 0 столбцов дает результат с 0 строками: пустой список.
Тип
transpose :: [[a]] -> [[a]]
заставляет transpose взять список списков a. Здесь a — произвольный тип, поэтому transpose не проверяет (и не может) проверять вводимые данные за пределами двух уровней списков.
Следовательно, опубликованные вами дела «видятся» transpose следующим образом:
ghci> transpose []
[]
ghci> transpose [[]]
[]
ghci> transpose [[something]]
[[something]]
ghci> transpose [[something]]
[[something]]
ghci> transpose [[something]]
[[something]]
ghci> transpose [[something]]
[[something]]
Теперь это легче понять. Как уже объяснил пользователь 2357112 в своем ответе, ввод [] равен 0*? матрица, [[]] — матрица 1*0, а [[something]] — матрица 1*1.
Мне нравится соображение, упомянутое в других ответах, когда я думаю о [[a]] как о матрице. Но я немного возражаю на том основании, что не все [[a]] на самом деле являются матрицами; довольно часто полезно иметь «неровные» вложенные списки, и transpose все еще может быть в них разумным и полезным. Поэтому я хотел бы привести некоторые аргументы, не предполагающие прямоугольности. У меня два.
Во-первых, предположим, что мы жили в альтернативной вселенной, где transpose [[]] = [[]]. Что же делать transpose [[], []]? На самом деле не существует хорошего способа отразить в выводе наличие двух пустых списков во входных данных. Итак, попробуем выбрать transpose [[], []] = [[]] еще раз. Но теперь у нас есть альтернативный сломанный шаблон:
> transpose [[], [], []]
[[]]
> transpose [[], []]
[[]]
> transpose [[]]
[[]]
> transpose []
[] -- whoops, not [[]] like the pattern would suggest
Если мы внесем все описанные выше изменения и изменим на transpose [] = [[]], чтобы этот шаблон работал, то ваш исходный шаблон снова сломается.
> transpose [[[[]]]]
[[[[]]]]
> transpose [[[]]]
[[[]]]
> transpose [[]]
[[]]
> transpose []
[[]] -- whoops, not [] like the pattern would suggest
Кажется, просто невозможно дать определение transpose, которое позволило бы реализовать все желаемые закономерности.
Во-вторых, текущее определение transpose действительно обладает некоторыми хорошими алгебраическими свойствами. Один из таких вот:
length' (transpose xs) = foldMap length' xs
Здесь length' аналогичен length, но возвращает беззнаковое число, экземпляр Monoid которого использует mappend = max; mempty = 0. Это свойство заставляет transpose [[]] = [], потому что
length' (transpose [[]]) = foldMap length' [[]]
= fold [length' []]
= fold [0]
= 0
и единственный способ получить length' foo = 0 — это foo = [].
(Этот второй аргумент очень и очень похож на аргумент, приведенный в других ответах, хотя он изложен совсем на другом языке!)
Это тот же результат, который дает
sequenceA @[] @ZipList [ZipList []]по модулю новых типов.