inf1 :: Int
inf1 = inf1+1

f1 :: Int -> (Int -> Int)
f1 0 _ = 0
f1 _ 0 = 0
f1 _ _ = 1

data Nats = Zero | Succ Nats deriving Show

inf2 :: Nats
inf2 = Succ inf2

f2 :: Nats -> Nats -> Nats
f2 Zero _ = Zero
f2 _ Zero = Zero
f2 _ _    = Succ Zero

cartesian :: Int -> Int -> [(Int,Int)]
-- cartesian 2 3 should give [(1,1),(1,2),(1,3),(2,1),(2,2),(2,3)]
cartesian x y = cartesian' x y y where
  cartesian' 0     _ _ = []
  cartesian' (n+1) 0 a = cartesian' n a a
  cartesian' n     m a = (n,m) : cartesian' n (m-1) a

curry3 :: ((a,b,c) -> d) -> (a -> (b -> (c -> d)))
curry3 f x y z = f (x,y,z)

uncurry3 :: (a -> (b -> (c -> d))) -> ((a,b,c) -> d)
uncurry3 f (x,y,z) = f x y z

data List a = Nil | Cons a (List a) deriving Show
test = Cons 1 (Cons 2 (Cons 3 Nil))

sqrList :: List Integer -> List Integer
sqrList Nil = Nil
sqrList (Cons x xs) = Cons (x*x) (sqrList xs)

doubleList Nil = Nil
doubleList (Cons x xs) = Cons (x+x) (doubleList xs)

square x = x*x
double x = x+x

mapList :: (a -> b) -> List a -> List b
mapList _ Nil = Nil
mapList f (Cons x xs) = Cons (f x) (mapList f xs)

sqrList2 = mapList square
doubleList2 = mapList double

data BinTree a = Leaf | Node a (BinTree a) (BinTree a) deriving Show
test1 = Node 'D' (Node 'B' (Node 'A' Leaf Leaf) (Node 'C' Leaf Leaf)) (Node 'I' (Node 'E' Leaf (Node 'G' (Node 'F' Leaf Leaf) (Node 'H' Leaf Leaf))) Leaf)
test2 = Node 2 (Node 1 Leaf Leaf) (Node 3 Leaf Leaf)

doubleAsList x = [x,x]

mapTree :: (a -> b) -> BinTree a -> BinTree b
mapTree _ Leaf = Leaf
mapTree f (Node x left right) = Node (f x) (mapTree f left) (mapTree f right)

sumList Nil = 0
sumList (Cons x xs) = x+sumList xs

prodList Nil = 1
prodList (Cons x xs) = x*prodList xs

foldList :: (a -> b -> b) -> b -> List a -> b
foldList _ g Nil = g
foldList f g (Cons x xs) = f x (foldList f g xs)

sumList2 = foldList (\x y -> x + y) 0
prodList2 = foldList (\x y -> x * y) 1

sumTree Leaf = 0
sumTree (Node x left right) = x+(sumTree left)+(sumTree right)

foldTree :: (a -> b -> b -> b) -> b -> BinTree a -> b
foldTree _ g Leaf = g
foldTree f g (Node x left right) = f x (foldTree f g left) (foldTree f g right)

prodTree = foldTree (\x y z -> x * y * z) 1

filterList :: (a -> Bool) -> List a -> List a
filterList _ Nil = Nil
filterList p (Cons x xs) | p x = Cons x ys
                         | otherwise = ys where
  ys = filterList p xs

filterTree :: (a -> Bool) -> BinTree a -> BinTree a
filterTree _ Leaf = Leaf
filterTree p (Node x left right) | p x = Node x (filterTree p left) (filterTree p right)
                                 | otherwise = error "sorry :("

zipWithList :: (a -> b -> c) -> List a -> List b -> List c
zipWithList _ Nil _   = Nil
zipWithList _ _   Nil = Nil
zipWithList f (Cons x xs) (Cons y ys) = Cons (f x y) (zipWithList f xs ys)

data Tree a = Trode a [Tree a] deriving Show

test3 = Trode 1 [Trode 2 [], Trode 3 [], Trode 4 [Trode 6 [], Trode 7 []], Trode 5 []]

mapTrode :: (a -> b) -> Tree a -> Tree b
mapTrode f (Trode x ts) = Trode (f x) (map (mapTrode f) ts)