学习Haskell映射,折叠,循环和递归

Question

我只是把我的脚趾浸入Haskell的世界,作为我的编程启蒙之旅的一部分(从程序到OOP再到并发到现在的功能).

我一直在尝试在线Haskell评估员.

但是我现在遇到了一个问题:

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

在程序语言中,这对我来说很容易(使用递归)(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;
    }
}

一切都非常好但是我在Haskell的失败尝试是这样的:

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

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

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

请记住,我过去30分钟只使用过Haskell!

我不仅仅是寻找答案,而是更多地解释它.

Answer 1

我不仅仅是寻找答案,而是更多地解释它.

在=的左侧,您将使用sum作为应用的函数x.编译器不知道其类型x,因此编译器使用类型变量a代表"类型" x.此时,编译器也不知道函数的结果类型sum,因此它选择另一个类型变量,即此类型t,代表结果类型.现在在左侧,编译器认为类型x是a -> t(函数接受a和返回t).

在=的右侧你添加x和sum.在Haskell中可以添加所有类型的数字,但只有在它们具有相同类型时才能添加两个数字.所以这里的编译器假设它sum具有相同的类型x,即类型a.

但是在Haskell中,标识符有一种类型 - 可能是whangdilly复杂类型,但仍然是一种类型.这包括sum,其符号两侧的类型应该相同,因此编译器会尝试求解该等式

a = a -> t

有没有对价值观a和t能够解决这个等式. 它根本无法完成.没有a这样a的等于一个接受自己作为参数的函数.因此出现了错误信息

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

即使有了所有的解释,它也不是一个很好的错误信息,是吗？

欢迎来到Haskell :-)

PS你可能喜欢尝试"Helium,用于学习Haskell",它为初学者提供了更好的错误信息.

Answer 2

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

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

或者更有效率,以尾递归的方式:

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

但是,Haskell有一个丰富的控制结构库,可以在惰性列表上运行.在这种情况下,可以使用reduce函数将列表缩减为单个值:折叠.

所以mysum可以写成:

mysum xs  = foldr (+) 0 xs

例如:

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

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

我建议你先介绍一下Haskell,也许是" 在Haskell中编程 ",以了解函数式编程的核心概念.本问题中描述了其他优秀的介绍性材料.