如何实现递归函数？

Question

下面定义了一个代数数据类型 IntList ：

data IntList = Empty | Cons Int IntList

函数 intListProd 计算 IntList 类型的乘积：

intListProd :: IntList -> Int
intListProd Empty      = 1
intListProd (Cons x l) = x * intListProd l

但我不确定如何创建 IntList 类型。

我试过了：

*Main> let x = Cons 3
*Main> :t x
x :: IntList -> IntList

但是如何创建类型 IntList 以便调用 intListProd ？

Answer 1

一个Cons单元格包含两个东西：一个元素和一个尾部。如果列表只应包含一个元素，则尾部为空（由 nullary 构造函数 Empty 表示）。因此，要表示包含 3 作为其唯一元素的列表，您可以使用：

let x = Cons 3 Empty

那么 :t x 将是 IntList。

Answer 2

您正在创建新的数据类型：

data IntList = Empty | Cons Int IntList

这基本上为您创建了 2 个数据构造函数：

> :t Empty
Empty :: IntList

> :t Cons
Cons :: Int -> IntList -> IntList

所以第一个 return 是 IntList 类型，第二个需要 2 个参数（Int 和 IntList）和 return IntList。

在您的绑定中，您只是部分应用 Cons 函数，只给它 1 个参数：

*Main> let x = Cons 3

这是要求您将另一个 IntList 作为完整类型。现在，您可以通过两种方式获得 IntList（因为您有 2 个此类型的构造函数）：

Cons 3 (Empty)

或

Cons 3 (Cons a b) --where a is an Int and b is IntList.

现在第二个，b 可以是 Empty 或 Const a' b':

Cons 3 (Cons 1 (Empty))

或

Cons 3 (Cons 2 (Cons 1 (Empty))) -- 3 2 1 could be any Int number.

现在让我们进一步了解第二种类型：

Cons Int ( Cons Int ( Cons Int ( IntList)))

还记得 Cons 接受一个 Int 和一个 IntList 并且 returns 接受一个 IntList 吗？

Cons Int ( Cons Int ( IntList)) --Now doing the same we came up to
Cons Int (IntList) -- Once more
IntList

这意味着我们的构造 Cons 3 (Cons 2 (Cons 1 (Empty))) 具有 IntList 类型，可用于对其应用 intListProd 计算。

How to implement recursive function?