Come implementare l'eliminazione con foldr in Haskell

Question

Ho studiato le pieghe negli ultimi giorni. Posso implementare semplici funzioni con loro, come length, concat e filter. Quello a cui sono bloccato sta cercando di implementare con le funzioni foldr come delete, take e find. Li ho implementati con la ricorsione esplicita ma non mi sembra ovvio come convertire questi tipi di funzioni in pieghe giuste.

Ho studiato i tutorial di Graham Hutton e Bernie Pope. Imitando lo dropWhile di Hutton, sono stato in grado di implementare delete con foldr ma non riesce su elenchi infiniti.

Dalla lettura Implement insert in haskell with foldr, How can this function be written using foldr? e Implementing take using foldr, sembrerebbe che ho bisogno di usare foldr per generare una funzione che poi fa qualcosa. Ma non capisco davvero queste soluzioni e non ho idea di come implementare, ad esempio, delete in questo modo.

Potrebbe spiegarmi una strategia generale per l'implementazione con le versioni lazy di foldr come quelle che ho menzionato. Forse potresti anche implementare delete come esempio poiché probabilmente è uno dei più facili.

Sto cercando una spiegazione dettagliata che un principiante possa capire. Non mi interessano solo le soluzioni, voglio sviluppare una comprensione in modo da poter trovare soluzioni a problemi simili.

Grazie.

Modifica: Al momento della scrittura c'è una risposta utile ma non è proprio quello che stavo cercando. Sono più interessato a un approccio che usa foldr per generare una funzione, che poi fa qualcosa. I link nella mia domanda hanno esempi di questo. Non capisco bene queste soluzioni, quindi mi piacerebbe avere maggiori informazioni su questo approccio.

Answer 1

delete è una ricerca modale. Ha due diverse modalità operative: se è già stato trovato o meno il risultato. È possibile utilizzare foldr per creare una funzione che passa lo stato lungo la linea quando viene controllato ciascun elemento. Quindi, nel caso di delete, lo stato può essere un semplice Bool. Non è esattamente il miglior tipo, ma lo farà.

Una volta identificato il tipo di stato, è possibile iniziare a lavorare sulla costruzione foldr. Ho intenzione di camminare attraverso a capire come ho fatto. Abiliterò ScopedTypeVariables solo così posso annotare meglio il tipo di sottoespressioni. Uno conosci il tipo di stato, sai che vuoi foldr per generare una funzione prendendo un valore di quel tipo e restituendo un valore del tipo finale desiderato. Questo è sufficiente per iniziare a delineare le cose.

