为什么foldl不是用和Fn函数短路的？ [英] why foldl is not short circuiting with andFn function?

问题描述

我的理解是， foldl 和 foldr 的执行方式如下所示：

$ b $ （f（f（f 1）2）3）（f（f（f 1） ... 30）

和

foldr fa [1..30] => （f 1（f 2（f 3（f ....（f 30 a）））））..）

so .. foldr（&& amp;）False（repeat False） can （&& amp;）False（....）） $ c>将第一个参数视为false，并且不需要评估第二个参数（这是一个大的thunk）。

所以

$ b发生了什么
$ b

  andFn :: Bool  - >布尔 - > Bool 
和Fn _ False = False 
和Fn x True = x 
  

和

  foldl andFn True（repeat False） -  => 
 
  - （andFn（andFn ...（andFn True False）... False）False）
  -  ^^最外和
  
 
 
 
但是这是永远的。
 
 
 
我认为 outermost andFn 会通过第二个参数的模式匹配知道答案是 False  .. 
 
 
 
在这里发生了什么？
解决方案 
  foldr 和 foldl 的参数比和Fn 。
  foldr fz（x：xs）= fx（foldr fz xs）
 foldl fz（x：xs）= foldl f（fzx）xs 
  
请注意， foldr 会立即将控制转移至 f ：if  f 是懒惰的，它可以避免计算 foldr fz xs 。
 
 
 
相反， foldl 将控制转移到...  foldl  ：函数 f 只会在开始时被使用
 
 
  foldl fz [] = z  -  z包含链接的f，NOW得到评估
  
因此 foldl fz infiniteList  will  always  diverge，不管什么 f 是：整个 infiniteList 需要在任何真正的计算发生之前完全迭代。 （偏离主题：这就是为什么，即使它起作用， foldl 往往具有糟糕的表现，而 foldl'更多）
 
 
 
特别是，发布的示例
  foldl和Fn True（重复False） -  => 
  - （andFn（andFn ...（andFn True False）... False）False）
  -  ^^ outermost andFn 
  
部分错误。 最外面的和Fn 实际上就是 last ，也就是 last 元素与重复False 。但是没有这样的野兽。
 
My understanding is that foldl and foldr executes like :

foldl f a [1..30] => (f (f (f ... (f a 1) 2) 3) ... 30)

and 

foldr f a [1..30] => (f 1 (f 2 (f 3 (f ....(f 30 a)))))..)

so.. foldr (&&) False (repeat False) can shortciruit as outermost f sees (&&) False ((&&) False (....)) sees first argument as false and does not need to evaluate the second argument (which is a large thunk).

so what happens with 
andFn :: Bool -> Bool -> Bool
andFn _ False = False
andFn x True  = x
and 
foldl andFn True (repeat False)  -- =>

-- (andFn (andFn ...(andFn True False) ... False) False)
--  ^^ outermost andFn
But this is taking forever.

I thought that outermost andFn would know that by pattern matching on second argument, the answer is False..

What else is happening here ?
解决方案
There is a larger difference between foldr and foldl than the order of the arguments to andFn.
foldr f z (x:xs) = f x (foldr f z xs)
foldl f z (x:xs) = foldl f (f z x) xs
Notice how foldr immediately transfers control to f: if f is lazy it can avoid the computation of foldr f z xs.

Instead, foldl transfers control to... foldl: the function f will only start being used when the base case is reached
foldl f z [] = z      -- z contains the chained f's, which NOW get evaluated
Hence foldl f z infiniteList will always diverge, no matter what f is: the whole infiniteList needs to be completely iterated over before any real computation happens. (Off topic: this is why, even when it works, foldl often has horrible performance, and foldl' is more used in practice.)

In particular, the posted example
foldl andFn True (repeat False)  -- =>
-- (andFn (andFn ...(andFn True False) ... False) False)
--  ^^ outermost andFn
is partly wrong. The "outermost andFn" would actually be the last one, i.e. the one related to the last element in repeat False. But there is no such a beast.

                        
这篇关于为什么foldl不是用和Fn函数短路的？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！