I think you're onto something with the Int/Integer thing....when using a type signature of "Integer", "f 1 113383" gives "248" immediately. Compiling and running the code with "Integer" types on my home machine yields "525".... which Euler says isn't the right answer? Because you're not providing the right number. :-) Also, on the strictness annotations: Do you put them in the type declaration? Or in the pattern match on the lhs of the declaration? I've tested your code with strictness annotations and it appears to not make a difference. GHC employs several optimization techniques, one of
Steve Klabnik wrote: those being strictness analysis, so maybe it is already using a strict, unboxed integer. The real speed-up (a non-linear one) here is not to re-calculate every sequence over and over again, but keep it in a map/array (as suggested by Rafael and me). I've found some Euler puzzles are impossible to solve without this technique. Niels P.S.: If you're really going for speed, compile (not interpret) the code (using -O -fvia-C, and there's some more stuff in the manual) using the latest greatest version of GHC.