代码之家 › 专栏 › 技术社区 › Darknight

学习haskell映射、折叠、循环和递归

functional-programming types recursion haskell

8

Darknight · 技术社区 · 15 年前

作为编程启蒙之旅的一部分(从过程到OOP,从并发到现在的功能),我刚刚涉足了Haskell的世界。

我在网上试过 Haskell Evaluator .

但是我现在陷入了一个问题:

创建一个简单的函数,它给出一个数字数组的总和。

在程序语言中,这对我来说非常简单(使用递归)(C):

private int sum(ArrayList x, int i)
{
  if (!(x.Count < i + 1)) {
        int t = 0;

        t = x.Item(i);
        t = sum(x, i + 1) + t;
        return t;
    }
}

一切都很好,但是我在哈斯克尔的失败尝试是这样的:

let sum x = x+sum  in map sum [1..10]

这导致以下错误(来自上述网站):

Occurs check: cannot construct the infinite type: a = a -> t

请记住,我过去30分钟只使用过哈斯克尔!

我不是简单地寻找一个答案,而是更多的解释。

4 回复 | 直到 8 年前

1

16

Norman Ramsey 15 年前

我不是简单地寻找一个答案,而是更多的解释。

在=的左侧使用 sum 作为一个函数应用于 x . 编译器不知道 X ,因此编译器使用类型变量 a 代表 X ”此时,编译器不知道函数的结果类型。 总和 或者,所以它选择另一个类型变量,这个类型 t ,表示结果类型。现在在左边,编译器认为 X 是 a -> t (功能接受 一 归还 T )

在=的右侧添加 X 和 总和 . 在haskell中,可以添加所有类型的数字,但只有当两个数字具有 相同的 类型。所以这里编译器假设 总和 与具有相同类型 X ,即类型 一 .

但在haskell中,标识符有一种类型,可能是一种非常复杂的类型,但也有一种类型。这包括 总和 ,其类型应在符号的两侧相同,因此编译器尝试求解公式

a = a -> t

没有值用于 一 和 T 解这个方程。 根本做不到。没有 一 这样 一 等于接受自己为参数的函数。从而产生错误信息

cannot construct the infinite type: a = a -> t

即使有了所有的解释,这也不是一个伟大的错误信息,是吗?

欢迎来到Haskell:-)

另外,你可能喜欢尝试“氦,用于学习haskell”,它为初学者提供了更好的错误信息。

2

12

Community CDub 8 年前

“sum”获取值列表并将其减少为单个值。您可以将其写为显式循环(记住haskell没有循环关键字,但使用递归)。请注意,根据列表的形状,定义有两个部分:

mysum []     = 0
mysum (x:xs) = x + mysum xs

或更有效地, tail-recursive 风格:

mysum xs = go 0 xs
   where
      go n []     = n
      go n (x:xs) = go (n+x) xs

但是,haskell有一个丰富的控制结构库,可以对懒惰的列表进行操作。在这种情况下, 减少列表的一个值可以用一个reduce函数来完成:一个fold。

所以mysum可以写成:

mysum xs  = foldr (+) 0 xs

例如:

Prelude> foldr (+) 0 [1..10]
55

你的错误是使用地图 ,它一次转换一个列表、一个元素,而不是折叠 .

我建议你从介绍哈斯克尔开始,也许” Programming in Haskell “,了解函数式编程的核心概念。介绍了其他很好的介绍材料。 in this question.

3

1

D'Nabre 15 年前

你需要读一个好的教程,有很多大的误解。

首先,我假设你指的是列表而不是数组。数组存在于haskell中,但在初学者级别,它们不是你会遇到的。(更不用说你用的是[1..10],它是数字1到10的列表)。

您想要的函数实际上是内置的,称为sum,因此我们必须调用其他函数,即new_sum:

new_sum [] = 0
new_sum (h:t) = h + (sum t)

4

0

stonemetal 15 年前

让我们来看看第一部分:

let sum x = x+sum

在这种情况下,总和的类型是什么?它接受一个数字并返回一个接受一个数字的函数,如果你写了这个数字,它将返回一个接受一个数字的函数等。设求和x++x 您将拥有一个接受数字并返回函数+X的函数。和求和=+ 将返回一个接受两个整数并将其相加的函数。

现在让我们来看第二部分。地图总和[1..10] map接受一个参数的函数,并将其应用于列表的每个元素。这里没有插入蓄能器的空间,所以让我们看看其他列表函数,特别是foldl、folder。这两个函数都有两个参数,一个是列表,另一个是起始值。foldl和folder的区别就在它们开始的那一边。L为左,1+2+3等,R为右,10+9+8等。

在foldl sum 0[1..10]中设sum=(+)