使用foldr编写foldl

7 回答

• 5

  一些解释是有序的！

  什么是id函数？有什么作用？我们为什么要在这里需要它？

  id 是identity function， id x = x ，在使用function composition， (.) 构建函数链时用作等效零 . 你可以找到defined in the Prelude .

  在上面的例子中，id函数是lambda函数中的累加器？

  累加器是通过重复功能应用构建的功能 . 没有明确的lambda，因为我们将累加器命名为 step . 如果你愿意，可以用lambda编写它：

  foldl f a bs = foldr (\b g x -> g (f x b)) id bs a
  

  或者作为Graham Hutton would write：

  5.1 foldl运算符现在让我们从suml示例中进行概括，并考虑标准运算符foldl，它使用函数f组合值，并以值v作为起始值，按从左到右的顺序处理列表的元素：foldl ::（β→α→β）→β→（[α]→β）
  foldl f v [] = v
  foldl f v（x：xs）= foldl f（f v x）xs
  使用此运算符，可以简单地通过suml = foldl（）重新定义suml . 许多其他函数可以使用foldl以简单的方式定义 . 例如，标准函数reverse可以使用foldl重新定义如下：reverse :: [α]→[α]
  reverse = foldl（λxsx→x：xs）[]
  这个定义比使用fold的原始定义更有效，因为它避免了对列表使用低效的append operator（） . 上一节中函数suml的计算的简单推广显示了如何根据fold重新定义函数foldl：foldl f v xs = fold（λxg→（λa→g（f a x）））id xs v
  相反，由于foldl在其列表参数的尾部是严格的但折叠不是这样的事实，因此不可能在foldl方面重新定义折叠 . 关于fold和foldl有许多有用的“对偶定理”，还有一些指导决定哪个算子最适合特定应用的指南（Bird，1998） .

  foldr的原型是foldr ::（a - > b - > b） - > b - > [a] - > b

  一个Haskell程序员会说 foldr 的 type 是 (a -> b -> b) -> b -> [a] -> b .

  而第一个参数是一个需要两个参数的函数，但myFoldl 's implementation uses 3 parameters, I'中的step函数完全混淆了

  这令人困惑和神奇！我们玩一个技巧并用一个函数替换累加器，然后将函数应用于初始值以产生结果 .

  Graham Hutton解释了在上面的文章中将 foldl 变为 foldr 的技巧 . 我们首先写下 foldl 的递归定义：

  foldl :: (a -> b -> a) -> a -> [b] -> a
  foldl f v []       = v
  foldl f v (x : xs) = foldl f (f v x) xs
  

  然后通过 f 上的静态参数转换重构它：

  foldl :: (a -> b -> a) -> a -> [b] -> a    
  foldl f v xs = g xs v
      where
          g []     v = v
          g (x:xs) v = g xs (f v x)
  

  现在让我们重写 g 以便向内浮动 v ：

  foldl f v xs = g xs v
      where
          g []     = \v -> v
          g (x:xs) = \v -> g xs (f v x)
  

  这与将 g 视为一个参数的函数相同，它返回一个函数：

  foldl f v xs = g xs v
      where
          g []     = id
          g (x:xs) = \v -> g xs (f v x)
  

  现在我们有 g ，一个递归遍历列表的函数，应用一些函数 f . 最终值是身份函数，每个步骤也会产生一个函数 .

  但是，我们在列表上已经有了一个非常类似的递归函数， foldr ！

  2折叠运算符折叠运算符起源于递归理论（Kleene，1952），而折叠作为编程语言的核心概念可以追溯到APL的简化运算符（Iverson，1962），后来又FP的插入算子（Backus，1978） . 在Haskell中，列表的折叠运算符可以定义如下：fold ::（α→β→β）→β→（[α]→β）
  fold f v [] = v
  fold f v（x：xs）= f x（fold f v xs）
  也就是说，给定类型α→β→β的函数f和类型β的值v，函数fold fv处理类型[α]的列表，通过替换nil构造函数[]来给出类型β的值 . 值v的列表末尾，以及函数f列表中的每个cons构造函数（:) . 以这种方式，fold运算符封装了一个简单的递归模式，用于处理列表，其中列表的两个构造函数简单地被其他值和函数替换 . 列表上的许多熟悉函数都使用fold进行简单定义 .

  这看起来像是一个非常类似于我们的 g 函数的递归方案 . 现在的诀窍是：使用手边所有可用的魔法（又名Bird，Meertens和Malcolm），我们应用一个特殊规则 universal property of fold ，它是处理列表的函数 g 的两个定义之间的等价，声明如下：

  g [] = v
  g（x：xs）= f x（g xs）
  如果和只有当g = fold f v时

  因此，折叠的普遍属性表明：

  g = foldr k v
  

  对于某些 k 和 v ， g 必须等效于两个等式：

  g []     = v
      g (x:xs) = k x (g xs)
  

  从我们之前的foldl设计中，我们知道 v == id . 但是对于第二个等式，我们需要 calculate k 的定义：

  g (x:xs)         = k x (g xs)        
  <=> g (x:xs) v       = k x (g xs) v      -- accumulator of functions
  <=> g xs (f v x)     = k x (g xs) v      -- definition of foldl
  <=  g' (f v x)       = k x g' v          -- generalize (g xs) to g'
  <=> k = \x g' -> (\a -> g' (f v x))      -- expand k. recursion captured in g'
  

  其中，用我们计算出的 k 和 v 的定义代替foldl的定义为：

  foldl :: (a -> b -> a) -> a -> [b] -> a    
  foldl f v xs =
      foldr
          (\x g -> (\a -> g (f v x)))
          id
          xs
          v
  

  递归 g 被foldr组合子替换，累加器变为通过列表的每个元素的 f 组合链构建的函数，以相反的顺序（因此我们向左折叠而不是向右折叠） .

  这肯定有点先进，所以要深入理解这种转换，折叠的通用属性，使转换成为可能，我推荐Hutton的教程，链接如下 .

  ---

  参考

  • Haskell Wiki: Foldl as foldr

  • A tutorial on the universality and expressiveness of fold，Graham Hutton，J . Functional Programming 9（4）：355 - 343，1999年7月 .

  • Malcolm, G. Algebraic data types and program transformation.，博士论文，格罗宁根大学 .

  回复于 2024-05-04T16:50:02+08:00