{-# LANGUAGE ScopedTypeVariables #-} 

delete :: forall a. Eq a => a -> [a] -> [a] 
delete a xs = foldr f undefined xs undefined 
    where 
    f :: a -> (Bool -> [a]) -> (Bool -> [a]) 
    f x g = undefined 

È un inizio. Il significato esatto di g è un po 'complicato qui. In realtà è la funzione per elaborare il resto dell'elenco. È accurato guardarlo come una continuazione, infatti. Rappresenta in modo assoluto l'esecuzione del resto della piegatura, con il tuo stato che scegli di passare. Detto questo, è il momento di capire cosa mettere in alcuni di questi posti undefined.

{-# LANGUAGE ScopedTypeVariables #-} 

delete :: forall a. Eq a => a -> [a] -> [a] 
delete a xs = foldr f undefined xs undefined 
    where 
    f :: a -> (Bool -> [a]) -> (Bool -> [a]) 
    f x g found | x == a && not found = g True 
       | otherwise   = x : g found 

Questo sembra relativamente semplice. Se l'elemento corrente è quello cercato, e non è stato ancora trovato, non inviarlo e continuare con lo stato impostato su True, a indicare che è stato trovato. otherwise, emette il valore corrente e continua con lo stato corrente.Questo lascia solo il resto degli argomenti a foldr. L'ultimo è lo stato iniziale. L'altra è la funzione di stato per una lista vuota. Ok, anche quelli non sono male.

{-# LANGUAGE ScopedTypeVariables #-} 

delete :: forall a. Eq a => a -> [a] -> [a] 
delete a xs = foldr f (const []) xs False 
    where 
    f :: a -> (Bool -> [a]) -> (Bool -> [a]) 
    f x g found | x == a && not found = g True 
       | otherwise   = x : g found 

Indipendentemente dallo stato, produrre una lista vuota quando si incontra una lista vuota. E lo stato iniziale è che l'elemento cercato non è stato ancora trovato.

Questa tecnica è applicabile anche in altri casi. Ad esempio, può essere scritto come foldr in questo modo. Se si guarda foldl come una funzione che trasforma ripetutamente un accumulatore iniziale, è possibile indovinare che è la funzione prodotta - come trasformare il valore iniziale.

{-# LANGUAGE ScopedTypeVariables #-} 

foldl :: forall a b. (a -> b -> a) -> a -> [b] -> a 
foldl f z xs = foldr g id xs z 
    where 
    g :: b -> (a -> a) -> (a -> a) 
    g x cont acc = undefined 

I casi di base non sono troppo difficile da trovare quando il problema viene definito come manipolare l'accumulatore iniziale, di nome z lì. L'elenco vuoto è la trasformazione dell'identità, id e il valore trasmesso alla funzione creata è z.

L'implementazione di g è più complessa. Non si può fare ciecamente sui tipi, perché ci sono due diverse implementazioni che usano tutti i valori attesi e il controllo del tipo. Questo è un caso in cui i tipi non sono sufficienti e devi considerare il significato delle funzioni disponibili.

Iniziamo con un inventario dei valori che sembrano come dovrebbero essere utilizzati e il loro tipo. Le cose che sembrano debbano essere utilizzate nel corpo di g sono f :: a -> b -> a, x :: b, cont :: (a -> a) e acc :: a. f prenderà ovviamente il x come secondo argomento, ma c'è una domanda sul posto appropriato da usare cont. Per capire dove va, ricorda che rappresenta la funzione di trasformazione restituita elaborando il resto dell'elenco e che foldl elabora l'elemento corrente e quindi passa il risultato di tale elaborazione al resto dell'elenco.

{-# LANGUAGE ScopedTypeVariables #-} 

foldl :: forall a b. (a -> b -> a) -> a -> [b] -> a 
foldl f z xs = foldr g id xs z 
    where 
    g :: b -> (a -> a) -> (a -> a) 
    g x cont acc = cont $ f acc x 

Questo suggerisce anche che foldl' può essere scritto in questo modo con un solo piccolo cambiamento:

{-# LANGUAGE ScopedTypeVariables #-} 

foldl' :: forall a b. (a -> b -> a) -> a -> [b] -> a 
foldl' f z xs = foldr g id xs z 
    where 
    g :: b -> (a -> a) -> (a -> a) 
    g x cont acc = cont $! f acc x 

La differenza è che ($!) è usato per suggerire la valutazione di f acc x prima che sia passato a cont. (Dico "suggerire", perché ci sono alcuni casi limite in cui ($!) non forza la valutazione anche per quanto riguarda WHNF.)

Answer 2

delete non funziona nell'intero elenco in modo uniforme. La struttura del calcolo non considera solo l'intero elenco un elemento alla volta. Differisce dopo aver colpito l'elemento che sta cercando. Questo ti dice che non può essere implementato come solo a foldr. Dovrà esserci una sorta di post-elaborazione coinvolta.

Quando ciò accade, lo schema generale è che si costruisce una coppia di valori e basta prendere uno di essi al completamento dello foldr. Questo è probabilmente quello che hai fatto quando hai imitato lo dropWhile di Hutton, anche se non sono sicuro dal momento che non hai incluso il codice. Qualcosa come questo?

delete :: Eq a => a -> [a] -> [a] 
delete a = snd . foldr (\x (xs1, xs2) -> if x == a then (x:xs1, xs1) else (x:xs1, x:xs2)) ([], []) 

L'idea principale è che xs1 sta andando sempre essere la piena coda della lista, e xs2 è il risultato della delete sopra la coda della lista. Dato che vuoi rimuovere solo il primo elemento che corrisponde, non vuoi usare il risultato di delete sulla coda quando fai corrispondere il valore che stai cercando, vuoi solo restituire il resto della lista invariato - che fortunatamente è quello che sarà sempre in xs1.

E sì, questo non funziona su liste infinite - ma solo per una ragione molto specifica. Il lambda è troppo severo.foldr funziona solo su liste infinite quando la funzione che viene fornita non sempre impone la valutazione del suo secondo argomento, e che lambda forza sempre la valutazione del suo secondo argomento nella corrispondenza del modello sulla coppia. Passare a un modello irrefutabile corrisponde a correzioni che, consentendo a lambda di produrre un costruttore prima di esaminare il suo secondo argomento.

delete :: Eq a => a -> [a] -> [a] 
delete a = snd . foldr (\x ~(xs1, xs2) -> if x == a then (x:xs1, xs1) else (x:xs1, x:xs2)) ([], []) 

Questo non è l'unico modo per ottenere questo risultato. Usare un let-binding o fst e snd come accessor sulla tupla farebbe anche il lavoro. Ma è il cambiamento con il più piccolo diff.

Il take-away più importante qui è quello di stare molto attenti nel gestire il secondo argomento della funzione di riduzione che si passa a foldr. Si desidera posticipare l'esame del secondo argomento ogni volta che è possibile, in modo che lo foldr possa scorrere pigramente nel maggior numero possibile di casi.

Se si guarda quel lambda, si vede che il ramo preso viene scelto prima di fare qualsiasi cosa con il secondo argomento della funzione di riduzione. Inoltre, vedrete che la maggior parte delle volte la funzione di riduzione produce un costruttore di liste in entrambe le metà della tupla del risultato prima che sia necessario valutare il secondo argomento. Dal momento che questi costruttori di elenchi sono quelli che escono da delete, sono ciò che importa per lo streaming, a condizione che non si impedisca alla coppia di intralciare il problema. E rendere inconfutabile il pattern-match sulla coppia è ciò che lo tiene lontano.

Come esempio bonus delle proprietà di streaming di foldr, considero il mio esempio preferito:

dropWhileEnd :: (a -> Bool) -> [a] -> [a] 
dropWhileEnd p = foldr (\x xs -> if p x && null xs then [] else x:xs) [] 

Si flussi - quanto più si può. Se capisci esattamente quando e perché funziona e non lo streaming, capirai praticamente ogni dettaglio della struttura di streaming di foldr.

Answer 3

Ecco un semplice eliminazione, implementato con foldr:

delete :: (Eq a) => a -> [a] -> [a] 
delete a xs = foldr (\x xs -> if x == a then (xs) else (x:xs)) [] xs