相关疑难解决方法(0)

我试图理解Haskell中的尾递归.我想我明白它是什么以及它是如何工作的但是我想确保我没有搞砸了.

这是"标准"因子定义:

factorial 1 = 1
factorial k = k * factorial (k-1)

例如,在运行时,factorial 3我的函数会自行调用3次(给它或者拿它).如果我想计算因子99999999,这可能会产生问题,因为我可能有堆栈溢出.在我到达之后,factorial 1 = 1我将不得不在堆栈中"返回"并将所有值相乘,因此我有6个操作(3个用于调用函数本身,3个用于乘以值).

现在我向您介绍另一种可能的因子实现:

factorial 1 c = c
factorial k c = factorial (k-1) (c*k)

这个也是递归的.它会称自己为3次.但它没有问题,然后仍然必须"回来"计算所有结果的乘法,因为我已经将结果作为函数的参数传递.

根据我的理解,这就是Tail Recursion的内容.现在,它似乎比第一个好一点,但你仍然可以轻松地拥有堆栈溢出.我听说Haskell的编译器会在后台将Tail-Recursive函数转换为for循环.我想这就是为什么它能够为尾递归功能付出代价呢？

如果这就是原因,那么如果编译器不打算做这个聪明的技巧,那么绝对没有必要尝试使函数尾递归 - 我是对的吗？例如,虽然理论上C#编译器可以检测并将尾递归函数转换为循环,但我知道(至少是我所听到的)目前它没有这样做.所以现在绝对没有必要使函数尾递归.是吗？

谢谢!

我有以下问题:

定义功能

and, or :: [Bool] -> Bool

Run Code Online (Sandbox Code Playgroud)

它给出了一个布尔列表的连接和分离.例如,

and [False, True] = False
or  [False, True] = True

Run Code Online (Sandbox Code Playgroud)

在空列表中and给出True并or给出False; 解释这些选择的原因.

我知道我可以回答它,但我不确定最有效的方法来解决它.任何帮助将非常感激.

我的解决方案是这样的(但我认为它可能更有效):

and, or :: [Bool] -> Bool

and []             = True
and [True, True]   = True
and [False, False] = True
and [True, False]  = False

or []             = False
or [True, True]   = False
or [False, False] = False
or [True, False]  = True