While o Tail Recursion in F #, cosa usare quando?

Ok, solo in F # e questo è il modo in cui ora lo capisco:

Quindi la mia domanda: dato che F # supporta anche il paradigma imperativo, useresti la ricorsione in coda in F # per problemi che non sono naturalmente ricorsivi? Soprattutto da quando ho letto il compilatore ricontatta la ricorsione della coda e lo trasforma in un ciclo while comunque?

Se è così: perché?

La risposta migliore è “nessuno dei due”. 🙂

C’è un po ‘di bruttezza associata ad entrambi i loop e alla ricorsione della coda.

Sebbene i loop richiedano mutabilità ed effetti, e sebbene io non abbia nulla contro l’uso di questi con moderazione, specialmente quando sono incapsulati nel contesto di una funzione locale, a volte ti senti come se stessi ingombrando / distruggendo il tuo programma quando inizi a introdurre effetti solo per il ciclo .

La ricorsione della coda ha spesso lo svantaggio di richiedere un parametro aggiuntivo di accumulo o uno stile di passaggio di continuazione. Questo disturba il programma con una piastra in più per massaggiare le condizioni di avvio della funzione.

La migliore risposta è quella di non usare né i loop né la ricorsione. Le funzioni di ordine superiore e lambda sono i tuoi salvatori qui, in particolare le mappe e le pieghe. Perché scherzare con strutture di controllo disordinate per il looping quando puoi incapsulare quelle nelle librerie riutilizzabili e quindi indicare semplicemente l’essenza del tuo calcolo in modo semplice e dichiarativo?

Se hai l’abitudine di chiamare spesso map / fold piuttosto che usare loop / ricorsione, oltre a fornire una funzione di piega insieme a qualsiasi nuovo tipo di dati strutturato ad albero che introduci, andrai lontano. 🙂

Per chi è interessato a saperne di più sulle pieghe in F #, perché non controllare i miei primi tre post del blog in una serie sull’argomento?

In ordine di preferenza e di stile generale di programmazione, scriverò il codice come segue:

Mappa / piega se disponibile

let x = [1 .. 10] |> List.map ((*) 2) 

È semplicemente comodo e facile da usare.

Funzione ricorsiva non a coda

 > let rec map f = function | x::xs -> fx::map f xs | [] -> [];; val map : ('a -> 'b) -> 'a list -> 'b list > [1 .. 10] |> map ((*) 2);; val it : int list = [2; 4; 6; 8; 10; 12; 14; 16; 18; 20] 

La maggior parte degli algoritmi è più facile da leggere ed esprimere senza ricorsione in coda. Ciò funziona particolarmente bene quando non è necessario ricorrere troppo profondamente, rendendolo adatto a molti algoritmi di ordinamento e alla maggior parte delle operazioni su strutture di dati bilanciate.

Ricorda, registra 2 (1.000.000.000.000.000) ~ = 50, quindi l’operazione di log (n) senza ricorsione in coda non è affatto spaventosa.

Coda ricorsiva con accumulatore

 > let rev l = let rec loop acc = function | [] -> acc | x::xs -> loop (x::acc) xs loop [] l let map fl = let rec loop acc = function | [] -> rev acc | x::xs -> loop (fx::acc) xs loop [] l;; val rev : 'a list -> 'a list val map : ('a -> 'b) -> 'a list -> 'b list > [1 .. 10] |> map ((*) 2);; val it : int list = [2; 4; 6; 8; 10; 12; 14; 16; 18; 20] 

Funziona, ma il codice è goffo e l’eleganza dell’algoritmo è leggermente oscurata. L’esempio sopra non è male da leggere, ma una volta entrati in strutture dati ad albero, inizia davvero a diventare un incubo.

Coda ricorsiva con passaggio di continuazione

 > let rec map cont f = function | [] -> cont [] | x::xs -> map (fun l -> cont <| fx::l) f xs;; val map : ('a list -> 'b) -> ('c -> 'a) -> 'c list -> 'b > [1 .. 10] |> map id ((*) 2);; val it : int list = [2; 4; 6; 8; 10; 12; 14; 16; 18; 20] 

Ogni volta che vedo un codice come questo, mi dico “ora è un trucco perfetto!”. A scapito della leggibilità, mantiene la forma della funzione non ricorsiva e lo trova molto interessante per gli inserimenti ricorsivi di coda in alberi binari .

