Come implementare zip con foldl (in una lingua ansiosa)

Question

Un programmatore Clojure so che recentemente ho osservato che è possibile implementare molte funzioni di sequenza in termini di Clojure reduce (che è Haskell foldl'), ma purtroppo non c'è modo di implementare (map list xs ys) (che è Haskell zip) con solo reduce.

Ora, ho letto su l'universalità di pieghe, quindi sono abbastanza sicuro che questo non è vero: certamente zip è possibile con foldr, e sarei sorpreso se non fosse possibile con foldl. Ai fini di questa discussione ignoriamo i problemi dell'entusiasmo di foldl rispetto a foldr: immaginiamo di avere memoria illimitata e lavorare solo con sequenze finite.

Così, ho preso il codice Haskell per implement zip with foldr, e tradotti al Clojure, facendo del mio meglio per regolare la differenza tra foldr e foldl:

(defn zip [xs ys] 
    (letfn [(done [_] []) 
      (step [z x] 
      (fn [ys] 
       (if (empty? ys) 
       [] 
       (conj (z (rest ys)) [x (first ys)]))))] 
    ((reduce step done xs) ys))) 
user> (zip [1 2] '[a b c]) ;=> [[1 b] [2 a]] 

E infatti noi otteniamo coppie di elementi da xs e ys sono insieme, ma fuori ordine: il primo elemento di xs è accoppiato con l'ultimo elemento di ys, e così via lungo la linea. Posso vedere la causa del problema: la funzione che produciamo consuma a partire da sinistra, ma la chiusura più esterna (che è chiamata prima) ha chiuso sull'ultimo elemento di xs, quindi non può accoppiarli a destra ordine.

Penso che la soluzione sia quella di costruire in qualche modo le chiusure all'interno, ma non riesco davvero a vedere come farlo. Accetterei volentieri una soluzione sia in Haskell che in Clojure.

Sto sperando in una soluzione del modulo zip = foldl f x, in modo che possa dire che è "solo" una riduzione. Ovviamente posso invertire uno degli elenchi, ma alla fine sembra zip xs ys = foldl f x xs $ reverse ys che non sembra molto soddisfacente o pulito.

Answer 1

In Haskell:

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

zip1 xs ys = -- foldr f (const []) xs ys 
      foldl (\r x a-> r (f x a)) id xs (const []) ys 
    where 
    f x r []  = [] 
    f x r (y:ys) = (x,y) : r ys 

Prelude> ZIP1 [1..9] [100..120]
[(1.100), (2.101), (3102), (4103), (5.104), (6.105), (7.106), (8.107), (9.108)]

Da Clojure piace aggiungendo alla fine della lista, un'altra variante è

zip2 xs ys = foldl f (const []) xs ys 
    where 
    f r x [] = [] 
    f r x ys = let (ys0,y) = (init ys, last ys) -- use some efficient Clojure here 
       in r ys0 ++ [(x,y)] 

Prelude> zip2 [1..9] [100..120]
[(1.112), (2.113), (3114), (4115), (5116), (6117), (7118), (8119), (9120)]

Come si può vedere la fine di linee elenca qui, al posto della parte anteriore.

Answer 2

semplicemente implementare

reverse = foldl (flip (:)) [] 

e applicarlo al secondo elenco.

Answer 3

altro esperto Clojure sottolineato che è più facile farlo in Clojure senza cercare di utilizzare la stessa struttura come soluzione foldr Haskell:

(defn zip [xs ys] 
    (first (reduce 
      (fn [[acc rest :as state] itm] 
      (if rest 
       [(conj acc [itm (first rest)]) 
       (next rest)] 
       state)) 
      [[] (seq ys)] 
      xs))) 

Questa piega poco più di una coppia, il primo dei quali è un risultato sequenza in costruzione, e il secondo è ciò che rimane di ys; xs vengono alimentati in un articolo alla volta tramite la riduzione. In Haskell questo potrebbe sembrare:

zip' :: [a] -> [b] -> [(a,b)] 
zip' xs ys = fst $ foldl f ([], ys) xs 
    where f state@(_, []) _x = state 
     f (acc, (y:ys)) x = ((acC++ [(x, y)]), ys) 

, tranne che, naturalmente, il acC++ [(x, y)] è molto più ragionevole in Clojure che in Haskell, dal momento che è efficiente.

Answer 4

Thesetwo soluzioni sono entrambe nella forma (-> (reduce f init x) something) anziché solo (reduce f init x). Entrambi portano un contenitore con la sequenza accumulata e uno stato extra, quindi estraggono la sequenza dal contenitore. In un caso il contenitore è una chiusura, nell'altro un vettore.

Se si desidera "solo" (reduce f init x) quindi riconoscere che si dispone già di tutto lo stato necessario nella sequenza accumulata stessa - la sua lunghezza.

(defn zip* [xs ys] 
    (let [xs (vec xs) 
     f (fn [a y] 
      (if (contains? xs (count a)) 
       (conj a [(xs (count a)) y]) 
       a))] 
    (reduce f [] ys)))