import Prelude hiding (repeat, iterate, concat)

-- List of all Fibonacci numbers:
fibs :: [Integer]
fibs = fibgen 0 1
 where
  fibgen :: Integer -> Integer -> [Integer]
  fibgen fib1 fib2 = fib1 : fibgen fib2 (fib1+fib2)

fib :: Int -> Integer
fib n = fibs !! n


-- Infinite list containing a given value:
repeat :: a -> [a]
repeat x = x : repeat x

-- Infinite list of elements where the subsequent element is changed by
-- some function.
iterate :: (a -> a) -> a -> [a]
iterate f x = x : iterate f (f x)

-- Infinite list of ones --> cyclic list!
ones :: [Int]
ones = 1 : ones

-- no sharing, double evaluation of (fib 100):
fib100Plus :: Integer
fib100Plus = fib 100 + fib 100

-- due to sharing, single evaluation of (fib 100):
fib100Double :: Integer
fib100Double = double (fib 100)
 where double x = x+x

-------------------------------------------------------------------------

-- Arithmetic sequences

-- all ascending numbers:
from :: Int -> [Int]
from n = iterate (+ 1) n

-- all numbers with a given step size:
fromThen :: Int -> Int -> [Int]
fromThen n1 n2 = iterate (+ (n2-n1)) n1

-- all numbers between the two arguments
fromTo :: Int -> Int -> [Int]
fromTo u o = if u>o then [] else u : fromTo (u+1) o

-- all numbers between the two arguments and a step given by the first args:
fromThenTo :: Int -> Int -> Int -> [Int]
fromThenTo n1 n2 o =
  let d = n2 - n1
  in if (d>=0 && n1>o) || (d<0 && n1<o)
       then []
       else n1 : fromThenTo (n1+d) (n2+d) o

{-
[n ..]       ===  from n
[n1,n2 ..]   === fromThen n1 n2
[n .. m]     === fromTo n m
[n1,n2 .. m] === fromThenTo n1 n2 m
-}

{-
-- Type class for enumerable types:
class Enum a where
  succ, pred :: a -> a
  toEnum :: Int -> a
  enumFrom :: a -> [a]                  -- [n..]
  enumFromTo :: a -> a -> [a]           -- [n..m]
  enumFromThen  :: a -> a -> [a]        -- [n1,n2..]
  enumFromThenTo  :: a -> a -> a -> [a] -- [n1,n2..m]

-- Instances exists for Int, Float, Char, Bool, Ordering,...

-- for types with minimal and maximal elements:
class Bounded a where
  minBound, maxBound :: a

-- Instances exists for Int, Char, Bool, Ordering,...
-}

data Color = Red | Yellow | Blue
  deriving (Show, Enum, Bounded)

-- Application: compact definition of factorials:
fac :: Int -> Int
fac n = foldr (*) 1 [1 .. n]

numLines :: [String]
numLines = map (uncurry (++)) (zip (map show [1..]) (repeat ". line"))

-------------------------------------------------------------------------

-- List comprehensions:

odds :: [Int]
odds = [ n | n <- [1 .. 99], odd n]

squareOdds :: [Int]
squareOdds = [ n*n | n <- [1 .. 99], odd n]

pairs :: [(Int,Int)]
pairs = [ (i,j) | i <- [1..10], j <- [5,10 .. 20] ]

prefixes :: [[Int]]
prefixes = [ [0 .. n] | n <- [0..] ]

factorials :: [Int]
factorials = [ foldr (*) 1 [1 .. n] | n <- [1 .. ] ]

triples = [ (x,y,z) | x <- [1..4], y <- [2..6], let z = x*y, x/=y ]

concat :: [[a]] -> [a]
concat xss = [ x | xs <- xss, x <- xs ]