Haskell - C stack overflow

Question

I've just been introduced to Haskell, so I'm not very practiced at how to code in the language, and hence, sorry if this is a duplicate, however I do not understand the other code written in the language.

I am trying to write an algorithm that will take the sum of the positive even integers not exceeding the value given. I have attempted to write the code however I have been getting the C stack overflow error.

Here is my code:

sumint :: Int -> Int
sumint x
  | x==0 = 0  
  | x==1 = 1
  | (x `mod` 2 == 0) && (x >= 2) = x + (sumint x-2)
  | (x `mod` 2 /= 0) && (x >= 1) = x + (sumint x-1)

Where am I going wrong to get this error?

Answer 1

Initial Error: Infinite Recursion

Stepping through your code:

sumint :: Int -> Int

Hey, a type signature. You rock.

sumint x
  | x==0 = 0

A base case, cool.

  | x==1 = 1

A totally unnecessary case. OK, sure... except. 1 is not even so why are we including it in the sum? It should be zero (or removed completely).

  | (x `mod` 2 == 0) && (x >= 2) = x + (sumint x-2)

The meat of the issue is here. 1. X is even - great. 2. X is positive, yep. The result is x + (sumint x) - 2 No!

• Error 1: Notice function application binds tigher than operators so this should be x + sumint (x-2).

This is the reason for your stack overflow. sumint 2 == 2 + (sumint 2) - 2 + (sumint 2) -2 + (sumint 2) -2 + ..., yay infinite recursion.

  | (x `mod` 2 /= 0) && (x >= 1) = x + (sumint x-1)

Another case... odds... positive... but why are we adding in x? You want to add evens, not odds. So fixing the above issue at the same time we get:

• Error 2: If you determine x is odd, don't add in x. Just use sumint (x-1).

Then you are out of cases. What happens if x is not positive? You need (another) case.

| otherwise = 0

Next Issue: No Accumulation

The problem now is you are building up a large thunk (unevaluated computation) instead of operating in constant space by accumulating the result as you progress. Notice if we expand your computation for, say, 6 we get:

sumint 6 = 6 + sumint (6-2) 
      = 6 + 4 + sumint (4-2)
      = 6 + 4 + 2 + sumint (2-2)
      = 6 + 4 + 2 + 0

You really don't want to keep all those additions separate, it would be good to pass in an accumulator such as:

sumint x = go x 0
 where
  go n accumulator
         | n <= 0    = accumulator
         | odd n     = go (n-1) accumulator
         | otherwise = go (n-2) (accumulator + n)

Side note: Other stackoverflow citizens might mention making the accumulator strict, which is good form. I don't want to distract the current asker with that discussion here. Notice using optimization, -O2, does suffice.

Idiomatic Solutions

All the above solutions are rather verbose. The general operation, iterating over a list with a function and accumulator, is a type of fold. Fold's are one of the many highly optimized structure traversals common in functional programming. In this case a "strict left fold" is the typical candidate (from Data.List). That is foldl'' the prime (') by convention means it is strict while the l means left.

sumint n = foldl' (+) 0 [val | val <- [0..n], even val]

Here we folded over the list to get our sum. To create the list of interest we used list comprehension - first enumerating the values from 0..n and skipping any value that does not meet the predicate even.

We can further clean this up and improve it by using the sum function and list comprehension that steps by 2, thus giving us only the evens you desire:

sumint n = sum [0,2..n]

Answer 2

Its an operator precedence problem. In Haskell, function application has the highest possible precedence. Thus when you write sumint x - 2, even though you are interpreting it as sumint (x-2), Haskell is interpreting it as (sumint x) - 2. Thus -- you are trying to define sumint x directly in terms of sumint x -- which just piles up recursive function calls until the stack overflows. You need to add explicit parentheses if you want the subtraction evaluated before the function application.