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.

Thanks in advanced.

Answer 1

'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.

Answer 2

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)

Answer 3

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]