concatenazione con (++)
forse sto pensando di profondità in questo, ma, per quanto ho capito, se si tenta di concatenare liste usando (++)
ad esempio:
[1, 2, 3] ++ [4, 5]
(++)
deve attraversare la lista di sinistra completa. Dare uno sguardo allo code of (++) lo rende ancora più chiaro.
(++) :: [a] -> [a] -> [a]
(++) [] ys = ys
(++) (x:xs) ys = x : xs ++ ys
Pertanto, sarebbe preferibile evitare l'uso (++)
, dal momento che con ogni chiamata reverse(xs)++[x]
nell'elenco è sempre più grande (o più piccolo a seconda sul punto di vista. In ogni modo, il programma deve semplicemente attraversare un'altra lista con ogni chiamata)
Esempio:
Diciamo implemento inverso come proposto attraverso la concatenazione.
reversex ::[Int]->[Int]
reversex [] = []
reversex (x:xs) = reversex(xs)++[x]
Inversione di una lista [1, 2, 3, 4] apparirebbe un po 'come questo:
reversex [1, 2, 3, 4]
reversex [2, 3, 4] ++ [1]
reversex [3, 4] ++ [2] ++ [1]
reversex [4] ++ [3] ++ [2] ++ [1]
reversex [] ++ [4] ++ [3] ++ [2] ++ [1]
[] ++ [4] ++ [3] ++ [2] ++ [1]
[4] ++ [3] ++ [2] ++ [1]
[4, 3] ++ [2] ++ [1]
[4, 3, 2] ++ [1]
[4, 3, 2, 1]
ricorsione in coda utilizzando l'operatore cons (:) !!!
Un metodo per gestire gli stack di chiamate è aggiungere accumulator. (non è sempre possibile aggiungere solo un accumulatore. Ma la maggior parte delle funzioni ricorsive offerte uno con sono primitive recursive e può quindi essere trasformata in tail recursive functions.)
Con l'aiuto dell'accumulatore, è possibile fare questo esempio lavoro, usando l'operatore cons (:)
. L'accumulatore - ys
nel mio esempio - si accumula il risultato corrente e viene trasmesso come parametro. A causa della dell'accumulatore siamo ora in grado di utilizzare le contro all'operatore di accumulare il risultato aggiungendo il capo della nostra lista iniziale ogni volta.
reverse' :: (Ord a) => [a] -> [a] -> [a]
reverse' (x:xs) ys = reverse' xs (x:ys)
reverse' [] ys = ys
C'è una cosa da notare qui.
L'accumulatore è un argomento in più. Non so se Haskell fornisce parametri di default, ma in questo caso sarebbe bello, perché si sarebbe sempre chiamare questa funzione con un elenco vuoto come l'accumulatore in questo modo: reverse' [1, 2, 3, 4] []
v'è abbondanza di letteratura sulla ricorsione in coda e sono sicuro che ci sono un sacco di domande simili su StackExchange/StackOverflow. Si prega di correggermi se trovate errori.
Cordiali saluti,
EDIT 1:
Will Ness ha sottolineato alcuni link per davvero buone risposte per quelli di voi che sono interessati:
EDIT 2:
Ok. Grazie a dFeuer e alle sue correzioni penso di capire Haskell un po 'meglio.
1.Il $!
è al di fuori della mia comprensione. In tutti i miei test sembrava che lo peggiorasse le cose.
2.As dFeuer sottolineato: Il thunk rappresenta l'applicazione di (:)
per x
e y
è semanticamente identico al x:y
ma richiede più memoria. Quindi questo è speciale per l'operatore cons (e costruttori pigri) e non è necessario forzare le cose in alcun modo.
3.If che invece sumUp interi di un elenco utilizzando una funzione molto simile, valutazione rigorosa attraverso BangPatterns o la funzione seq
impedirà la pila diventi troppo grande se utilizzati in modo appropriato. ad esempio:
sumUp' :: (Num a, Ord a) => [a] -> a -> a
sumUp' (x:xs) !y = reverse' xs (x + y)
sumUp' [] y = y
Notare il botto di fronte a y. L'ho provato in ghci e lo occupa meno memoria.
Come nota a margine, si può (e dovrebbe) chiamata senza l'utilizzo di parentesi: 'inversa (x: xs) = xs invertire ++ [x]', o verrai inciampato quando lavori con funzioni con più argomenti. –
Non chiamare funzioni come 'func (arg)'. Quello è il povero Haskell. Chiamate sempre funzioni come 'func arg'.Il codice con spazi chiari rende il codice più sicuro e leggibile. – AJFarmar