首页 文章

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

提问于
浏览 次
9

我最近认识的一个Clojure程序员说它是's possible to implement lots of sequence functions in terms of Clojure' s reduce （这是Haskell的 foldl' ），但令人遗憾的是，只有 reduce 才能实现 (map list xs ys) （这是Haskell的 zip ） .

现在，我很确定这不是真的：当然 zip 可能 foldr ，'d be surprised if it weren'可能 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 似乎不太令人满意或干净 .

haskell clojure functional-programming fold

4 回答

  • 2

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

    (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中更合理，因为它是有效的 .

    回复于
  • 2

    These two解决方案的形式均为 (-> (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)))
    回复于
  • 3

    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

    前奏曲> zip1 [1..9] [100..120] [（1,100），（2,101），（3,102），（4,103），（5,104），（6,105），（7,106），（8,107），（ 9108）]

    由于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），（ 9120）]

    正如您所看到的那样，列表末尾排列在此处，而不是前面 .

    回复于
  • 0

    简单实施

    reverse = foldl (flip (:)) []

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

    回复于

相关问题