• 4

  考虑 foldr 的类型：

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

  而 step 的类型类似于 b -> (a -> a) -> a -> a . 由于步骤已传递给 foldr ，我们可以得出结论，在这种情况下，折叠具有类似 (b -> (a -> a) -> (a -> a)) -> (a -> a) -> [b] -> (a -> a) 的类型 .

  不要被不同签名中 a 的不同含义所混淆;它只是一个类型变量 . 另外，请记住，函数箭头是右关联的，因此 a -> b -> c 与 a -> (b -> c) 相同 .

  所以，是的， foldr 的累加器值是 a -> a 类型的函数，初始值是 id . 这是有道理的，因为 id 是一个函数，与你在列表中添加所有值时以零作为初始值开始时的原因相同 .

  至于 step 有三个参数，请尝试重写它：

  step :: b -> (a -> a) -> (a -> a)
  step x g = \a -> g (f a x)
  

  这是否更容易看到's going on? It takes an extra parameter because it'返回一个函数，并且它的两种编写方式是等效的 . 另请注意 foldr 之后的额外参数： (foldr step id xs) z . 括号中的部分是折叠本身，它返回一个函数，然后将其应用于 z .

  回复于 2024-05-04T16:50:02+08:00
• 88

  （快速浏览我的答案[1]，[2]，[3]，[4]以确保你理解Haskell的语法，高阶函数，currying，函数组合，$运算符，中缀/前缀运算符，section和lambdas ）

  折叠的通用属性

  fold只是某种递归的编纂 . 普遍性属性简单地说明，如果你的递归符合某种形式，它可以根据一些正式规则转换成折叠 . 相反，每个折叠都可以转换为这种递归 . 再一次，一些递归可以转换为折叠，给出完全相同的答案，并且一些递归不能，并且有一个确切的过程来做到这一点 .

  基本上，如果你的递归函数在列表上工作，就像在左边一样，你可以将它转换为右边的一个折叠，用 f 和 v 代替它实际上是什么 .

  g []     = v              ⇒
  g (x:xs) = f x (g xs)     ⇒     g = foldr f v
  

  例如：

  sum []     = 0   {- recursion becomes fold -}
  sum (x:xs) = x + sum xs   ⇒     sum = foldr 0 (+)
  

  这里 v = 0 和 sum (x:xs) = x + sum xs 相当于 sum (x:xs) = (+) x (sum xs) ，因此 f = (+) . 还有2个例子

  product []     = 1
  product (x:xs) = x * product xs  ⇒  product = foldr 1 (*)
  
  length []     = 0
  length (x:xs) = 1 + length xs    ⇒  length = foldr (\_ a -> 1 + a) 0
  

  练习：递归地实现map，filter，reverse，concat和concatMap，就像左边的上面的函数一样 . 根据上面的公式将这5个函数转换为foldr，即在右侧的fold公式中替换f和v .

  折叠通过折叠

  如何编写一个从左到右对数字求和的递归函数？

  sum [] = 0     -- given `sum [1,2,3]` expands into `(1 + (2 + 3))`
  sum (x:xs) = x + sum xs
  

  找到的第一个递归函数在开始累加之前完全展开，这不是我们需要的 . 一种方法是创建一个具有累加器的递归函数，它会立即在每一步上加上数字（阅读tail recursion以了解有关递归策略的更多信息）：

  suml :: [a] -> a
  suml xs = suml' xs 0
    where suml' [] n = n   -- auxiliary function
          suml' (x:xs) n = suml' xs (n+x)
  

  好吧，停下来！在GHCi中运行此代码并确保您了解它是如何工作的，然后仔细并仔细地继续 . suml 无法通过折叠重新定义，但 suml' 可以 .

  suml' []       = v    -- equivalent: v n = n
  suml' (x:xs) n = f x (suml' xs) n
  

  suml' [] n = n 来自功能定义，对吗？并且 v = suml' [] 来自通用属性公式 . 这给了 v n = n 这个函数，它立即返回它收到的任何东西： v = id . 我们来计算 f ：

  suml' (x:xs) n = f x (suml' xs) n
  -- expand suml' definition
  suml' xs (n+x) = f x (suml' xs) n
  -- replace `suml' xs` with `g`
  g (n+x)        = f x g n
  

  因此， suml' = foldr (\x g n -> g (n+x)) id ，因而 suml = foldr (\x g n -> g (n+x)) id xs 0 .

  foldr (\x g n -> g (n + x)) id [1..10] 0 -- return 55
  

  现在我们只需要概括，用变量函数替换 + ：

  foldl f a xs = foldr (\x g n -> g (n `f` x)) id xs a
  foldl (-) 10 [1..5] -- returns -5
  

  结论

  现在阅读Graham Hutton的A tutorial on the universality and expressiveness of fold . 得到一些笔和纸，试着找出他写的所有东西，直到你自己得到大部分的折叠 . 不要理解某些事情，你可以随时回来，但也不要拖延太多 .

  回复于 2024-05-04T16:50:02+08:00
