Learning Haskell maps, folds, loops and recursion

Question

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.

Answer 1

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.