Implementazione prendere usando foldr

Questa è la mia versione take utilizzando foldr:Implementazione prendere usando foldr

myTake n list = foldr step [] list 
       where step x y | (length y) < n = x : y 
           | otherwise = y 

main = do print $ myTake 2 [1,2,3,4]

L'uscita non è quello che mi aspetto:

[3,4]

Allora ho provato a eseguire il debug inserendo la lunghezza del y in se stesso e il risultato è stato:

[3,2,1,0]

non capisco perché le lunghezze sono inserite in ordine decrescente. Forse qualcosa di ovvio mi è mancato?

fonte

2013-04-08 badmaash

o in parole, il motivo è che '' y' in fase xy' chiamato da 'foldr' sta ** non ** per *" resto del listino ancora da elaborato "*, ** ma ** per *" risultato dell'elaborazione del resto dell'elenco "*. Quindi la tua funzione dice, * "se la lunghezza del resto della lista elaborato è già' n' o più, non anteporre nulla ad essa, altrimenti anteponi l'elemento corrente "*. –

Se si desidera implementare take utilizzando foldr è necessario simulare l'attraversamento della lista da sinistra a destra. Il punto è che la funzione di piegatura dipenda da un argomento aggiuntivo che codifica la logica che si desidera e non dipende solo dalla coda piegata della lista.

take :: Int -> [a] -> [a] 
take n xs = foldr step (const []) xs n 
    where 
    step x g 0 = [] 
    step x g n = x:g (n-1)

Qui, foldr restituisce una funzione che prende un argomento numerico e attraversa la lista da sinistra a destra prendendo da esso l'importo richiesto. Questo funzionerà anche su liste infinite a causa della pigrizia. Non appena l'argomento extra raggiunge lo zero, foldr si interrompe e restituisce una lista vuota.

fonte

2013-04-08 13:59:08 is7s

Visualization of <code>foldr</code>

foldr si applica la funzione step partire dagli ultimi elementi * **. Cioè,

foldr step [] [1,2,3,4] == 1 `step` (2 `step` (3 `step` (4 `step` []))) 
         == 1 `step` (2 `step` (3 `step` (4:[]))) 
         == 1 `step` (2 `step (3:4:[])) -- length y == 2 here 
         == 1 `step` (3:4:[]) 
         == 3:4:[] 
         == [3, 4]

Le lunghezze sono "inseriti" in ordine decrescente perché : è un anteponendo funzionamento. Le lunghezze più lunghe vengono aggiunte all'inizio della lista.

_{(Immagine tratta da http://en.wikipedia.org/wiki/Fold_%28higher-order_function%29)}

*: Per semplicità, assumiamo ogni operazione è rigorosa, il che è vero in step implementazione del PO.

fonte

2013-04-08 13:20:03 kennytm

"' foldr' applicherà la funzione 'passo' a partire dagli * ultimi elementi *." Questa affermazione è, nel migliore dei casi, molto fuorviante di fronte alla valutazione pigra. Haskell valuta infatti il tuo secondo albero da sinistra a destra, e se la funzione 'step' non è severa sul suo secondo argomento, può interrompere anticipatamente il calcolo. L'esempio più semplice di questo è 'safeHead = foldr (\ x _ -> Just x) Nothing'. –

Dovrei aggiungere che la sequenza dei passaggi di valutazione passa dalle applicazioni di funzione interne a quelle esterne, che è l'ordine * opposto a quello di Haskell. Il 'passo' più esterno viene valutato per primo, quello con' 1' come primo argomento. Se 'step' non ha bisogno del suo secondo argomento, allora il calcolo finisce lì, prima che guardi il resto degli elementi della lista. Se 'passo x _ = solo x', quindi' foldr step Nothing [1,2,3,4] == step 1 (foldr step Nothing [2,3,4]) == Solo 1'. –

@sacundim Ma il 'passo' della domanda è rigoroso nel suo secondo argomento, quindi in questo caso' foldr' non ha altra scelta che lavorare dalla fine della lista in primo piano e valutare il 'passo' più esterno, prima devono essere valutati i 'step' interiori. La risposta trarrebbe vantaggio dal chiarire che si tratta di una situazione speciale, ma la descrizione è corretta per il codice specificato. –

Le altre risposte finora lo rendono troppo complicato, perché sembrano eccessivamente legate alla nozione che lo foldr funzioni "da destra a sinistra". C'è un senso in cui lo fa, ma Haskell è un linguaggio pigro, quindi un calcolo "da destra a sinistra" che usa un passo lazy fold verrà effettivamente eseguito da sinistra a destra, man mano che il risultato viene consumato.

studio di questo codice:

take :: Int -> [a] -> [a] 
take n xs = foldr step [] (tagFrom 1 xs) 
    where step (a, i) rest 
       | i > n  = [] 
       | otherwise = a:rest 

tagFrom :: Enum i => i -> [a] -> [(a, i)] 
tagFrom i xs = zip xs [i..]

fonte

2013-04-08 17:18:57

Implementazione prendere usando foldr

risposta

Problemi correlati