Implementare zip usando foldr

Question

Sono attualmente al capitolo 4 di Real World Haskell e sto cercando di avvolgere la testa implementazione di foldl in termini di foldr .

(Ecco il loro codice :)

myFoldl :: (a -> b -> a) -> a -> [b] -> a

myFoldl f z xs = foldr step id xs z
    where step x g a = g (f a x)

Ho pensato di provare a implementare zip usando la stessa tecnica, ma non sembra che stia facendo alcun progresso. È anche possibile?

Answer 1

zip2 xs ys = foldr step done xs ys
  where done ys = []
        step x zipsfn []     = []
        step x zipsfn (y:ys) = (x, y) : (zipsfn ys)

Come funziona: (foldr step done xs) restituisce una funzione che consuma ys; quindi scendiamo l'elenco xs creando una composizione nidificata di funzioni che verranno applicate alla parte corrispondente di ys.

Come trovarlo: ho iniziato con l'idea generale (da simili esempi visti prima), ha scritto

zip2 xs ys = foldr step done xs ys

quindi compilato ciascuna delle seguenti righe a turno con ciò che doveva essere per fare in modo che i tipi e i valori vengano visualizzati correttamente È stato più facile considera i casi più semplici prima di quelli più difficili.

La prima riga potrebbe essere scritta più semplicemente come

zip2 = foldr step done

come ha mostrato Mattiast.

Answer 2

La risposta era già stata data qui, ma non una derivazione (illustrativa). Quindi, anche dopo tutti questi anni, forse vale la pena aggiungerlo.

In realtà è abbastanza semplice. In primo luogo,

foldr f z xs 
   = foldr f z [x1,x2,x3,...,xn] = f x1 (foldr f z [x2,x3,...,xn])
   = ... = f x1 (f x2 (f x3 (... (f xn z) ...)))

quindi per eta-espansione,

foldr f z xs ys
   = foldr f z [x1,x2,x3,...,xn] ys = f x1 (foldr f z [x2,x3,...,xn]) ys
   = ... = f x1 (f x2 (f x3 (... (f xn z) ...))) ys

Come è evidente qui, se f non è forzante nel suo secondo argomento , funziona prima su x1 e ys , f x1 r1 ys dove r1 = (f x2 (f x3 (... (f xn z) ...))) = foldr fz [x2, x3, ..., xn] .

Quindi, usando

f x1 r1 [] = []
f x1 r1 (y1:ys1) = (x1,y1) : r1 ys1

organizziamo il passaggio di informazioni da sinistra a destra lungo l'elenco, chiamando r1 con il resto dell'elenco di input ys1 , foldr fz [x2, x3, ..., xn] < code> ys1 = f x2 r2 ys1 , come passaggio successivo. E questo è tutto.

---

Quando ys è più corto di xs (o della stessa lunghezza), il caso [] per f incendi e l'elaborazione si interrompe. Ma se ys è più lungo di xs , la custodia f di [] non si attiva e noi arriva all'ultima f xn z (yn: ysn) ,

f xn z (yn:ysn) = (xn,yn) : z ysn

Poiché abbiamo raggiunto la fine di xs , l'elaborazione zip deve terminare:

z _ = []

E questo significa che dovrebbe essere usata la definizione z = const [] :

zip xs ys = foldr f (const []) xs ys
  where
    f x r []     = []
    f x r (y:ys) = (x,y) : r ys

Dal punto di vista di f , r svolge il ruolo di continuazione del successo , che f chiama quando l'elaborazione deve continuare, dopo aver emesso la coppia (x, y) .

Quindi r è " cosa si fa con più ys quando ci sono più x s " , e z = const [] , la nil -case in foldr , è " cos'è fatto con ys quando non ci sono più x s " . Oppure f può arrestarsi da solo, restituendo [] quando ys è esaurito.

---

Nota come ys viene utilizzato come una sorta di valore accumulato, che viene passato da sinistra a destra lungo l'elenco xs , da una chiamata di f al prossimo (il passo "accumulo" essendo, qui, togliendo un elemento testa da esso).

Naturalmente questo corrisponde alla piega a sinistra, dove un passaggio cumulativo è " applicando la funzione " ;, con z = id che restituisce il valore finale accumulato quando " non ci sono più x s " ;:

foldl f a xs =~ foldr (\x r a-> r (f a x)) id xs a

Allo stesso modo, per elenchi finiti,

foldr f a xs =~ foldl (\r x a-> r (f x a)) id xs a

E poiché la funzione di combinazione decide se continuare o meno, ora è possibile avere una piega a sinistra che può fermarsi presto:

foldlWhile t f a xs = foldr cons id xs a
  where 
    cons x r a = if t x then r (f a x) else a

o un salto a sinistra, foldlQuando t ... , con

    cons x r a = if t x then r (f a x) else r a

ecc.

Answer 3

Ho trovato un modo usando un metodo abbastanza simile al tuo:

myzip = foldr step (const []) :: [a] -> [b] -> [(a,b)]
    where step a f (b:bs) = (a,b):(f bs)
          step a f [] = []

Answer 4

