list - 在 Haskell 中编写列表上的递归函数

Question

我有以下问题:

Define the functions

and, or :: [Bool] -> Bool

which give the conjunction and disjunction of a list of Booleans. For instance,

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

On an empty list and gives True and or gives False; explain the reason for these choices.

我知道我可以回答它，但不确定最有效的布局方式。任何帮助将不胜感激。

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

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

Answer 1

您必须采取的关键步骤是归纳思考。您当前的解决方案:

and :: [Bool] -> Bool

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

列举了一些可能性，但它显然不适用于所有列表。那么如何编写一个适用于任意长度列表的列表呢？

在 Haskell 中，您通常可以通过分解数据类型来编写函数。在本例中，列出。列表定义为:

data [a] = []
         | a : [a]

因此，列表有两种情况:要么是空列表，要么是带有尾部的一个元素。让我们开始编写 and 函数，以便它匹配列表的这两种情况:

and []     = True
and (a:as) = ...

因此，“基本情况”(空列表)是True。但是对于只有一个元素和一些尾部的列表的情况我们应该怎么做呢？

嗯，我们在 Haskell 中已经有了 && 函数:

> True && True
True
> True && False
False
> False && True
False
> False && False
False

有趣!因此，&& 接受两个参数，并正确确定两个参数是否为 True。我们目前有一个包含一个元素的列表和一个尾部列表。同时，我们定义了 and 函数，该函数在应用于列表时会生成单个 bool 值。

因此我们可以进行归纳步骤并使用我们定义的函数and以及&&二元运算符来完成我们的定义:

and []     = True
and (a:as) = a && (and as)

因此，我们将列表的尾部评估为某个值(递归地)，并使用 && 运算符将该值与当前值组合起来，这就是我们的函数写的。

由列表的递归结构驱动的递归和归纳是编程中学习的关键技术。如果你能写出这个，你就向前迈出了一大步。