Comprendere questa funzione di trasposizione della matrice in Haskell

Question

Questa funzione di trasposizione della matrice funziona, ma sto cercando di capire la sua esecuzione passo dopo passo e non la capisco.

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

con

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

ritorna:

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

Non capisco come l'operatore di concatenazione sta lavorando con la mappa. Concatena ogni testa di x nella stessa chiamata di funzione? Come?

è questo

(map head x) 

creazione di un elenco degli elementi di testa di ciascuna lista? sguardo

Answer 1

Let a ciò che la funzione fa per il tuo esempio di input:

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

Si noti che l'ordine in cui ho scelto di ridurre i termini, non è lo stesso del Haskell ordine di valutazione utilizzerà, ma che non cambia il risultato.

Edit: In risposta alla tua domanda modificato:

è questo

(map head x) 

creazione di un elenco degli elementi di testa di ciascuna lista?

Sì, lo è.

Answer 2

L'operatore cons : collega un oggetto di tipo a a un elenco di tipo [a]. In

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

Il lato sinistro è una lista (a = [b]), mentre il lato destro è una lista di lista ([a] = [[b]]), in modo tale costruzione è valido. Il risultato è

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

---

Nel tuo caso, map head x e map tail x divide la matrice

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

in

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

(e sì, map head x è un elenco degli elementi di testa di ogni lista.) Il 2 ° parte è recepita (per le fasi di dettaglio vedere @sepp2k 's risposta) per formare

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

così contro-ing [1,4,7] a questo dà

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 è tuo amico:

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

Anche se non capisci map (un problema che vorresti correggere velocemente!), I tipi di queste espressioni raccontano molto di come lavorano. Il primo è un singolo elenco preso da un elenco di liste, quindi diamo un semplice vettore ad esso per vedere cosa succede.

Si potrebbe desiderare di scrivere

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

ma che non riesce a 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]

Ricordate, il tipo di argomento è una lista di liste, in modo

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

Ottenere un un po 'più complesso

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

fare lo stesso ma con tail invece di head dà

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

Come si può vedere, la definizione di transpose viene ripetutamente affettando il via la prima “riga” con map head x e che recepisce il resto, che è map tail x.

Answer 4

A proposito, questa funzione non funziona quando viene fornito un input come [[1,2,3], [], [1,2]]. Tuttavia, la funzione di trasposizione da Data.List accetta questo input e restituisce [[1,1], [2,2], [3]].

Quando si chiama il codice ricorsivo transpose, è necessario eliminare lo [].

Answer 5

Queste cose sono uguali:

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

È lambda-espressione, che significa torno alla testa di xs ogni xs Esempio:

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] 

È semplice