Sto lottando con Haskell e l'idea di usare la ricorsione per iterare sulle cose.Come tradurre questo frammento in Haskell?
Per esempio, come sarebbe
// this might seem silly but I need to do it
list1 = empty list
list2 = list of numbers
for i from 0 to N // N being a positive integer
for each number in list2
if number == i, add to list1
tradurre nella 'paradigma funzionale'? Qualsiasi guida sarebbe apprezzata.
Andando per gradi:
list2 = list of numbers
Abbiamo prendo questo come un dato, in modo list2 è ancora solo un elenco di numeri.
for i from 0 to N // N being a positive integer
Il modo corretto di fare questo in Haskell è generalmente con una lista. Pigrizia significa che i valori saranno calcolati solo quando usati, quindi attraversare una lista da 0 a N finisce per essere la stessa cosa del loop che hai qui. Quindi, solo il [0..n] farà il trucco; abbiamo solo bisogno di capire cosa fare con esso.
for each number in list2
dato "per ogni" si può dedurre che dovremo attraversare la totalità del list2 qui; cosa ne facciamo, non lo sappiamo ancora.
if number == i, add to list1
Stiamo costruendo list1 come andiamo, così idealmente vogliamo che per essere il risultato finale dell'espressione. Ciò significa anche che in ogni fase ricorsiva, vogliamo che il risultato sia lo list1 che abbiamo "finora". Per fare ciò, dovremo assicurarci di passare il risultato di ogni passaggio mentre procediamo.
Quindi, scendendo alla carne di esso:
La funzione filter trova tutti gli elementi di una lista che contengono una predicato; useremo filter (== i) list2 qui per trovare quello che cerchiamo, quindi aggiungiamo quello al risultato del passaggio precedente. Quindi ogni passaggio sarà simile a questo:
step :: (Num a) => [a] -> a -> [a]
step list1 i = list1 ++ filter (== i) list2
Che gestisce l'anello interno. Tornando indietro, è necessario eseguire questo per ogni valore , con il valore list1 passato a ogni passaggio.Questo è esattamente ciò che si piegano funzioni sono per, e in questo caso step è esattamente quello che ci serve per una piega a sinistra:
list2 :: (Num a) => [a]
list2 = -- whatever goes here...
step :: (Num a) => [a] -> a -> [a]
step list1 i = list1 ++ filter (== i) list2
list1 :: (Num a) => a -> [a]
list1 n = foldl step [] [0..n]
Se vi state chiedendo dove la ricorsione è, sia filter e foldl che stanno facendo per noi . Come regola generale, di solito è meglio evitare la ricorsione diretta quando ci sono funzioni di livello superiore per farlo per te.
Detto questo, l'algoritmo qui è stupido in diversi modi, ma non ho voglia di entrare in quella, perché sembrava che sarebbe distrarre dalla tua domanda effettiva più che sarebbe d'aiuto.
Ci dispiace, ma non posso fare a meno di usare un algoritmo migliore ...
let goodNumber n = (0 <= n && n < N)
let list1 = sort (filter goodNumber list2)
Edit: Col senno di poi si tratta di un po 'di eccessivo, dal momento che l'OP stava cercando di implementare un ordinamento algo in primo luogo.
let list1 = sort [a | a<-list2, a>=0, a<=N]
a<-list2 preleva ogni numero di lista2 a>=0, a<=N controllo se il numero scelto soddisfa tutte queste condizioni se sono soddisfatte le condizioni, una è messo in un nuovo elenco Una volta che tutti gli elementi di lista2 sono stati così controllati e Inserito in una nuova lista, facciamo una specie su questo L'elenco risultante è assegnato alla lista1
Perché non usare 'concatMap' invece di piegare su una fase di concatenazione esplicita? – bdonlan
Nota che in questo caso puoi utilizzare la comprensione delle liste: [numero | i <- [1..N], numero <-list2, i == numero] che è la traduzione diretta del tuo pseudo-codice. – ysdx
Grazie per l'ottima risposta. Mi rendo conto che il frammento che ho postato è bizzarro ... Ho drasticamente rasato ogni significato da esso. Fa parte di un esercizio di classificazione dei radix che sto facendo. –