Si consideri il seguente (Haskell) Codice:Questa funzione di sequenza di Fibonacci è ricorsiva?
fib=0:1:zipWith (+) fib (tail fib)
Un collega sta cercando di affermare che questa non è una funzione ricorsiva perché fib è semplicemente un elenco che si definisce con se stessa e che è in qualche modo diverso da una funzione che fa lo stesso. Penso che stia fumando crack.
Cosa ne pensi?
La definizione di fibonacci con zipWith non è una funzione ricorsiva, infatti non è coinvolta alcuna funzione, fib è una lista (dati) che è pigramente auto-definita, utilizzando la pigra semantica di Haskell. In un certo senso, puoi chiamarlo lista ricorsiva o dati ricorsivi; ma non funzione ricorsiva.
Potrebbe essere difficile racchiudere la lista ricorsiva poiché pochissimi linguaggi di programmazione hanno qualcosa vicino, ma noterete che in Haskell tutte le funzioni richiedono esattamente un parametro. fib non accetta alcun parametro, perché non è una funzione. Poiché non è coinvolta alcuna funzione, non è possibile avere una funzione ricorsiva.
Il tuo collega non sta fumando crack, è illuminato (o fumo crack, se questa è la tua definizione di illuminazione).
Questo è semplicemente sbagliato: 'zipWith' è una funzione ricorsiva che definisce la sequenza.'fib' non è una lista ricorsiva: è una lista semplice e non ricorsiva che si riferisce al risultato * della valutazione della funzione ricorsiva' zipWith' *. (Sì, Haskell supporta anche dati ricorsivi, ma questo si riferisce a definizioni come 'xs = 1: 2: 3: xs', non all'esempio della domanda.) –
@Piet Delport:' fib' appare sul lato destro del proprio definizione .... che parola usi per quello? Io chiamo "ricorsivo". Né la ricorsività né la funzionalità (funzionalità?) Di 'zipWith' vengono messe in discussione qui. –
pelotom: In Haskell esiste una differenza fondamentale tra i dati * ricorsivi e le funzioni ricorsive *. I dati ricorsivi si hanno quando una struttura di dati si riferisce concretamente ai propri costruttori, come accade quando si dice 'xs = 1: 2: 3: xs': i contro finali si riferiscono a quello iniziale, formando un ciclo. Esistono molti modi diversi per ottenere questo tipo di ricorsione dei dati: vedere [Tying the Knot] (http://www.haskell.org/haskellwiki/Tying_the_Knot). Le funzioni ricorsive, d'altra parte, sono come 'zipWith'. Possono anche o non definire strutture dati ricorsive, ma in questo caso, 'fib' non lo è. –
L'esempio che hai fornito è ricorsivo. Ma la sequenza di Fibonacci per natura non deve essere. Ci sono iterative versions of the algorithm e anche explicit functions.
L'iterazione è solo un caso speciale di ricorsione, e generare una sequenza sarà sempre ricorsivo in un certo senso, per ragioni spero ovvie. La formula per calcolare indipendentemente singoli termini, tuttavia, non è di per sé ricorsiva (sebbene utilizzi funzioni che verranno probabilmente calcolate in modo ricorsivo). –
A parte l'implementazione Haskell qui, i numeri di Fibonacci sono una sequenza definita da una relazione di ricorrenza. Matematicamente parlando, ogni termine è definito come una funzione dei termini precedenti. Sconfiggilo con la semantica matematica.
Sebbene la definizione standard sia la relazione di ricorrenza, qualsiasi implementazione specifica potrebbe utilizzare il modulo chiuso (anche se questo non lo è), quindi questo non sarebbe un argomento valido per le domande di implementazione. –
È ricorsivo. Si può dire perché il nome sul LHS del = appare anche sul RHS.
È tuttavia non una funzione. È possibile sapere perché il tipo di fib non contiene uno ->.
È passato molto tempo dall'ultima volta che ho usato Haskell. Utilizzare il costruttore di funzioni è un requisito indispensabile per creare una funzione? Non riesco a trovare un'istruzione definita nel rapporto Haskell, ma il tipo di funzione è definito lessicalmente come 'type :: = btype [-> type]', cioè il costruttore di funzioni seguito da un altro tipo è facoltativo. Tuttavia, in seguito si dice che "Un tipo di funzione ha la forma' t1 -> t2' ... ". [[fonte] (http://www.haskell.org/onlinereport/haskell2010/haskellch4.html#x10-620004)] –
'fib' non è la funzione,' zipWith' è. –
@Piet: Ma quella non era la domanda. L'OP dice esplicitamente "questa funzione di sequenza di Fibonacci", quindi non sta chiaramente chiedendo di zipWith (a meno che tu non stia dicendo che zipWith è "funzione di sequenza di Fibonacci"). – sepp2k
Perché questa funzione sia ricorsiva, deve essere sia ricorsiva che una funzione. Come fa notare sepp2k, è chiaramente ricorsivo perché il nome fib appare su entrambi i lati dello =. Cioè, fib è definito in termini di se stesso.
È una funzione? Non secondo il suo tipo. In haskell, chiamiamo una funzione "dati" con argomento 0. Quindi questa definizione di fib crea una struttura dati ricorsiva, ma non una funzione ricorsiva.
'fib' è una * non * struttura dati ricorsiva in questo caso:" struttura dati ricorsiva "significa qualcosa di completamente diverso in Haskell. 'fib' è una struttura di dati infinita, non ripetitiva (e quindi non ricorsiva) generata da una funzione ricorsiva (' zipWith'). –
Mio, che ratto di sottili distinzioni terminologiche. Cos'è questo"?
fib=0:1:zipWith (+) fib (tail fib)
Non è una funzione ricorsiva. Non sono dati ricorsivi. È una definizione ricorsiva.
Cosa viene definito?
fib
Che tipo di cosa è fib, secondo questa definizione?
[Integer]
Un elenco di numeri interi (o forse un elenco di tutti i vecchi dati numerici).
È fib una funzione? No, è una lista. fib è definito in modo ricorsivo? Sì. fib è definito in modo ricorsivo se abbiamo sostituito zipWith con una funzione non ricorsiva dello stesso tipo (ad esempio \ f xs ys -> xs)? Sì, anche se sarebbe un elenco definito ricorsivamente diverso.
È fib un elenco ciclico? No. La "struttura dati ricorsiva" significa "struttura ciclica dei dati"? Non secondo il documento di Hoare, "Strutture dati ricorsive": http://portal.acm.org/book_gateway.cfm?id=63445&type=pdf&bookpath=%2F70000%2F63445%2Fcb-p217-hoare.pdf&coll=&dl=&CFID=15151515&CFTOKEN=6184618
In un'impostazione tipizzata, "struttura dati ricorsiva" significa non più o meno di "abitante di un tipo definito in modo ricorsivo". Corrispondentemente "fred" è una struttura dati ricorsiva, anche se non è definita in modo ricorsivo, e infatti può essere gestita da funzioni ricorsive come ++.
L'espressione "funzione ricorsiva" indica "funzione definita ricorsivamente". La frase "valore ricorsivo" significa "valore definito ricorsivamente", come esiste nei linguaggi non stretti: le lingue rigide hanno il problema della "ricorsione del valore".
E se si pensa che è pedante, provare a definire fib in questo modo in un totale linguaggio di programmazione , e scoprirete che la nozione di "definizione ricorsiva" si divide in "Definizioni ricorsione strutturale" (che consumano dati in un modo che si ferma) e "definizione per corecursione controllata" (producendo dati in un modo che va), e che fib è di quest'ultima varietà. In questa impostazione, la produttività di fib dipende in modo cruciale dalla pigrizia di zipWith. Nell'ambientazione di Haskell, ovviamente, non devi preoccuparti di nessuna di quelle cose per capire che tipo di definizione è qualcosa, solo per capire se ha una mezza possibilità di funzionare.
Poiché la maggior parte delle risposte sostengono il collega per quanto riguarda la funzione di parte di: "fib è non una funzione ricorsiva" Mi piacerebbe approfondire la parte ricorsiva che Conor McBride ha accennato nella sua risposta.
La definizione data per fib è non ricorsiva, è co-ricorsiva.
La ricorsione coincide con la ricorsione in quanto, come molti posters hanno sottolineato, anche l'RHS della definizione appare sul RHS. Ma non c'è un caso base. La ricorsione e il corecursion "corrono in direzioni opposte".
La precedente definizione di fib inizia dai valori iniziali 0 e 1 e si sposta "su" da lì e continua. D'altro canto, una definizione ricorsiva, dire (una funzione di calcolo) il numero di Fibonacci n-esimo
fib' 0 = 0
fib' 1 = 1
fib' n = fib' (n-1) + fib' (n-2)
passeggiate "basso" dal numero n-esimo fino a raggiungere i casi di base e ci si ferma.
Credo che questo rivendica la crackhead in entrambi i punti :-)
Per ulteriori letture controllare le voci di Wikipedia Corecursion ei collegamenti lì. Se riesci a metterti le mani su di esso, il capitolo 10 di Haskell Road to Logic, Maths and Programming di Kees Doets e Jan van Eijck può essere degno di una sbirciatina.
Anche se molte persone nei commenti stanno discutendo se la definizione è o meno una funzione, ma tutti sembrano concordare sul fatto che sia ricorsiva.
Per quanto riguarda l'argomento funzione/non funzionale, in Haskell, dal punto di vista del programmatore, NON CI INTERESSA! Poiché entrambe le funzioni e le strutture dati vengono valutate pigramente, un valore e una funzione senza argomenti che restituiscono un valore sono indistinguibili. Quello che hai è un elenco di numeri interi, valutato pigramente e ricorsivamente. fib è contemporaneamente un "elenco di interi", una "funzione di nessun argomento che restituisce un elenco di numeri interi", un "elenco di funzioni senza argomenti che restituiscono numeri interi" e "una funzione di nessun argomento che restituisce un elenco di funzioni senza argomenti restituire interi ".
Onestamente non importa. Il linguaggio non fa distinzione tra i quattro. La teoria dei tipi non fa distinzione tra i quattro (e innumerevoli altri: una funzione di nessun argomento che restituisce uno di questi è ugualmente valida, come è una funzione di nessun argomento che lo restituisce, all'infinito). Onestamente non fa alcuna differenza se chiami o meno fib una "funzione" o meno.
Ma è ricorsivo.
printf "Oh no, una funzione con argomenti zero, non possiamo averlo!" o morire; –
Un 'fib' in effetti. – Ani
'zipWith' è la funzione ricorsiva e' fib' si riferisce al suo risultato. Non c'è nulla di magico o non ricorsivo su di esso. (Le risposte sottostanti che affermano che "non ha alcuna funzione" sono confuse quanto il tuo collega.) –