Per gli Haskeller non nativi qui, ho scritto una versione Scheme di questo algoritmo per chiarire cosa sta realmente accadendo:

> (define (zip lista listb)
    ((foldr (lambda (el func)
           (lambda (a)
             (if (empty? a)
                 empty
                 (cons (cons el (first a)) (func (rest a))))))
         (lambda (a) empty)
         lista) listb))
> (zip '(1 2 3 4) '(5 6 7 8))
(list (cons 1 5) (cons 2 6) (cons 3 7) (cons 4 8))

Il foldr genera una funzione che, quando applicata a un elenco, restituirà lo zip dell'elenco piegato con l'elenco dato alla funzione. L'Haskell nasconde il lambda interno a causa della valutazione pigra.

---

Per approfondire ulteriormente:

Inserisci zip in input: '(1 2 3) La funzione foldr viene chiamata con

el->3, func->(lambda (a) empty)

Questo si espande in:

(lambda (a) (cons (cons el (first a)) (func (rest a))))
(lambda (a) (cons (cons 3 (first a)) ((lambda (a) empty) (rest a))))

Se dovessimo restituirlo ora, avremmo una funzione che prende un elenco di un elemento e restituisce la coppia (3 elementi):

> (define f (lambda (a) (cons (cons 3 (first a)) ((lambda (a) empty) (rest a)))))
> (f (list 9))
(list (cons 3 9))

Continuando, foldr ora chiama func con

el->3, func->f ;using f for shorthand
(lambda (a) (cons (cons el (first a)) (func (rest a))))
(lambda (a) (cons (cons 2 (first a)) (f (rest a))))

Questa è una funzione che prende una lista con due elementi, ora, e li comprime con (lista 2 3) :

> (define g (lambda (a) (cons (cons 2 (first a)) (f (rest a)))))
> (g (list 9 1))
(list (cons 2 9) (cons 3 1))

Cosa sta succedendo?

(lambda (a) (cons (cons 2 (first a)) (f (rest a))))

a , in questo caso, è (elenco 9 1)

(cons (cons 2 (first (list 9 1))) (f (rest (list 9 1))))
(cons (cons 2 9) (f (list 1)))

E, come ricorderete, f comprime l'argomento con 3 .

E questo continua ecc ...

Answer 5

Il problema con tutte queste soluzioni per zip è che si ripiegano solo su una lista o sull'altra, il che può essere un problema se entrambi sono "buoni produttori", nel linguaggio di elenco fusione. Ciò di cui hai effettivamente bisogno è una soluzione che si ripiega su entrambi gli elenchi. Fortunatamente, esiste un articolo su questo, chiamato " Coroutining Folds with Hyperfunctions " .

È necessario un tipo ausiliario, un'iperfunzione, che è fondamentalmente una funzione che utilizza un'altra iperfunzione come argomento.

newtype H a b = H { invoke :: H b a -> b }

Le iperfunzioni qui usate agiscono sostanzialmente come uno "stack" di funzioni ordinarie.

push :: (a -> b) -> H a b -> H a b
push f q = H $ \k -> f $ invoke k q

È inoltre necessario un modo per mettere insieme due iperfunzioni, end to end.

