Comprender esta función de transposición de matrices en Haskell

Question

Esta función de transposición matricial funciona, pero estoy intentando comprender su ejecución paso a paso y no la entiendo.

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

con

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

que devuelve:

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

No entiendo cómo el operador de concatenación está trabajando con el mapa. ¿Concatena cada cabeza de x en la misma llamada de función? ¿Cómo?

es este

(map head x) 

creación de una lista de los elementos centrales de cada lista? mirada

Answer 1

Vamos a lo que hace la función por su ejemplo de entrada:

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]] 

Tenga en cuenta que el orden en el que he elegido para reducir los términos, no es el mismo que el Haskell orden de evaluación va a utilizar, pero eso no cambia el resultado

Editar: En respuesta a su pregunta Editado:

es este

(map head x) 

creación de una lista de los elementos centrales de cada lista?

Sí, lo es.

Answer 2

El operador cons : adjunta un objeto del tipo a a una lista del tipo [a]. En

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

El LHS es una lista (a = [b]), mientras que el RHS es una lista de lista ([a] = [[b]]), de manera tal construcción es válido. El resultado es

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

---

En su caso, map head x y map tail x divide la matriz

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

en

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

(y sí, map head x es una lista de los elementos de cabeza de cada lista.) La segunda parte se transpone (por pasos detallan ver @sepp2k 'respuesta s) para formar

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

así contras-Ing [1,4,7] a esto le da

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 3

ghci es su amigo:

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

Incluso si no comprende map (¡un problema que desea corregir rápidamente!), Los tipos de estas expresiones dicen mucho sobre cómo trabajan. La primera es una lista única tomada de una lista de listas, así que vamos a darle un vector simple para ver qué sucede.

Es posible que desee escribir

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

pero que no termina de typecheck:

<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]

Recuerde, el tipo del argumento es una lista de listas, por lo

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

Conseguir una un poco más complejo

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

Hacer lo mismo pero con tail en lugar de head da

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

Como se puede ver, la definición de transpose es cortar en varias ocasiones de la primera “fila” con map head x y transponer el resto, que es map tail x.

Answer 4

Por cierto, esta función no funciona cuando se le da una entrada como [[1,2,3], [], [1,2]]. Sin embargo, la función de transposición de Data.List aceptará esta entrada y devolverá [[1,1], [2,2], [3]].

Cuando llamamos al código recursivo transpose, tenemos que deshacernos del [].

Answer 5

Estas cosas son los mismos:

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

Es lambda-expresión, lo que significa que regrese la cabeza de xs para cada xs Ejemplo:

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] 

Es simple