import Prelude hiding ((++), last, concat, (!!), fst, snd,
zip, unzip, map, foldr, filter)
infixr 5 ++
fac :: Integer -> Integer
fac n | n >= 0 = fac' n
where fac' :: Integer -> Integer
fac' 0 = 1
fac' n = n * fac' (n-1)
fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
fibEff :: Integer -> Integer
fibEff n = fibHelp n 0 1
where fibHelp :: Integer -> Integer -> Integer -> Integer
fibHelp 0 res1 _ = res1
fibHelp n res1 res2 = fibHelp (n-1) res2 (res2+res1)
isPrime :: Integer -> Bool
isPrime n = n/=1 && checkDiv (n `div` 2)
where checkDiv :: Integer -> Bool
checkDiv m = m == 1 || n `mod` m /= 0 && checkDiv (m - 1)
data Tree a = Node (Tree a) a (Tree a)
| Empty
deriving Show
{-
-- GADT style
data Tree a where
Node :: Tree a -> a -> Tree a -> Tree a
Empty :: Tree a
-}
test_tree :: Tree Integer
test_tree = Node (Node Empty 3 Empty) 5 (Node (Node Empty 9 Empty) 3 (Node Empty 2 Empty))
height :: Tree a -> Int
height Empty = 0
height (Node tl _ tr) = max (height tl) (height tr) + 1
data List a = Nil
| Cons a (List a)
{-
data [a] = [] | a : [a]
-}
(++) :: [a] -> [a] -> [a]
[] ++ ys = ys
(x:xs) ++ ys = x : xs ++ ys
treeToList :: Tree a -> [a]
treeToList Empty = []
treeToList (Node tl v tr) = treeToList tl ++ [v] ++ treeToList tr
{-
data Maybe a = Nothing | Just a
-}
isNothing :: Maybe a -> Bool
isNothing Nothing = True
isNothing (Just _) = False
head :: [a] -> a
head (x:_) = x
last :: [a] -> a
--last xs = head (reverse xs)
last [x] = x
last (_:xs) = last xs
concat :: [[a]] -> [a]
concat [] = []
concat (xs:xss) = xs ++ concat xss
(!!) :: [a] -> Int -> a
(x:_) !! 0 = x
(_:xs) !! n = xs !! (n - 1)
type String = [Char]
--data (,) a b = (,) a b
--data () = ()
fst :: (a,b) -> a
fst (x,_) = x
snd :: (a,b) -> b
snd (_,x) = x
zip :: [a] -> [b] -> [(a,b)]
zip [] _ = []
zip _ [] = []
zip (x:xs) (y:ys) = (x,y) : zip xs ys
unzip :: [(a,b)] -> ([a],[b])
unzip [] = ([],[])
unzip ((x,y):xys) = let (xs,ys) = unzip xys in
(x:xs,y:ys)
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr _ e [] = e
foldr f e (x:xs) = x `f` (foldr f e xs)
foldTree :: (b -> a -> b -> b) -> b -> Tree a -> b
foldTree _ e Empty = e
foldTree f e (Node tl v tr) = f (foldTree f e tl) v (foldTree f e tr)
flip :: (a -> b -> c) -> b -> a -> c
flip f x y = f y x
(.) :: (b -> c) -> (a -> b) -> a -> c
(f . g) x = f (g x)
filter :: (a -> Bool) -> [a] ->[a]
--filter _ [] = []
--filter p (x:xs) | p x = x : filter p xs
-- | otherwise = filter p xs
--filter p = foldr (\x ys -> if p x then x:ys else ys) []
filter p = foldr (\x -> if p x then (x:) else id) []
{-
class Eq a where
(==), (/=) :: a -> a -> Bool
x /= y = not x == y
x == y = not x /= y
-}
instance Eq a => Eq (Tree a) where
Empty == Empty = True
(Node tl1 v1 tr1) == (Node tl2 v2 tr2) = v1 == v2 && tl1 == tl2 && tr1 == tr2
_ == _ = False
infTree1 = Node infTree1 42 infTree1
infTree2 = Node infTree2 73 infTree2
nats :: Int -> [Int]
nats n = n : nats (n + 1)
primes :: [Int]
primes = sieve (nats 2)
sieve :: [Int] -> [Int]
sieve (p : ns) = p : sieve (filter (\n -> n `mod` p /= 0) ns)
list = [(i,j) | i <- [1..4], j <- [3..6], i /= j ]
main = do
putStr "Hello "
putStrLn "students,"
text <- getLine
putStrLn ("You wrote: " ++ text)
putStrLn ("Yes, thats, what you really wrote: " ++ text)