• 9

  这是我的证据 foldl 可以用 foldr 表示，除了名称意大利面之外我发现它很简单 step 功能介绍 .

  这个命题是 foldl f z xs 相当于

  myfoldl f z xs = foldr step_f id xs z
          where step_f x g a = g (f a x)
  

  这里要注意的第一件重要事情是第一行的右侧实际上被评估为

  (foldr step_f id xs) z
  

  因为 foldr 只需要三个参数 . 这已经暗示 foldr 将计算不是值而是计算curried函数，然后将其应用于 z . 有两个案例需要调查，以确定 myfoldl 是否为 foldl ：

  • 基本案例：空列表

  myfoldl f z []
  = foldr step_f id [] z    (by definition of myfoldl)
  = id z                    (by definition of foldr)
  = z
  
    foldl f z []
  = z                       (by definition of foldl)
  

  • 非空列表

  myfoldl f z (x:xs)
  = foldr step_f id (x:xs) z          (by definition of myfoldl)
  = step_f x (foldr step_f id xs) z   (-> apply step_f)
  = (foldr step_f id xs) (f z x)      (-> remove parentheses)
  = foldr step_f id xs (f z x)
  = myfoldl f (f z x) xs              (definition of myfoldl)
  
    foldl f z (x:xs)
  = foldl f (f z x) xs
  

  由于在第2行中，第一行和最后一行在两种情况下都具有相同的形式，因此可以使用它将列表向下折叠直到 xs == [] ，在这种情况下1.保证相同的结果 . 所以通过归纳， myfoldl == foldl .

  回复于 2024-05-04T16:50:02+08:00
