Implementazione della mappa con ricorsione della coda

La ricorsione della coda non è una buona idea in Haskell con le funzioni di lista, perché la ricorsione in coda impedisce alla valutazione lenta di restituire un risultato parziale.

Comunque, per rispondere alla tua domanda, è possibile scrivere una funzione "mappa invertita" (come map eccetto che l'ordine degli elementi è invertito) che è ricorsivo in coda e non passa attraverso l'elenco di ogni passaggio. Mantiene un accumulatore che è l'elenco dei risultati finora (indietro) e per ogni nuovo elemento nell'input antepone il risultato all'accumulatore (ed è per questo che è indietro).

reverseMap :: (a -> b) -> [a] -> [b]
reverseMap func = helper [] where
  helper acc [] = acc
  helper acc (h:t) = helper (func h : acc) t

Naturalmente, dato che hai ottenuto i risultati all'indietro, devi invertirlo di nuovo, e dal momento che reverse è anch'esso ricorsivo in coda, l'intera operazione è ricorsiva in coda.

myMap :: (a -> b) -> [a] -> [b]
myMap func = helper [] where
  helper acc [] = reverse acc
  helper acc (h:t) = helper (func h : acc) t

Le funzioni ricorsive in Haskell sono attività complicate.

Haskell è pigro, quindi nella maggior parte delle situazioni questa funzione sarà valutata solo se necessario, e ciò significa che la prima cosa valutata sarà sempre il tipo costruttore : , poiché tutto ciò che usa il risultato deve prima guardare al costruttore del tipo prima che possa guardare qualsiasi valore all'interno.

Quindi Haskell prima crea un nodo lista contenente uno stub non valutato per il valore func h e uno stub non valutato per la coda accumulateRec func t . E solo quando questi valori sono effettivamente necessari valuterà questi stub.

O in altre parole, in Haskell, qualsiasi funzione ricorsiva che utilizza il risultato di ricorsione come argomento per un costruttore di dati probabilmente non è effettivamente ricorsiva nel modello di esecuzione.

La linea di fondo è che la funzione che hai già ha il vantaggio che le funzioni ricorsive della coda hanno, vale a dire la valutazione dello spazio costante invece di costruire una grande pila di ricorsioni.