In Haskell, è idiota scrivere tanto del tuo codice in funzioni di ordine superiore come pieghe, mappe e spiegazioni il più possibile. Quindi quali tipi di codice non possono essere scritti con quelle funzioni di ordine superiore? Quando è necessaria la ricorsione esplicita?Quando è necessaria la ricorsione esplicita?
Supponiamo di avere un linguaggio senza ricorsione o qualcosa del genere. Ciò significa che non ci sono strutture di looping. Significa anche che abbiamo anche dei tipi (non ricorsivi) in modo che non possiamo formare un combinatore Y e scappare. In questa lingua, siamo veramente deboli, separati da tanti nostri strumenti.
Ma possiamo porre una buona domanda su questa lingua. Vale a dire, qual è la cosa più piccola che dobbiamo dargli perché diventi altrettanto potente di una lingua senza tali restrizioni?
Si scopre che ci sono due risposte.
possiamo introdurre leganti ricorsive, come un comando let rec o qualcosa di simile let Haskell che è sempre let rec. In altre parole, una struttura che ci consente di definire let x = e in b in modo tale che se è libero in e, viene calcolato come punto fisso nell'equazione x = e.
Possiamo introdurre la funzione fix :: (a -> a) -> a tale che fix f si riduce in un passaggio a f (fix f).
Dovrebbe essere chiaro dalla presentazione di cui sopra che fix può essere implementato usando leganti ricorsive. Che cosa è un po 'meno chiaro è che leganti ricorsive possono essere implementati da quelli non ricorsivi usando fix, ma qui ci sono:
let x = fix $ \this -> e
Il valore this si riferisce a tutta l'espressione che finisce legato come x che è proprio quello vogliamo.
Quindi, perché ho fatto di tutto per dire tutto quanto sopra? In sostanza, mi piacerebbe sostenere che non è possibile affermare che la ricorsione è necessariamente implementata tramite combinatori HOF come map a condizione che si sia disposti a considerare fix in tale elenco. Mi piacerebbe anche argomentare che qualsiasi ricorsione implementata dai combinatori in quel set può essere eseguita "esplicitamente" usando i leganti ricorsivi. Sono ugualmente potenti.
La parte interessante arriva quando si considerano i combinatori HOF come foldr/unfoldr da soli. Questi sono in qualche modo un po 'più deboli rispetto a fix/ricorsivi. Il vantaggio è che se si costruisce un linguaggio di programmazione fuori solo un insieme selezionato di foldr/unfoldr principi -come allora si può ottenere un ricchissimo, sub-Turing linguaggio completo che può essere totale o garantito per terminare.
Penso che molte persone trovino le definizioni di dati ricorsive più facili da leggere rispetto ai tipi Mu/Fix/Nu. Non è strettamente necessario, ma molto utile lì.
Analogamente, è possibile scrivere le istanze Foldable/Unfoldabe per tale tipo di dati utilizzando la ricorsione, ma una volta fornite, la ricorsione esplicita non è richiesta in futuro.
Stai chiedendo quando la ricorsione è * necessaria * o quando è * idiomatica *? Il tuo titolo dice il primo; la tua ultima frase dice il secondo. –
Buon punto. Mi stavo chiedendo entrambi, ma lo limiterò a una domanda: quando è effettivamente necessaria la ricorsione esplicita? Modificherò la domanda. –
Le funzioni di ordine superiore come 'map' e' fold' sono implementate con ricorsione. Se li stai usando, semanticamente, stai usando la ricorsione. Sintatticamente, non è mai necessario ricorrere alla ricorsione, tranne una volta, per definire la "funzione ricorsiva canonica" - 'fix f = let x = f x in x'. – user2407038