• 0

  没有通往数学的皇家之路，甚至也没有Haskell . 让

  h z = (foldr step id xs) z where   
       step x g =  \a -> g (f a x)
  

  到底是什么 h z ？假设 xs = [x0, x1, x2] .
  应用foldr的定义：

  h z = (step x0 (step x1 (step x2 id))) z
  

  应用步骤的定义：

  = (\a0 -> (\a1 -> (\a2 -> id (f a2 x2)) (f a1 x1)) (f a0 x0)) z
  

  替换为lambda函数：

  = (\a1 -> (\a2 -> id (f a2 x2)) (f a1 x1)) (f z x0)
  
  = (\a2 -> id (f a2 x2)) (f (f z x0) x1)
  
  = id (f (f (f z x0) x1) x2)
  

  应用id的定义：

  = f (f (f z x0) x1) x2
  

  应用foldl的定义：

  = foldl f z [x0, x1, x2]
  

  它是皇家之路还是什么？

  回复于 2024-05-04T16:50:02+08:00
• 1

  这可能会有所帮助，我尝试以不同的方式进行扩展 .

  myFoldl (+) 0 [1,2,3] = 
  foldr step id [1,2,3] 0 = 
  foldr step (\a -> id (a+3)) [1,2] 0 = 
  foldr step (\b -> (\a -> id (a+3)) (b+2)) [1] 0 = 
  foldr step (\b -> id ((b+2)+3)) [1] 0 = 
  foldr step (\c -> (\b -> id ((b+2)+3)) (c+1)) [] 0 = 
  foldr step (\c -> id (((c+1)+2)+3)) [] 0 = 
  (\c -> id (((c+1)+2)+3)) 0 = ...
  

  回复于 2024-05-04T16:50:02+08:00
• 1

  foldr step zero (x:xs) = step x (foldr step zero xs)
  foldr _ zero []        = zero
  
  myFold f z xs = foldr step id xs z
    where step x g a = g (f a x)
  
  myFold (+) 0 [1, 2, 3] =
    foldr step id [1, 2, 3] 0
    -- Expanding foldr function
    step 1 (foldr step id [2, 3]) 0
    step 1 (step 2 (foldr step id [3])) 0
    step 1 (step 2 (step 3 (foldr step id []))) 0
    -- Expanding step function if it is possible
    step 1 (step 2 (step 3 id)) 0
    step 2 (step 3 id) (0 + 1)
    step 3 id ((0 + 1) + 2)
    id (((0 + 1) + 2) + 3)
  

  嗯，至少，这对我有帮助 . 即使它不太对劲 .

  回复于 2024-05-04T16:50:02+08:00