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

Question

我有以下问题:

定义功能

and, or :: [Bool] -> Bool

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

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

在空列表中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

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函数,当应用于列表时会产生单个布尔值.

因此,我们可以使用归纳步骤并使用我们定义的函数and,与&&二元运算符一起完成我们的定义:

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

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

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

Answer 2

我建议使用模式匹配来剖析列表.从这些条件开始:

and [] = True
and (True : xs) = ...
and (False : xs) = ...

好的,对于一个空列表and是True.如果列表以" True"头开头,您如何确定完整列表的"真实性"？你需要递归电话吗？如果你有一个False"头"怎么办？

该or情况是相似的,只是开始or [] = False

请注意,当您从这些定义开始时,这些定义已经模式匹配真值,您甚至不需要使用&&或||.