Понимание этой функции транспонирования матрицы в Haskell

Question

Эта матричная функция транспонирования работает, но я пытаюсь понять ее пошаговое выполнение и не понимаю.

    transpose:: [[a]]->[[a]]
    transpose ([]:_) = []
    transpose x = (map head x) : transpose (map tail x)

с

transpose [[1,2,3],[4,5,6],[7,8,9]]

возвращается:

 [[1,4,7],[2,5,8],[3,6,9]]

Я не понимаю, как оператор конкатенации работает с картой. Он объединяет каждую головку x в одном и том же вызове функции? Как?

это

(map head x)

создать список элементов заголовка каждого списка?

Answer 1

Давайте посмотрим, что функция делает для вашего примера ввода:

transpose [[1,2,3],[4,5,6],[7,8,9]]
<=>
(map head [[1,2,3],[4,5,6],[7,8,9]]) : (transpose (map tail [[1,2,3],[4,5,6],[7,8,9]]))
<=>
[1,4,7] : (transpose [[2,3],[5,6],[8,9]])
<=>
[1,4,7] : (map head [[2,3],[5,6],[8,9]]) : (transpose (map tail [[2,3],[5,6],[8,9]]))
<=>
[1,4,7] : [2,5,8] : (transpose [[3],[6],[9]])
<=>
[1,4,7] : [2,5,8] : (map head [[3],[6],[9]]) : (transpose (map tail [[3],[6],[9]]))
<=>
[1,4,7] : [2,5,8] : [3, 6, 9] : (transpose [[], [], []])
<=>
[1,4,7] : [2,5,8] : [3, 6, 9] : [] -- because transpose ([]:_) = []
<=>
[[1,4,7],[2,5,8],[3,6,9]]

Обратите внимание, что порядок, в котором я выбрал сокращение сроков, не совпадает с порядком оценки, который будет использовать haskell, но это не меняет результат.

Изменить: В ответ на ваш отредактированный вопрос:

это

(map head x)

создать список элементов заголовка каждого списка?

Да, это так.

Answer 2

ghci ваш друг:

*Main> :t map head
map head :: [[a]] -> [a]
*Main> :t map tail
map tail :: [[a]] -> [[a]]

Даже если вы не понимаете map (проблема, которую вы хотите быстро исправить!), Типы этих выражений многое говорят о том, как они работают. Первый - это отдельный список, взятый из списка списков, поэтому давайте подадим ему простой вектор, чтобы увидеть, что происходит.

Возможно, вы захотите написать

*Main> map head [1,2,3]

но это не проверяет тип:

<interactive>:1:14:
    No instance for (Num [a])
      arising from the literal `3' at :1:14
    Possible fix: add an instance declaration for (Num [a])
    In the expression: 3
    In the second argument of `map', namely `[1, 2, 3]'
    In the expression: map head [1, 2, 3]

Помните, тип аргумента - это список списков, поэтому

*Main> map head [[1,2,3]]
[1]

Немного сложнее

*Main> map head [[1,2,3],[4,5,6]]
[1,4]

То же самое, но с tail вместо head дает

*Main> map tail [[1,2,3],[4,5,6]]
[[2,3],[5,6]]

Как видите, определение transpose многократно отрезает первую «строку» с помощью map head x и транспонирует остальное, что составляет map tail x.

Answer 3

Оператор cons : присоединяет объект типа a к списку типа [a]. В

(map head x) : transpose (map tail x)

LHS - это список (a = [b]), тогда как RHS - это список списка ([a] = [[b]]), поэтому такая конструкция допустима. Результат

[x,y,z,...] : [[a,b,...],[d,e,...],...] = [[x,y,z,...], [a,b,...],[d,e,...],...]

---

В вашем случае map head x и map tail x разбивают матрицу

x = [[1,2,3],[4,5,6],[7,8,9]]

в

map head x = [1,4,7]
map tail x = [[2,3],[5,6],[8,9]]

(и да, map head x - это список элементов заголовка каждого списка.) 2-я часть транспонирована (подробности см. В @ sepp2k ) для формирования

transpose (map tail x) = [[2,5,8],[3,6,9]]

так что [1,4,7] так дает

map head x : transpose (map tail x) =  [1,4,7] : [[2,5,8],[3,6,9]]
                                    = [[1,4,7] ,  [2,5,8],[3,6,9]]

Answer 4

Эти вещи одинаковы:

map head xxs
map (\xs -> head xs) xxs

Это лямбда-выражение, что означает, что я возвращаю голову xs для каждого xs Пример:

   map head [[1,2,3],[4,5,6],[7,8,9]]
-> map (\xs -> head xs) [[1,2,3],[4,5,6],[7,8,9]]
-> [head [1,2,3], head [4,5,6], head [7,8,9]]
-> [1,4,7]

Все просто

Answer 5

Кстати, эта функция не работает при вводе, например [[1,2,3], [], [1,2]]. Однако функция транспонирования из Data.List примет этот вход и вернет [[1,1], [2,2], [3]].

Когда мы вызываем рекурсивный код transpose, нам нужно избавиться от [].