Learning Haskell maps, folds, loops and recursion
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.
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 :-)
PS You might enjoy trying "Helium, for learning Haskell", which gives much nicer error messages for beginners.
'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.
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)
上一篇: ）和[x：
下一篇: 学习Haskell地图，折叠，循环和递归