Probabilmente è la mia monade-fobia che parla qui, o forse la mia intrinseca mancanza di familiarità con il call / cc di Lisp, ma penso che quelle occasioni in cui CSP semplifica davvero gli algoritmi sono poche e lontane tra loro. Gli esempi contrari sono i benvenuti nei commenti.

Mentre loop / per loops

Mi viene in mente che, a parte le comprensioni di sequenza, non ho mai usato il ciclo F # durante il ciclo. In ogni caso…

 > let map fl = let l' = ref l let acc = ref [] while not <| List.isEmpty !l' do acc := (!l' |> List.hd |> f)::!acc l' := !l' |> List.tl !acc |> List.rev;; val map : ('a -> 'b) -> 'a list -> 'b list > [1 .. 10] |> map ((*) 2);; val it : int list = [2; 4; 6; 8; 10; 12; 14; 16; 18; 20] 

È praticamente una parodia della programmazione imperativa. Potresti essere in grado di mantenere un po ‘di equilibrio dichiarando let mutable l' = l , invece, ma qualsiasi funzione non banale richiederà l’uso di ref .

Molti problemi hanno una natura ricorsiva, ma aver pensato imperativamente per un lungo periodo spesso ci impedisce di vederlo.

In generale, utilizzerei una tecnica funzionale laddove ansible in un linguaggio funzionale: i loop non sono mai funzionali poiché si basano esclusivamente sugli effetti collaterali. Quindi, quando si tratta di codice o algoritmi imperativi, l’uso di loop è adeguato, ma in un contesto funzionale, non sono considerati molto interessanti.

La tecnica funzionale non si riferisce solo alla ricorsione, ma utilizza anche le funzioni appropriate di ordine superiore.

Quindi, sumndo una lista, né un ciclo for, né una funzione ricorsiva, ma una fold è la soluzione per avere un codice comprensibile senza reinventare la ruota.

Onestamente, qualsiasi problema che puoi risolvere con un ciclo è già ricorsivo in modo naturale, dato che puoi tradurre entrambi in salti (solitamente condizionati) alla fine.

Credo che dovresti rispettare le chiamate di coda in quasi tutti i casi in cui devi scrivere un ciclo esplicito. È solo più versatile:

  • Un ciclo while ti limita a un corpo di loop, mentre una coda ti consente di passare da uno stato all’altro mentre il “loop” è in esecuzione.
  • Un ciclo while ti limita a una condizione per controllare la terminazione, con la ricorsione della coda puoi avere un’espressione di corrispondenza arbitrariamente complicata in attesa di deviare il stream di controllo da un’altra parte.
  • La coda chiama tutti restituisce valori utili e può produrre errori di tipo utili. Un ciclo while non restituisce nulla e si basa su effetti collaterali per fare il suo lavoro.
  • Mentre i loop non sono di prima class mentre funzionano con le chiamate tail (o mentre i loop sono in essi) lo sono. I binding ricorsivi in ​​ambito locale possono essere controllati per il loro tipo.
  • Una funzione ricorsiva della coda può essere facilmente suddivisa in parti che utilizzano chiamate in coda per chiamarsi reciprocamente nella sequenza necessaria. Questo potrebbe rendere le cose più facili da leggere e ti aiuterà se scoprirai di voler iniziare nel bel mezzo di un ciclo. Questo non è vero per un ciclo while.

Tutto sumto mentre i loop in F # sono utili solo se lavorerai veramente con lo stato mutabile, all’interno di un corpo di una funzione, facendo ripetutamente la stessa cosa fino a quando una certa condizione non viene soddisfatta. Se il ciclo è generalmente utile o molto complicato, potresti volerlo scomporre in un altro bind di livello superiore. Se i tipi di dati sono essi stessi immutabili (un sacco di tipi di valore .NET sono), è ansible ottenere molto poco dall’utilizzo di riferimenti mutabili a loro comunque.

Direi che dovresti ricorrere solo a loop per casi di nicchia in cui un ciclo while è perfetto per il lavoro ed è relativamente breve. In molti linguaggi di programmazione imperativi, mentre i loop sono spesso intrecciati in ruoli innaturali come roba di guida ripetutamente su una dichiarazione di un caso. Evita questo tipo di cose e vedi se puoi usare le chiamate di coda o, ancora meglio, una funzione di ordine superiore, per raggiungere gli stessi fini.

per problemi che non sono naturalmente ricorsivi .. lo trasformi in un ciclo while comunque

Hai risposto tu stesso. Usa la ricorsione per problemi ricorsivi e loop per cose che non sono funzionali in natura. Pensa sempre: che sembra più naturale, che è più leggibile.