相关疑难解决方法(0)

我今天在unix中发现了"time"命令,并认为我会用它来检查Haskell中尾递归和正常递归函数之间运行时的差异.

我写了以下函数:

--tail recursive
fac :: (Integral a) => a -> a
fac x = fac' x 1 where
    fac' 1 y = y
    fac' x y = fac' (x-1) (x*y) 

--normal recursive
facSlow :: (Integral a) => a -> a
facSlow 1 = 1
facSlow x = x * facSlow (x-1)

这些都是有效的,记住它们只是用于这个项目,所以我没有费心去检查零或负数.

但是,在为每个编写一个main方法,编译它们,并使用"time"命令运行它们时,两者都具有相似的运行时,正常的递归函数使尾递归函数边缘化.这与我在lisp中关于尾递归优化的内容相反.这是什么原因？

在Haskell Wiki的monad中的递归中有一个声称是尾递归的例子:

f 0 acc = return (reverse acc)
f n acc = do
    v  <- getLine
    f (n-1) (v : acc)

虽然命令式符号使我们相信它是尾递归的,但它根本不是那么明显(至少对我而言).如果我们去糖,do我们得到

f 0 acc = return (reverse acc)
f n acc = getLine >>= \v -> f (n-1) (v : acc)

并重写第二行导致

f n acc = (>>=) getLine (\v -> f (n-1) (v : acc))

所以我们看到它f发生在第二个参数内>>=,而不是在尾递归位置.我们需要考察IO的>>=得到答案.显然,将递归调用作为do块中的最后一行是一个尾递归函数的充分条件.

假设monad是尾递归的,如果这个monad中的每个递归函数都定义为 …