尾递归识别

Question

我正在努力学习Haskell,我偶然发现了以下内容:

myAdd (x:xs) = x + myAdd xs
myAdd null = 0

f = let n = 10000000 in myAdd [1 .. n]

main = do
 putStrLn (show f)

使用GHC进行编译时,会产生堆栈溢出.作为一名C/C++程序员,我本以期望编译器进行尾调用优化.

我不喜欢在这样的简单情况下我必须"帮助"编译器,但有什么选择？我认为要求在不使用O(n)存储器的情况下完成上面给出的计算是合理的,并且不需要推迟专门的功能.

如果我不能自然地陈述我的问题(即使是这样的玩具问题),并且期望在时间和空间方面有合理的表现,那么Haskell的大部分吸引力都会丢失.

Answer 1

首先,确保你正在编译-O2.它会让很多性能问题消失:)

我能看到的第一个问题是那里null只是一个变量名.你想要的[].它在这里是等价的,因为唯一的选择是x:xs和[],但它并不总是如此.

这里的问题很简单:当你打电话时sum [1,2,3,4],它看起来像这样:

1 + (2 + (3 + (4 + 0)))

因为Haskell的非严格语义,所以没有减少任何这些添加到一个数字.解决方案很简单:

myAdd = myAdd' 0
  where myAdd' !total [] = total
        myAdd' !total (x:xs) = myAdd' (total + x) xs

(您需要{-# LANGUAGE BangPatterns #-}在源文件的顶部进行编译.)

这会在另一个参数中累积加法,实际上是尾递归(你的不是; +在尾部位置而不是myAdd).但实际上,它并不是我们在Haskell中关心的尾部递归; 这种区别主要与严格的语言有关.这里的秘诀就是一声模式上total:它迫使它来评估每一次myAdd'被调用,因此未评估的补充建立,并在不断的空间中运行.在这种情况下,GHC实际上可以-O2通过其严格性分析来解决这个问题,但我认为通常最好明确你想要什么严格和什么不是.

请注意,如果添加是懒惰的,您的myAdd定义将正常工作; 问题是你正在使用严格的操作对列表进行惰性遍历,最终导致堆栈溢出.这主要是算术,对标准数字类型(Int,Integer,Float,Double等)是严格的.

这非常难看,每当我们想写一个严格的折叠时,写这样的东西会很痛苦.值得庆幸的是,Haskell为此准备了抽象!

myAdd = foldl' (+) 0

(你需要添加import Data.List来编译它.)

foldl' (+) 0 [a, b, c, d]就像(((0 + a) + b) + c) + d,除了在每个应用程序(+)(这是我们如何将二元运算符+称为函数值)中,该值被强制评估.生成的代码更清晰,更快速,更易于阅读(一旦您知道列表折叠如何工作,您就可以理解使用它们编写的任何定义比递归定义更容易).

基本上,这里的问题并不是编译器无法弄清楚如何使程序高效 - 这就是让它变得有效可以改变它的语义,优化永远不应该这样做.Haskell的非严格语义肯定会给程序员带来更多"传统"语言(如C语言)的学习曲线,但随着时间的推移它变得越来越容易,一旦你看到Haskell的非严格性提供的强大功能和抽象,你永远不会想要去背部 :)

Answer 2

扩展示例ehird在评论中暗示:

data Peano = Z | S Peano
  deriving (Eq, Show)

instance Ord Peano where
    compare (S a) (S b) = compare a b
    compare Z Z = EQ
    compare Z _ = LT
    compare _ _ = GT

instance Num Peano where
    Z + n = n
    (S a) + n = S (a + n)
    -- omit others
    fromInteger 0 = Z
    fromInteger n
        | n < 0 = error "Peano: fromInteger requires non-negative argument"
        | otherwise = S (fromInteger (n-1))

instance Enum Peano where
    succ = S
    pred (S a) = a
    pred _ = error "Peano: no predecessor"
    toEnum n
        | n < 0 = error "toEnum: invalid argument"
        | otherwise = fromInteger (toInteger n)
    fromEnum Z = 0
    fromEnum (S a) = 1 + fromEnum a
    enumFrom = iterate S
    enumFromTo a b = takeWhile (<= b) $ enumFrom a
    -- omit others

infinity :: Peano
infinity = S infinity

result :: Bool
result = 3 < myAdd [1 .. infinity]

result是True通过定义myAdd,但如果编译器转换为尾递归循环,它将不会终止.因此,转换不仅是效率的变化,也是语义的变化,因此编译器不能这样做.

Answer 3

关于"问题是为什么编译器无法优化看起来很容易优化的东西的一个有趣的例子."

假设我是从Haskell转向C++.我曾经写过,foldr因为在Haskell foldr中通常比foldl懒惰和列表融合更有效.

所以我试图foldr在C中编写一个(单链接)列表并抱怨为什么它效率非常低:

int foldr(int (*f)(int, node*), int base, node * list)
{
    return list == NULL
        ? base
        : f(a, foldr(f, base, list->next));
}

效率低下并不是因为有问题的C编译器是象牙塔理论家为了自己的满意而开发的一种不切实际的玩具工具,但是因为所讨论的代码对于C来说是非常非惯用的.

不是你不能用foldrC 编写高效的情况:你只需要一个双向链表.在Haskell中,类似地,您可以编写一个高效的foldl,您需要严格的注释foldl才能有效.标准库提供foldl(无注释)和foldl'(带注释).

在Haskell中左侧折叠列表的想法与使用C中的递归向后迭代单个链接列表的想法相同.编译器可以帮助普通人,而不是变态lol.

由于您的C++项目可能没有向后迭代单链接列表的代码,我的HNC项目只包含1个foldl我错误写入之前我已经掌握了足够的Haskell.你几乎不需要foldl在Haskell.

您必须忘记前向迭代是自然且最快的,并了解向后迭代是.前向迭代(左折叠)不会按照您的意图执行,直到您注释:它执行三次传递 - 列表创建,thunk链构建和thunk评估,而不是两次(列表创建和列表遍历).请注意,在不可变世界列表中,只能有效地向后创建列表:a:b是O(1),而++ [b]是O(N).

并且后向迭代不会按照您的意图执行.它可以通过C背景进行一次而不是三次.它不会创建一个列表,将其遍历到底部然后向后遍历它(2遍) - 它在创建它时遍历列表,即1遍.通过优化,它只是一个循环 - 没有创建实际的列表元素.在优化关闭的情况下,它仍然是O(1)空间操作,具有更大的常量开销,但解释有点长.