如何用 foldl 实现 zip（用一种急切的语言）

Question

我认识的一位 Clojure 程序员最近评论说，根据 Clojure 的 reduce（即 Haskell 的 foldl'）可以实现很多序列函数，但令人遗憾的是没有办法只用 reduce.

来实现 (map list xs ys)（这是 Haskell 的 zip）

现在，我已经了解了折叠的普遍性，所以我很确定这不是真的：当然 zip 可以用 foldr，我会感到惊讶如果 foldl 不可能。出于本次讨论的目的，我们忽略了 foldl 与 foldr 相比的急切问题：假设我们有无限的内存并且只处理有限的序列。

所以，我把Haskell代码带到了implement zip with foldr，并将其翻译成Clojure，尽最大努力调整foldr和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]]

事实上，我们确实从 xs 和 ys 中得到成对的元素对，但顺序是乱序的：xs 的第一个元素与 ys 的最后一个元素配对，依此类推。我可以看出问题的原因：我们生成的函数从左边开始消耗 ys，但是最外层的闭包（首先调用）已经关闭了 xs 的最后一个元素，所以它不能在右边将它们配对订单。

我认为解决方法是以某种方式从内到外构建闭包，但我真的不知道该怎么做。我很乐意接受 Haskell 或 Clojure 中的解决方案。

我希望有一个 zip = foldl f x 形式的解决方案，这样我就可以说它是 "just" 一个减少。当然，我可以反转其中一个列表，但它最终看起来像 zip xs ys = foldl f x xs $ reverse ys，这看起来不太令人满意或干净。

Answer 1

简单实现

reverse = foldl (flip (:)) []

并将其应用于第二个列表。

Answer 2

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),(3,102),(4,103),(5,104),(6,105),(7,106),(8,107),(9,108)]

由于 Clojure 喜欢在列表末尾追加，另一种变体是

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),(3,114),(4,115),(5,116),(6,117),(7,118),(8,119),(9,120)]

如您所见，列表的 end 排在此处，而不是前面。

Answer 3

另一位 Clojure 专家指出，在 Clojure 中执行此操作更容易，而无需尝试使用与 Haskell 的 foldr 解决方案相同的结构：

(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)))

这只是折叠了一对，第一个是正在构建的结果序列，第二个是 ys 的剩余部分； xs 正在通过 reduce 一次输入一个项目。在 Haskell 这看起来像：

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)

当然 acc ++ [(x, y)] 在 Clojure 中比在 Haskell 中更合理，因为它是高效的。

Answer 4

解决方案都是 (-> (reduce f init x) something) 形式，而不仅仅是 (reduce f init x)。两者都携带一个包含累积序列和一些额外状态的容器，然后从容器中提取序列。在一种情况下，容器是一个闭包，在另一种情况下，容器是一个向量。

如果你想要 "just" (reduce f init x) 然后认识到你已经在累积序列本身中拥有你需要的所有状态 - 它的长度。

(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)))

如何用 foldl 实现 zip（用一种急切的语言）

How to implement zip with foldl (in an eager language)

haskell

clojure

functional-programming

fold