在Haskell的列表上编写递归函数 [英] Writing a recursive function on lists in Haskell

问题描述

我有以下问题：

lockquote

定义函数

 和，或者:: [Bool]  - > Bool 
  

它们给出了布尔列表的连接和分离。例如，

 和[False，True] = False 
或[False，True] = True 
  

在一个空列表和上给出 True 和或给出 False ;解释这些选择的原因。

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

我的解决方案是这样的（但我认为它可能更有效率）：

 和，或:: [Bool]  - > Bool 
 
和[] = True 
和[True，True] = True 
和[False，False] = True 
和[True，False] = False 
 
或[] = False 
或[True，True] = False 
或[False，False] = False 
或[True，False] = True 
  

解决方案

您需要做的关键一步是思考 。您当前的解决方案：

  and :: [Bool]  - > Bool 
 
和[] = True 
和[True，True] = True 
和[False，False] = True 
和[True，False] = False 
  

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

在Haskell中，通常可以通过拆分数据类型来编写函数。在这种情况下，列表。列表定义为：

  data [a] = [] 
 | a：[a] 
  

因此，列表有两种情况：空列表或一个元素尾巴。让我们开始编写你的和函数，以便匹配这两个列表的情况：

 和[] = True 
和（a：as）= ... 
  

因此，空白列表基本情况是 True 。但是我们应该如何处理包含一个元素和尾部的列表？

好的，我们已经有了&& 在Haskell中的函数：

 >真正的&& True 
 True 
>真正的&& False 
 False 
>假&& True 
 False 
>假&&假
假
  

有趣！因此，&& 接受两个参数，并正确判断两个参数是否为True。我们目前有一个元素列表和一个尾部列表。同时，我们定义了和函数，当应用于列表时，会得到一个布尔值。

因此，我们可以使为归纳步骤，并使用我们定义的函数和，以及<$ c $

 和[] = True   
和（a：as）= a&& （和）
  

因此，我们评估列表的尾部到某个值（递归），并使用&& 运算符将那个值与当前值结合在一起，这就是我们的函数。

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

I have the following 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.

I know I can answer it but am not sure of the most efficient way to lay it out. Any help would be much appreciated.

My solution was this (but I think it could be more efficient):

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

解决方案

The key step you're going to have to make is to think inductively. Your current solution:

and :: [Bool] -> Bool

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

enumerates some of the possibilities, but it obviously doesn't work for all lists. So how to write one that will work for lists of any length?

In Haskell, you can usually write your functions by taking apart a data type. In this case, lists. Lists are defined as:

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

So, lists have two cases: either the empty list, or a one element with a tail. Let's start writing your and function then, so that it matches those two cases for lists:

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

So, the "base case", the empty list, is True. But what should we do for the case of a list with one element, and some tail?

Well, we already have the && function in Haskell:

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

Interesting! So, && takes two arguments, and correctly determines if both arguments are True. And we are currently have a list with one element, and a list for a tail. And at the same time, we're defining the and function, that results in a single boolean value when applied to a list.

So we can make the inductive step and use the function we're defining, and, together with the && binary operator, to finish our definition:

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

So we evaluate the tail of the list to some value (recursively), and use the && operator to combined that value with the current value, and that's our function written.

Recursion and induction, driven by the recursive structure of the lists, are the key technique to learn in programming. If you can write this, you're making a big step forward.

这篇关于在Haskell的列表上编写递归函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！