首页 文章

使用foldr实现zip

提问于
浏览 次
19

我试图绕着implementing foldl in terms of foldr缠身 .

（这是他们的代码:)

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)

我以为我会尝试使用相同的技术实现 zip ，但我似乎没有取得任何进展 . 它甚至可能吗？

haskell functional-programming fold combinators

7 回答

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

    这是如何工作的：（foldr step done xs）返回一个消耗ys的函数;所以我们沿着xs列表构建一个嵌套的函数组合，每个函数将应用于ys的相应部分 .

    如何提出它：我从一般的想法（从之前看到的类似例子）开始，写道

    zip2 xs ys = foldr step done xs ys

    然后依次填写以下每一行，以使类型和值正确出现 . 在较难的案例之前，最容易考虑最简单的案例 .

    第一行可以更简单地写成

    zip2 = foldr step done

    正如mattiast所示 .

    回复于
  • 5

    答案已经在这里给出，但不是（说明性的）推导 . 所以即使经过这么多年，也许值得添加它 .

    它实际上非常简单 . 第一，

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

    因此通过eta扩展，

    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

    这里显而易见的是，如果 f 在其第二个参数中是非强制的，则它首先在 x1 和 ys ， f x1 r1 ys r1 = (f x2 (f x3 (... (f xn z) ...))) = foldr f z [x2,x3,...,xn] 上工作 .

    所以，使用

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

    我们安排在列表中从左向右传递信息，通过调用 r1 与输入列表的其余部分 ys1 ， foldr f z [x2,x3,...,xn] ys1 = f x2 r2 ys1 ，作为下一步 . 就是这样 .

    当 ys 短于 xs （或相同长度）时， f 的 [] 情况会触发，处理将停止 . 但是如果 ys 长于 xs 那么 f 的 [] 案例赢得了't fire and we' ll到达最终的 f xn z (yn:ysn) 应用程序，

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

    由于我们已经到了 xs 的末尾， zip 处理必须停止：

    z _ = []

    这意味着应该使用 z = const [] 定义：

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

    从 f 的角度来看， r 扮演成功延续的角色，在发出成对 (x,y) 之后， f 在处理继续时调用 .

    所以 r 是“当有更多 x s时更多 ys 做了什么”，而 z = const [] ， foldr 中的 nil -case是“当没有 x s时 ys 做了什么” . 或者 f 可以自行停止，当 ys 用尽时返回 [] .

    注意 ys 如何用作一种累积值，它沿着列表 xs 从左向右传递，从 f 的一次调用到下一次（"accumulating"步骤，这里，从中剥离头元素） .

    Naturally这对应于左侧折叠，其中累积步骤为"applying the function"， z = id 在“没有更多 x s”时返回最终累计值：

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

    同样，对于有限列表，

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

    由于组合功能决定是否继续，现在可以让左侧折叠可以提前停止：

    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

    或者跳过左折， foldlWhen t ... ，带

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

    等等

    回复于
  • 16

    我发现了一种使用与你的方法非常相似的方法：

    myzip = foldr step (const []) :: [a] -> [b] -> [(a,b)]
    where step a f (b:bs) = (a,b):(f bs)
          step a f [] = []
    回复于
  • 5

    对于非原生的Haskellers，我已经编写了这个算法的Scheme版本，以便更清楚实际发生的事情：

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

    foldr 产生一个函数，当应用于列表时，它将返回折叠列表的zip，其中包含给函数的列表 . 由于懒惰的评估，Haskell隐藏了内部 lambda .

    进一步分解：

    在输入上输入zip：'（1 2 3）使用调用foldr func

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

    这扩展到：

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

    如果我们现在要返回这个，我们有一个函数，它接受一个元素的列表并返回该对（3个元素）：

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

    继续，foldr现在调用func

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

    这是一个func，它带有一个带有两个元素的列表，现在，并用 (list 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))

    发生了什么？

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

    a ，在这种情况下，是 (list 9 1)

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

    并且，如您所知， f 将其参数与 3 拉开 .

    这继续等......

    回复于
  • 0

    zip 的所有这些解决方案的问题在于它们只折叠一个列表或另一个列表，如果它们都是"good producers"，则在列表融合的说法中可能会出现问题 . 你到底是什么需求是折叠两个列表的解决方案 . 幸运的是，有一篇文章正是如此，称为"Coroutining Folds with Hyperfunctions" .

    你需要一个辅助类型，一个超函数，它基本上是一个以另一个超函数作为参数的函数 .

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

    这里使用的超级函数基本上就像普通函数的“堆栈” .

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

    您还需要一种方法将两个超级功能放在一起，端到端 .

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

    这与法律的 push 有关：

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

    结果是一个关联运算符，这是标识：

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

    您还需要忽略“堆栈”上其他所有内容并返回特定值的内容：

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

    最后，您需要一种从超级函数中获取值的方法：

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

    run 将所有 push ed函数串起来，端到端，直到它命中 base 或无限循环 .

    因此，现在您可以将两个列表折叠为超级函数，使用将信息从一个传递到另一个的函数，并汇总最终值 .

    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)

    折叠两个列表之所以重要的原因是GHC确实称之为列表融合，这在_3045713中被讨论过，但可能应该更为人所知 . 作为一个好的列表生成者并使用 build 与 foldr 可以防止大量无用的 生产环境 和立即使用列表元素，并且可以暴露进一步的优化 .

    回复于
  • 9

    我自己试着理解这个优雅的解决方案，所以我试着自己推导出类型和评估 . 所以，我们需要编写一个函数：

    zip xs ys = foldr step done xs ys

    在这里，我们需要派生 step 和 done ，无论它们是什么 . 回想foldr的类型，实例化为列表：

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

    但是，我们的 foldr 调用必须实例化为类似下面的内容，因为我们必须接受不是一个，而是两个列表参数：

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

    因为 -> 是right-associative，这相当于：

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

    我们的 ([b] -> [(a,b)]) 对应于原始 foldr 类型签名中的 state 类型变量，因此我们必须用它替换 state 的每次出现：

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

    这意味着我们传递给 foldr 的参数必须具有以下类型：

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

    回想一下 foldr (+) 0 [1,2,3] 扩展为：

    1 + (2 + (3 + 0))

    因此，如果 xs = [1,2,3] 和 ys = [4,5,6,7] ，我们的 foldr 调用将扩展为：

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

    这意味着我们的 1step(2step(3stepdone)) 构造必须创建一个递归函数，该函数将通过 [4,5,6,7] 并压缩元素 . （请记住，如果其中一个原始列表较长，则会丢弃多余的值） . IOW，我们的构造必须具有 [b] -> [(a,b)] 类型 .

    3stepdone 是我们的基本情况，其中 done 是初始值，如 foldr (+) 0 [1..3] 中的 0 . 我们不想在3之后压缩任何东西，因为3是 xs 的最终值，所以我们必须终止递归 . 如何在基本情况下终止递归列表？您返回空列表 [] . 但回想一下 done 型签名：

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

    因此我们不能只返回 [] ，我们必须返回一个忽略它接收的函数 . 因此请使用const：

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

    现在让我们开始弄清楚_3045753应该是什么 . 它将 a 类型的值与 [b] -> [(a,b)] 类型的函数组合在一起，并返回 [b] -> [(a,b)] 类型的函数 .

    在 3stepdone 中，我们知道稍后将转到我们的压缩列表的结果值必须是 (3,6) （从原始 xs 和 ys 了解） . 因此 3stepdone 必须评估为：

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

    记住，我们必须返回一个函数，在其中我们以某种方式压缩元素，上面的代码是有意义的和类型检查 .

    现在我们假设 step 应该如何评估，让's continue the evaluation. Here'来看看 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)

    评估产生了这个步骤的实现（请注意，我们通过返回一个空列表来解释 ys 早期耗尽元素）：

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

    因此，完整函数 zip 实现如下：

    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

    P.S . ：如果你受到褶皱优雅的启发，请阅读Writing foldl using foldr，然后阅读Graham Hutton的A tutorial on the universality and expressiveness of fold .

    回复于
  • 10

    一个简单的方法：

    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)
    回复于

相关问题