haskell – 无限列表上的foldl行为

我对列表中的foldl与foldr的理解是:

如果我们右边用函数s和一个起始累加器a折叠[0,1,2,3],我们这样做:

f 0(f 1(f 2(f 3 a)))

如果我们使用函数s和起始累加器a保留fold [0,1,2,3],我们这样做:

f(f(f(f 0 a)1)2)3)

鉴于:

elem_r :: (Eq a) => a -> [a] -> Bool
elem_r y ys = foldr (\x acc -> if x == y then True else acc) False ys

elem_l :: (Eq a) => a -> [a] -> Bool
elem_l y ys = foldl (\acc x -> if x == y then True else acc) False ys

我似乎很清楚elem_r 3 [0 ..]将计算它真正必须的值,并在达到值3时立即返回True.

f 0(f 1(f 2(f 3(…)))

而elem_l 3 [0 ..]需要在返回结果之前评估完整的嵌套函数应用程序.

f(f(f(f(f 0 3)1)2)3)…)

现在我的问题是:

在elem_l 0 [0 ..]的特定情况下
搜索的元素是列表的第一项.

在这个表达式中:
f(f(f(f(f 0 0)1)2)3)…)
最里面的函数(f 0 0)可以立即被评估为“真”.
为什么Haskell继续评估其余的嵌套函数?

因为f(f(f(f(0 0)1)2)3)…)不对.最后的括号和第一个f不匹配,最初的参数都是错误的.它确实是

(f ... (f (f (f (f False 0) 1) 2) 3) ...)

所以在foldl完成构建这个表达式之后(从来没有),我们必须通过无限量的嵌套表达式,首先评估它们,然后才能到达最里面的表达式,最后得到它(因为f在0上停止) .或者在这种情况下,永远不会.

另一个测试,搜索3,将在之前停止(f(f(f(f False 0)1)2)3),因为现在f停在3;但是在构建了无限的嵌套表达式之后,它仍然必须先经历无限量的嵌套表达式.

相关文章
相关标签/搜索