我的重写折叠功能是否已优化？

Question

我刚刚在2天前创建了Haskell,所以我还不确定如何优化我的代码.

作为练习,我已经改写foldl和foldr(我会给foldl这里却foldr是一样的,更换last用head和init用tail).

代码是:

module Main where

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

    myFoldl func = ( \x -> (\theList
        -> if (length theList == 0) then
            x
        else
            myFoldl func (func x (last theList) ) (init theList)
        ) )

我唯一关心的是我怀疑Haskell不能在这里应用尾调用优化,因为递归调用不是在函数结束时进行的.

如何优化尾调用？Haskell的内置foldl实现是否与我的实现方式不同？

Answer 1

您在代码示例中使用括号以及强调尾递归表明您将从Lisp或Scheme转到Haskell.如果你是从像Scheme这样急切的语言来到Haskell,请注意:尾部调用几乎不像Haskell那样可以预测性能,因为它们是一种急切的语言.你可以使用由于懒惰而在线性空间中执行的尾递归函数,并且你可以使用由于懒惰而在常量空间中执行的非尾递归函数.(已经困惑了吗？)

你定义中的第一个缺陷是使用length theList == 0.这会强制评估列表的整个脊柱,并且是O(n)时间.最好使用模式匹配,就像foldl在Haskell 中这个天真的定义一样:

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

然而,这在Haskell中表现得非常糟糕,因为我们实际上并没有计算f z x部分直到调用者foldl要求结果; 因此,这foldl会在每个列表元素的内存中累积未评估的thunk,并且不会从尾递归中获益.事实上,尽管是尾递归,但这个天真foldl的长列表可能会导致堆栈溢出!(该Data.List模块具有foldl'没有此问题的功能.)

与此相反,许多Haskell非尾递归函数表现得非常好.例如,find根据随附的非尾递归定义来定义foldr:

find :: (a -> Boolean) -> [a] -> Maybe a
find pred xs = foldr find' Nothing xs
    where find' elem rest = if pred elem then Just elem else rest

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (subfold xs)
    where subfold = foldr f z

由于懒惰,这实际上在线性时间和恒定空间中执行.为什么？

1. 一旦找到满足谓词的元素,就不需要遍历列表的其余部分来计算值rest.
2. 一旦你看到一个元素并确定它不匹配,就没有必要保留关于该元素的任何数据.

我现在要传授的教训是:不要将你渴望的语言中的表现假设引入Haskell.你只有两天了; 首先要集中精力理解语言的语法和语义,而不要扭曲自己编写优化版本的函数.你foldl最初会不时遇到风格的堆栈溢出,但你会及时掌握它.

编辑[9/5/2012]:更简单的演示,即find尽管不是尾递归,但懒惰仍然在恒定的空间中运行.首先,简化定义:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

find :: (a -> Bool) -> [a] -> Maybe a
find p xs = let step x rest = if p x then Just x else rest
            in foldr step Nothing xs

现在,使用等式推理(即,使用等于等于,基于上面的定义),并以惰性顺序(最外面的第一个)进行评估,让我们计算find (==400) [1..]:

find (==400) [1..]
    -- Definition of `find`:
    => let step x rest = if x == 400 then Just x else rest
       in foldr step Nothing [1..]

    -- `[x, y, ...]` is the same as `x:[y, ...]`:
    => let step x rest = if x == 400 then Just x else rest
       in foldr step Nothing (1:[2..])

    -- Using the second equation in the definition of `foldr`:
    => let step x rest = if x == 400 then Just x else rest
       in step 1 (foldr step Nothing [2..])

    -- Applying `step`:
    => let step x rest = if x == 400 then Just x else rest
       in if 1 == 400 then Just 1 else foldr step Nothing [2..]

    -- `1 == 400` is `False`
    => let step x rest = if x == 400 then Just x else rest
       in if False then Just 1 else foldr step Nothing [2..]

    -- `if False then a else b` is the same as `b`
    => let step x rest = if x == 400 then Just x else rest
       in foldr step Nothing [2..]

    -- Repeat the same reasoning steps as above 
    => let step x rest = if x == 400 then Just x else rest
       in foldr step Nothing (2:[3..])
    => let step x rest = if x == 400 then Just x else rest
       in step 2 (foldr step Nothing [3..])
    => let step x rest = if x == 400 then Just x else rest
       in if 2 == 400 then Just 2 else foldr step Nothing [3..]
    => let step x rest = if x == 400 then Just x else rest
       in if False then Just 2 else foldr step Nothing [3..]
    => let step x rest = if x == 400 then Just x else rest
       in foldr step Nothing [3..]
        .
        .
        .

    => let step x rest = if x == 400 then Just x else rest
       in foldr step Nothing [400..]
    => let step x rest = if x == 400 then Just x else rest
       in foldr step Nothing (400:[401..])
    => let step x rest = if x == 400 then Just x else rest
       in step 400 (foldr step Nothing [401..])
    => let step x rest = if x == 400 then Just x else rest
       in if 400 == 400 then Just 400 else foldr step Nothing [401..]
    => let step x rest = if x == 400 then Just x else rest
       in if True then Just 400 else foldr step Nothing [401..]

    -- `if True then a else b` is the same as `a`
    => let step x rest = if x == 400 then Just x else rest
       in Just 400

    -- We can eliminate the `let ... in ...` here:
    => Just 400

请注意,随着我们继续执行列表,连续评估步骤中的表达式不会逐渐变得更复杂或更长; 在步骤表达式的长度或深度Ñ不成正比Ñ,它基本上固定的.这实际上说明了如何find (==400) [1..]在恒定的空间中懒惰地执行.

Answer 2

惯用的Haskell看起来与此截然不同,避开if-then-else,嵌套的lambdas,括号和解构函数(head,tail).相反,你会写它像:

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f z0 xs0 = go z0 xs0
   where
       go z []     = z
       go z (x:xs) = go (f z x) xs

依赖于模式匹配,where子句,尾递归,保护声明.