如何用foldl实现zip(用急切的语言)

Question

我最近认识的一个Clojure程序员说过用Clojure reduce(就是Haskell的foldl')来实现很多序列函数是可能的,但遗憾的是没有办法实现(map list xs ys)(就是Haskell的zip)reduce.

现在,我已经读到了折叠的普遍性,所以我很确定这不是真的:当然zip是可能的foldr,如果不可能,我会感到惊讶foldl.出于讨论的目的,我们忽略了与之foldl相比的渴望问题foldr:想象我们拥有无限的记忆并且只能使用有限的序列.

所以,我使用Haskell代码用foldr实现zip,并将其翻译成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,这样我就可以说它只是"减少".当然我可以反转其中一个列表,但最后它zip xs ys = foldl f x xs $ reverse ys看起来似乎看起来不太令人满意或干净.

Answer 1

在哈斯克尔：

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

前奏> 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)]

前奏> zip2 [1..9] [100..120]
[(1,112),(2,113),(3,114),(4,115),(5,116),(6,117),(7,118),(8,119),(9,120 )]

正如您所看到的，列表的末尾排列在这里，而不是前面。