{-

  Max Sherman
  CSE 341
  Section 4

  Todo:
  1. HW questions
  2. Warmup writing functions identifying types
  3. List comprehensions
  4. fold
  5. Type definitions

-}

import Data.Char

-- (me to remind on syntax) write map
-- what is type?

-- (them) write map2
-- what is type?

-- (them write compose
compose f g x = f $ g x -- or f (g x)
-- what is type?

-- List comprehensions
-- (me) the list of squares of even numbers
evenSquares = [x^2 | x <- [1..], mod x 2 == 0]
-- cartesian product: [1..n]^2    (together)
cart n = [(a,b) | a <- [1..n], b <- [1..n]]
-- (me) fibonacci numbers
fibs = 0 : 1 : [i + j | (i,j) <- zip fibs (tail fibs)]

-- (them) write a function that takes an int n and returns all pairs (i,j) where
-- i and j are coprime, and i <= n and j <= n.  Use a list comprehension, gcd
-- function
coprimes n = [(i, j) | i <- [1..n], j <- [1..n], gcd i j == 1]


-- fold
-- what is fold?
myfoldr f b [] = b
myfoldr f b (x:xs) = f x (myfoldr f b xs)

-- fold (+) 0 (1 : 2 : 3 : []) -->
-- 1 + (2 + (3 + 0))
-- so essentially replace the ':' with '+', and the '[]' with 0
-- what is the type?

-- sum (me) -- easy because both of the arguments to (+) have the same type

-- reverse (them)
revlist lst = myfoldr (\x y -> y ++ [x]) [] lst

-- map
mymap f lst = myfoldr (\x y -> f x : y) [] lst

-- write a partition function that takes a list and returns a 2-tuple where the
-- first element contains a list with half the elements of the original list in it,
-- and the second element contains a list with the OTHER half of the elements
-- of the original list in it
partition lst = myfoldr (\x (a,b) -> (b, x : a)) ([], []) lst


-- algebraic datatypes

-- let's make natural numbers: [0..]
data Nat = O | S Nat

instance Show Nat where
  show O = "0"
  --show (S n) = "S" ++ show n
  show (S n) = show (1 + read (show n))

-- if we really wanted to we could define a read instance for Nat as well

-- pred is the function that subtracts one
mypred :: Nat -> Nat
mypred O = O -- kinda bogus
mypred (S n) = n

-- we can fix the O case with option types
data Option a = None | Some a deriving (Show)

mypred' :: Nat -> Option Nat
mypred' O = None
mypred' (S n) = Some n

-- (them) write add
add :: Nat -> Nat -> Nat
add O m = m
add (S n) m = S (add n m)

-- (them) write multiply, hint: use add
mult :: Nat -> Nat -> Nat
mult O m = O
mult (S n) m = add m (mult n m)

-- sweet
two = (S (S O))
three = add two (S O)
five = add two three
fifteen = mult three five

-- how can we write our own list?
data MyList a = Nil | Cons (a, (MyList a)) deriving (Eq,Show)
-- if time write a better show for this

exlst = Cons (3, (Cons (4, (Cons (5, Nil)))))

-- (them) map w new list type
coolmap :: (a -> b) -> MyList a -> MyList b
coolmap f Nil = Nil
coolmap f (Cons (x,xs)) = (Cons (f x, coolmap f xs))

-- if time do tail recursive append w the new list type