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

发布于 2024-09-05 11:31:52 字数 748 浏览 2 评论 0原文

我刚刚涉足 Haskell 的世界，这是我编程启蒙之旅的一部分（从过程式到 OOP，再到并发，再到现在的函数式）。

我一直在尝试在线 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;
    }
}

一切都很好，但是我在 Haskell 上的失败尝试是这样的：

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

这导致了以下错误（来自上述网站）：

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

请记住，我只在过去 30 分钟内使用过 Haskell！

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

原文

I've only just dipped my toe in the world of Haskell as part of my journey of programming enlightenment (moving on from, procedural to OOP to concurrent to now functional).

I've been trying an online Haskell Evaluator.

However I'm now stuck on a problem:

Create a simple function that gives the total sum of an array of numbers.

In a procedural language this for me is easy enough (using recursion) (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;
    }
}

All very fine however my failed attempt at Haskell was thus:

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

this resulted in the following error (from that above mentioned website):

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

Please bear in mind I've only used Haskell for the last 30 minutes!

I'm not looking simply for an answer but a more explanation of it.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

穿越时光隧道 2024-09-12 11:31:52

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

在 = 的左侧，您使用 sum 作为应用于 x 的函数。编译器不知道x的类型，因此编译器使用类型变量a来代表“x的类型”。此时编译器也不知道函数 sum 的结果类型，因此它选择另一个类型变量，即此类型 t 来代表结果类型。现在，在左侧，编译器认为 x 的类型是 a ->; t（函数接受a并返回t）。

在 = 的右侧添加 x 和 sum。在 Haskell 中，所有类型的数字都可以相加，但只有当两个数字具有相同类型时才可以相加。所以这里编译器假设 sum 与 x 具有相同的类型，即类型 a。

但在 Haskell 中，标识符只有一种类型——也许是一种非常复杂的类型，但仍然是一种类型。这包括 sum，其类型在 ` 符号两侧应该相同，因此编译器尝试求解方程

a = a -> t

a 没有值并且t 来解决这个方程。这根本不可能完成。不存在 a 使得 a 等于接受自身作为参数的函数。因此出现了错误消息

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

即使有了所有的解释，这也不是一个很好的错误消息，不是吗？

欢迎使用 Haskell :-)

PS 您可能喜欢尝试“Helium，用于学习 Haskell”，它为初学者提供了更好的错误消息。

I'm not looking simply for an answer but a more explanation of it.

On the left-hand side of the = you use sum as a function applied to x. The compiler doesn't know the type of x, so the compiler uses type variable a to stand for "the type of x." At thus point the compiler doesn't know the result type of the function sum either, so it picks another type variable, this type t, to stand for the result type. Now on the left-hand side the compiler thinks that the type of x is a -> t (function accepting a and returning t).

On the right-hand side of the = you add x and sum. In Haskell all kinds of numbers can be added, but you can add two numbers only if they have the same type. So here the compiler assumes that sum has the same type as x, namely type a.

But in Haskell an identifier has one type—maybe a whangdilly complicated type, but one type nevertheless. This includes sum, whose type should be the same on both sides of the ` sign, so the compiler tries to solve the equation

a = a -> t

There are no values for a and t that solve this equation. It simply can't be done. There is no a such that a is equal to a function that accepts itself as an argument. Thus ariseth the error message

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

Even with all the explanation, it's not such a great error message, is it?

Welcome to Haskell :-)

P.S. You might enjoy trying "Helium, for learning Haskell", which gives much nicer error messages for beginners.

回复收藏 0 原文

满意归宿 2024-09-12 11:31:52

'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 有一个丰富的控制结构库，可以在惰性列表上运行。在这种情况下，可以使用归约函数将列表缩减为单个值：折叠。

因此 mysum 可以写为：

mysum xs  = foldr (+) 0 xs

例如：

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

您的错误是使用 map，它会转换列表，一次一个元素，而不是 fold。

我建议你从 Haskell 的介绍开始，也许是“用 Haskell 编程”，了解函数式编程的核心概念。本问题中描述了其他很好的介绍性材料。

'sum' takes a list of values and reduces it to a single value. You can either write it as an explicit loop (remember that Haskell has no loop keywords, but uses recursion). Note how the definition has two parts, based on the shape of the list:

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

Or more efficiently, in a tail-recursive style:

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

However, Haskell has a rich library of control structures that operate on lazy lists. In this case, reduction of a list to a single value can be done with a reduce function: a fold.

So mysum can be written as:

mysum xs  = foldr (+) 0 xs

For example:

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

Your mistake was to use a map, which transforms a list, one element at a time, rather than a fold.

I'd suggest you start with an introduction to Haskell, perhaps "Programming in Haskell", to get a feel for the core concepts of functional programming. Other good introductory materials are described in this question.

回复收藏 0 原文

花开半夏魅人心 2024-09-12 11:31:52

你需要阅读一个好的教程，其中有很多很大的误解。

首先，我假设您指的是列表而不是数组。 Haskell 中存在数组，但您在初学者级别不会遇到它们。（更不用说您正在使用 [1..10]，它是数字 1 到 10 的列表）。

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

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

You need to read a good tutorial, there are a number of big misunderstandings.

First I'm going to assume you mean lists and not arrays. Arrays exist in Haskell, but they aren't something you'd encounter at the beginner level. (Not to mention you're using [1..10] which is a list of the numbers 1 to 10).

The function you want is actually built in, and called sum, so we'll have to call our something else, new_sum:

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

回复收藏 0 原文

一人独醉 2024-09-12 11:31:52

让我们看一下第一部分：

let sum x = x+sum

在这种情况下，sum 的类型是什么？它接受一个数字并返回一个接受数字的函数，该函数返回一个接受数字的函数等（如果您已经编写了它）
令总和 x = + x
您将有一个接受数字并返回函数 +x 的函数。
和
让总和 = +
将返回一个接受两个整数并将它们相加的函数。

现在让我们看第二部分。
在地图总和[1..10]中
map 接受一个只有一个参数的函数，并将其应用于列表中的每个元素。那里没有空间容纳累加器，所以让我们看看其他列表函数，特别是foldl、foldr。这两个函数都采用两个参数的函数：列表和起始值。 Foldl 和 Foldr 之间的区别在于它们开始的一侧。 l 向左，所以 1 + 2 + 3 等，r 向右，10 + 9 + 8 等。

让 sum = (+) in Foldl sum 0 [1..10]

Let's look at the first part of this:

let sum x = x+sum

What would the type of sum be in this case? It takes a number and returns a function that takes a number which returns a function that takes a number etc. if you had written it
let sum x = + x
you would have a function that takes a number and returns the function +x.
and
let sum = +
would return a function that takes two integers and adds them.

so now let's look at the second part.
in map sum [1..10]
map takes a function of one argument and applies it to every element of the list. There is no room to wedge an accumulator in there, so let's look at other list functions in particular foldl, foldr. both of these take a function of two arguments a list and a beginning value. The difference between foldl and foldr is on the side in which they start. l being left so 1 + 2 + 3 etc and r being right 10 + 9 + 8 etc.

let sum = (+) in foldl sum 0 [1..10]

回复收藏 0 原文

~没有更多了~