{-
  * Copyright (c): Uwe Schmidt, FH Wedel
  *
  * You may study, modify and distribute this source code
  * FOR NON-COMMERCIAL PURPOSES ONLY.
  * This copyright message has to remain unchanged.
  *
  * Note that this document is provided 'as is',
  * WITHOUT WARRANTY of any kind either expressed or implied.
-}

module RecFct where

import Prelude hiding ( length
                      , product
                      , reverse
                      , zip
                      , even
                      , odd
                      )

import qualified Prelude as P

factorial       :: Integer -> Integer
factorial n
    | n == 0    = 1
    | n >  0    = n * factorial (n - 1)


(.*.) :: Int -> Int -> Int
m .*. n
    | n == 0    = 0
    | n >  0    = m + (m .*. (n - 1))

product          :: Num a => [a] -> a
product []       = 1
product (n : ns) = n * product ns

length          :: [a] -> Int
length []       = 0
length (x : xs) = 1 + length xs

reverse          :: [a] -> [a]
reverse []       = []
reverse (x : xs) = reverse xs ++ [x]

(.++.)           :: [a] -> [a] -> [a]
[]       .++. ys = ys
(x : xs) .++. ys = x : (xs .++. ys)

insert          :: Ord a => a -> [a] -> [a]
insert x []     = [x]
insert x (y : ys)
    | x <= y    = x : y : ys
    | otherwise = y : insert x ys

isort           :: Ord a => [a] -> [a]
isort []        = []
isort (x : xs)  = insert x (isort xs)

zip                     :: [a] -> [b] -> [(a, b)]
zip []        _         = []
zip _        []         = []
zip (x : xs) (y : ys)   = (x,y) : zip xs ys

numberLines    :: [b] -> [(Int, b)]
numberLines xs = zip [1..length xs] xs

fib   :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

even :: Integer -> Bool
even 0 = True
even n = odd (n - 1)

odd :: Integer -> Bool
odd 0 = False
odd n = even (n - 1)

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

type Coins = [Int]

change :: Int -> Coins -> [Coins]
change n cs
  | n <  0 = []
  | n == 0 = [[]]
  | n >  0 = change' cs
  where
    change' []        = []
    change' (c : cs1) = [c : xs | xs <- change (n - c) cs]
                        ++
                        change n cs1

numChanges :: Int -> Coins -> Int
numChanges n cs = length (change n cs)

change1cent :: [Coins]
change1cent = change 1 [50, 20, 10, 5, 2, 1]

change2cent :: [Coins]
change2cent = change 2 [50, 20, 10, 5, 2, 1]

change10cent :: [Coins]
change10cent = change 10 [50, 20, 10, 5, 2, 1]

change1euro :: Int
change1euro = numChanges 100 [50, 20, 10, 5, 2, 1]

-- tests

test1 :: Int -> Coins -> Bool
test1 n cs = all sumEqualsN (change n cs)
  where
    sumEqualsN xs = sum xs == n

test2 :: Int -> Coins -> Bool
test2 n cs = all legalCoins (change n cs)
  where
    legalCoins xs = all (`elem` cs) xs