Non-exhaustive patterns are one thing the compiler can't catch:

  fn 0 = return ()
  main = fn 1

Giving an empty list to head/tail is another:

  main = head []

Speaking of the first example, compiling it with -Wall provides some hints:

  $ ghc --make test.hs -Wall
  test.hs:1:1:
      Warning: Pattern match(es) are non-exhaustive
               In an equation for `fn':
                   Patterns not matched: #x with #x `notElem` [0#]

Wow, that's cool. It even works for non-Bounded argument types, as in fn [0] = 0:

  Warning: Pattern match(es) are non-exhaustive
        In an equation for `fn':
            Patterns not matched:
                []
                #x : _ with #x `notElem` [0#]
                0# : (_ : _)

I'm at school all day, but I'll post something tonight.

OK, so we were learning about greedy algorithms at school and I implemented a very naive implementation of a change making algorithm for Canadian coins. Here's the Haskell code:

    makeChange :: Int -> [Int]
    makeChange amount = loop 0 [200, 100, 25, 10, 5, 1] []
        where loop total coins@(c:cs) solution
                  | total == amount = solution
                  | null coins = error "no solution"
                  | otherwise = if total + c > amount then
                                    loop total cs solution
                                else
                                    loop (total + c) coins (c : solution)

(I could make this a lot better by returning an [(Int, Int)] and by using integer division, but I wanted to just follow the algorithm described in the textbook.)

To make sure that my code was correct, I wrote a QuickCheck property:

    quickCheck (\(Positive n) -> sum (makeChange n) == n)

However, running this after compiling my file with GHC causes a stack overflow and I need to Ctrl+C out of the process.

On the other hand, the exact same algorithm in OCaml runs extremely quick and without a hicup.

quickcheck is running makeChange with an arbitrary Int. maxBound :: Int here is 2147483647. When given a number that large, makeChange recurses a lot, subtracting one two-dollar coin at a time, so you blow the stack. This is where you need to consult a haskell guru to find a way to make your code tail-recursive -- or find a smarter algorithm (using mod c for example so it only needs to recurse 6 times total).

Amusingly, if you simply change the type to Integer -> [Integer], it all works ok. I suspect that since Integers have unbounded size, quickcheck only tests with reasonably small ones.

It's even worse than that if he's on a 64-bit machine!

It runs just fine on my box with i = 2^32: 10s to completion or thereabouts.

However, the way this is written, the code has to construct the entire list in memory before it can print any of it out so for larger lists it is pretty much guaranteed to blow the stack and / or memory depending on the computational representation.

If it was using a snoclist or something then it could stream the output and perform the calculation in constance space, as it stands it has to hold on to the whole list of integers before outputting any of them.

I'm surprised that the OCaML version 'just worked' frankly: either a) the OP didn't use QuickCheck with their OCaML code or b) the OCaML QuickCheck doesn't bother testing across the whole Int space.

Also, a quick test reveals that quickCheck on an Int will by default test 100 Ints across the entire range up to Int::maxbound. If your Ints are 64 bit this really isn't going to work very well on this code, regardless of what language you write it in unless you can stream the output. Any code that holds on to the list is going to fall over, since the size of the list is going to exceed physical memory for larger test values.

The code is already tail recursive, which is why it's doubly puzzling. Also, like you said, using an Integer instead fixes the problem. But I find that fixing these issues distracts me away from the main problem and that doesn't happen in OCaml.