Take this naive definition of Fibonacci sequence:
let rec fib n =
if n < 2I
then 1I
else fib (n-1I) + fib (n-2I)
*Good*: correct, easy to write. *Bad*: performance. Calculates
the same values over and over again.
How about saving up the results? There is this function
I got from Don Syme's blog:
open System.Collections.Generic
let memoize [...]
Problem 10 is about primes again, and it's getting tedious. Thankfully the sieve from Problem 8 can be factored out into a separate module. Now we need to make a correction there - Integer instead of Int, as the numbers are getting large.
import Control.Monad
import Data.Array.ST
import Control.Monad.ST
sieve n
= runSTUArray $
[...]
Problem 9 is a lovely simple problem. The equations can be solved to a closed form to speed the search up. I am totally inept at solving equations, but I have Maxima. So:
(%i1) e1: a + b + c = 1000;
(%o1) [...]
Problem 8 in Haskell is really about I/O. ByteString is great. Fast, lazy, intuitive and monadic I/O. Especially since the latest Parsec can be run on ByteStrings… But no need for that here. Just a simple problem:
module Euler0008 where
import Data.Char
import qualified Data.ByteString.Lazy as BS
ascii0 = ord ‘0′
fives bs | BS.length bs >= 5 = BS.take [...]
Problem 7 is primes again. In Haskell, it is always tempting to have an infinite list of primes and filter it. However, this is not nearly as efficient as the simple sieve. Sieving, however, inherently assumes mutation. This means it requires some dancing in Haskell to get right. The ST monad is one way to [...]
Problem 6: this is really a trivial, but it has prompted me to explore Computer Algebra Systems a bit. For those of us who do not own Maple or Mathematica, there is a free program called Maxima, an ancient fork of commercial LISP-based Maxyma.
Let us solve Problem 6 symbolically:
`maxima
Maxima 5.13.0 http://maxima.sourceforge.net
Using Lisp GNU Common Lisp [...]
The Problem 5 is so easy in Haskell it is just a shame. Seriously, Haskell should have less functions in the Prelude:
euler0005 = foldl1 lcm [1..20]
The efficiency purists would insist at least on this:
euler0005 = Data.List.foldl1′ lcm [1..20]
Problem 4
This problem is slightly interesting as you need to choose what to generate. I chose to generate palindromes, from 999999 downwards, and then check if they can be factorized as two three-digit numbers. As a bonus, there are also functions to compose/decompose a number to a sequence of digits in arbitrary base:
module Euler0004 where
import [...]
Problem 3:
For really efficient prime algorithms (such as Miller-Rabin test) look at Prime numbers). For now a simple garden variety prime test will do.
module Euler0003 where
import Test.QuickCheck
di x y = x `mod` y == 0
primes = 2 : 3 : 5 : filter prime [7, [...]
Problem 2:
Naive Haskell:
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
euler0002 = sum $ filter even $ takeWhile (<= 4000000) fibs
This kind of problems is of course where naive Haskell shines. Define an infinite list recursively and fold it.
Thinking twice about it: there is Binet's formula for fibs, [...]