(.#.) :: H b c -> H a b -> H a c
f .#. g = H $ \k -> invoke f $ g .#. k

Questo è legato alla push dalla legge:

(push f x) .#. (push g y) = push (f . g) (x .#. y)

Questo risulta essere un operatore associativo, e questa è l'identità:

self :: H a a
self = H $ \k -> invoke k self

Hai anche bisogno di qualcosa che ignori tutto il resto dello " stack " e restituisce un valore specifico:

base :: b -> H a b
base b = H $ const b

E infine, hai bisogno di un modo per ottenere un valore da un'iperfunzione:

run :: H a a -> a
run q = invoke q self

esegui mette insieme tutte le funzioni push ed, insieme, end-to-end, fino a quando non raggiunge una base o esegue un loop all'infinito.

Quindi ora puoi piegare entrambi gli elenchi in iperfunzioni, usando le funzioni che passano le informazioni dall'una all'altra e assemblano il valore finale.

zip xs ys = run $ foldr (\x h -> push (first x) h) (base []) xs .#. foldr (\y h -> push (second y) h) (base Nothing) ys where
  first _ Nothing = []
  first x (Just (y, xys)) = (x, y):xys

  second y xys = Just (y, xys)

Il motivo per cui ripiegare entrambe le liste è importante a causa di qualcosa che GHC chiama lista fusione , di cui si parla in il modulo GHC.Base , ma probabilmente dovrebbe essere molto più noto. Essere un buon produttore di elenchi e utilizzare build con foldr può impedire molta produzione inutile e consumo immediato di elementi di elenco e può esporre ulteriori ottimizzazioni.

Answer 6

Ho cercato di capire da solo questa elegante soluzione, quindi ho cercato di ricavare da solo i tipi e la valutazione. Quindi, dobbiamo scrivere una funzione:

zip xs ys = foldr step done xs ys

Qui dobbiamo derivare step e done , qualunque essi siano. Richiama foldr tipo, istanziato in liste:

foldr :: (a -> state -> state) -> state -> [a] -> state

Tuttavia, la nostra invocazione foldr deve essere istanziata a qualcosa di simile di seguito, perché non dobbiamo accettare uno, ma due argomenti dell'elenco:

foldr :: (a -> ? -> ?) -> ? -> [a] -> [b] -> [(a,b)]

Poiché - > è associazione associativa , ciò equivale a:

foldr :: (a -> ? -> ?) -> ? -> [a] -> ([b] -> [(a,b)])

Il nostro ([b] - > [(a, b)]) corrisponde alla variabile di tipo state nel tipo originale foldr firma, quindi dobbiamo sostituire ogni occorrenza di state con essa:

foldr :: (a -> ([b] -> [(a,b)]) -> ([b] -> [(a,b)]))
      -> ([b] -> [(a,b)])
      -> [a]
      -> ([b] -> [(a,b)])

Questo significa che gli argomenti che passiamo a foldr devono avere i seguenti tipi:

step :: a -> ([b] -> [(a,b)]) -> [b] -> [(a,b)]
done :: [b] -> [(a,b)]
xs :: [a]
ys :: [b]

Ricorda che foldr (+) 0 [1,2,3] si espande in:

1 + (2 + (3 + 0))

Pertanto, se xs = [1,2,3] e ys = [4,5,6,7] , il nostro foldr l'invocazione si espanderebbe in:

1 `step` (2 `step` (3 `step` done)) $ [4,5,6,7]

Ciò significa che il nostro costrutto 1 `step` (2` step` (3 `step` done)) deve creare una funzione ricorsiva che passi attraverso [4,5,6 , 7] e comprimi gli elementi. (Tenere presente che se uno degli elenchi originali è più lungo, i valori in eccesso vengono eliminati). IOW, il nostro costrutto deve avere il tipo [b] - > [(A, b)] .

3 `step` done è il nostro caso base, dove done è un valore iniziale, come 0 in foldr (+ ) 0 [1..3] . Non vogliamo comprimere nulla dopo 3, perché 3 è il valore finale di xs , quindi dobbiamo terminare la ricorsione. Come si interrompe la ricorsione sull'elenco nel caso di base? Si restituisce un elenco vuoto [] . Ma ricorda la firma di tipo done :

done :: [b] -> [(a,b)]

Pertanto non possiamo restituire solo [] , dobbiamo restituire una funzione che ignori tutto ciò che riceve. Pertanto utilizzare const :

done = const [] -- this is equivalent to done = \_ -> []

Ora cominciamo a capire quale step dovrebbe essere. Combina un valore di tipo a con una funzione di tipo [b] - > [(a, b)] e restituisce una funzione di tipo [b] - > [(A, b)] .

In 3 `step` done , sappiamo che il valore del risultato che sarebbe poi andato alla nostra lista zippata deve essere (3,6) (sapendo dall'originale < code> xs e ys ). Pertanto 3 `step` done deve valutare in:

\(y:ys) -> (3,y) : done ys

Ricorda, dobbiamo restituire una funzione, all'interno della quale in qualche modo comprimiamo gli elementi, il codice sopra è ciò che ha senso e i typechecks.

Ora che abbiamo assunto come valutare esattamente step , continuiamo la valutazione. Ecco come appaiono tutti i passaggi di riduzione nella nostra valutazione foldr :

3 `step` done -- becomes
(\(y:ys) -> (3,y) : done ys)
2 `step` (\(y:ys) -> (3,y) : done ys) -- becomes
(\(y:ys) -> (2,y) : (\(y:ys) -> (3,y) : done ys) ys)
1 `step` (\(y:ys) -> (2,y) : (\(y:ys) -> (3,y) : done ys) ys) -- becomes
(\(y:ys) -> (1,y) : (\(y:ys) -> (2,y) : (\(y:ys) -> (3,y) : done ys) ys) ys)

La valutazione ha dato origine a questa implementazione del passaggio (si noti che teniamo conto del fatto che ys si sta esaurendo anticipatamente gli elementi restituendo un elenco vuoto):

step x f = \[] -> []
step x f = \(y:ys) -> (x,y) : f ys

Pertanto, la funzione completa zip è implementata come segue:

zip :: [a] -> [b] -> [(a,b)]
zip xs ys = foldr step done xs ys
  where done = const []
        step x f [] = []
        step x f (y:ys) = (x,y) : f ys

PS: se ti ispiri all'eleganza delle pieghe, leggi Scrivi foldl usando foldr e poi di Graham Hutton un tutorial sull'universalità e l'espressività di fold .

Answer 7

Un approccio semplice:

lZip, rZip :: Foldable t => [b] -> t a -> [(a, b)]

-- implement zip using fold?
lZip xs ys = reverse.fst $ foldl f ([],xs) ys
     where f  (zs, (y:ys)) x = ((x,y):zs, ys)

-- Or;
rZip xs ys = fst $ foldr f ([],reverse xs) ys
     where f x (zs, (y:ys))  = ((x,y):zs, ys)