foldl / foldr查询

5 回答

• 6

  在 foldl 情况下，lambda作为第一个参数传递累加器，而第二个参数传递list元素 . 在 foldr 情况下，lambda作为第一个参数传递list元素，第二个参数传递累加器 .

  你的lambda忽略第一个参数，并在第二个参数中加1，所以在 foldl 情况下你将1加到最后一个元素，而在 foldr 情况下，你正在计算列表中元素的数量 .

  回复于 2024-04-26T15:32:53+08:00
• 7

  那是因为参数的顺序在 foldl 中翻转 . 比较他们的类型签名：

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

  所以你看，在使用 foldl 的代码中，你重复递增累加器，忽略列表 . 但是在带有 foldr 的代码中，你甚至都没有触及累加器，只是增加了列表的元素 . 由于最后一个元素是 3 ，结果是 3 + 1 = 4 .

  如果您使用字符列表而不是字符串，您可以更容易地看到您的错误：

  ghci> foldr (\_ -> (+1)) 0 ['a','b','c']
  3
  ghci> foldl (\_ -> (+1)) 0 ['a','b','c']
  
  :1:20:
      No instance for (Num Char)
        arising from the literal `0'
      Possible fix: add an instance declaration for (Num Char)
      In the second argument of `foldl', namely `0'
      In the expression: foldl (\ _ -> (+ 1)) 0 ['a', 'b', 'c']
      In an equation for `it':
          it = foldl (\ _ -> (+ 1)) 0 ['a', 'b', 'c']
  ghci>
  

  回复于 2024-04-26T15:32:53+08:00
• 7

  不同之处在于两件事：

  • 您正在丢弃累加功能的一个输入并将常量功能应用于另一个 .

  • 累加函数的参数顺序在两者之间是不同的 .

  使用左侧折叠，累加器是您丢弃的参数，因此每次将 (+1) 应用于列表中的下一个项目并最终返回最后一个元素加一个 .

  使用右侧折叠，累加器是您保留的参数，因此每次将 (+1) 应用于上一个结果时，该值为0并且开始增加三次（对于列表中的每个项目） .

  如果你使用更明显不同的输入值，可能更容易看到这里发生了什么：

  Prelude> foldl (\_ -> (+1)) 100 [5,6,7]
  8
  Prelude> foldr (\_ -> (+1)) 100 [5,6,7]
  103
  

  再次，“最后一个参数加一个”和“列表长度加上初始值” .

  回复于 2024-04-26T15:32:53+08:00
• 4

  在 foldl f 中，累加器是 f 的左参数，您忽略它，因此返回 1 + 最后一个元素 . 对于 foldr ，累加器是正确的参数，因此您将每个项目的累加器增加1，从而有效地给出列表的长度 .

  f x y = y + 1
  
  foldl f 0 [1, 2, 3]
  = f (f (f 0 1) 2) 3 
  = f ignored 3
  = 3 + 1
  = 4
  
  foldr f 0 [1, 2, 3]
  = f 1 (f 2 (f 3 0)))
  = f ignored (f ignored (f ignored 0)))
  = ((((0 + 1) + 1) + 1)
  = 3
  

  回复于 2024-04-26T15:32:53+08:00
• 6

  去除currying和point自由样式可能会有所帮助 . 你的两个表达式是等效的：

  foldl (\acc x ->   x + 1) 0 [1,2,3]
  foldr (\x acc -> acc + 1) 0 [1,2,3]
  

  当这样看时，结果应该显得更加明显

  回复于 2024-04-26T15:32:53+08:00