factorial :: Integer -> Integer
factorial n = if n < 2 then 1 else n * factorial (n-1)

-- Infinite lists are fun.

fibo_like :: Integer -> Integer -> [Integer]
fibo_like a b = a : fibo_like b (a+b)

fibonacci, lucas :: [Integer]
fibonacci = fibo_like 0 1
lucas = fibo_like 2 1

{- to look at them, take some finite prefix:
> take 15 fibonacci
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377]
-}


-- The classic example: the primes.
-- Note the recursion on the list itself.

primes :: [Integer]
primes = 2 : [ p | p <- [3,5..], isprime p ]
    where isprime p = all (\d -> p `mod` d /= 0) $
                      takeWhile (\d -> d*d <= p) primes

{- or for the line-count purists:
primes = 2 : [ p | p <- [3,5..], nodivs p (takeWhile (\d -> d*d <= p) primes)]
    where nodivs p ds = all (\d -> p `mod` d /= 0) ds
-}


{-
Now, write your own favorite sequence.
You could try
- the Catalan numbers
- the partition function; more complicated
- the binomial coefficients (probably just as a function)
-}