-- haskell notes :)
import System.Random
import Data.List
import Data.Char
import qualified Data.Set as Set
import qualified Data.Sequence as Seq
import Control.Monad.State

fact :: Int -> Int
fact n = if n == 0 then 1 else n * fact(n-1)

fact1 :: Int -> Int 
fact1 0 = 1
fact1 n = n * fact1(n-1)

-- hey steffeeeeeeee

sumSquare :: (Num a) => a -> a -> a
sumSquare x y = x^2 + y^2

-- [Int] === List<Int>

--myMap :: (Int -> Double) -> [Int] -> [Double], not general enough
myMap :: (a -> b) -> [a] -> [b]
myMap f lst = if null lst then [] else (f (head lst)):(myMap f (tail lst))

myMap1 :: (a -> b) -> [a] -> [b]
myMap1 f [] = []
myMap1 f (x:xs) = (f x):(myMap1 f xs)

sort1 :: (Ord a) => [a] -> [a]
sort1 [] = []
sort1 (x:xs) = (sort1 (filter (< x) xs)) ++ [x] ++ (sort1 (filter (>= x) xs))
  
sort2 :: (Ord a) => [a] -> [a]
sort2 [] = []
sort2 (x:xs) = (sort2 smaller) ++ [x] ++ (sort2 bigger)
  where (smaller,bigger) = partition (< x) xs
        

--fun with laziness
fibs :: [Integer]
fibs = 0:1:(zipWith (+) fibs (tail fibs))

exists :: (a -> Bool) -> [a] -> Bool
exists pred lst = not (null (filter pred lst))

-- exists even [1,2,3,4,5,6,7] = not (null (filter even [1,2,3,4,5,6,7]))
-- = not (null (filter even [2,3,4,5,6,7])) 
-- = not (null 2:(filter even [3,4,5,6,7])) = True

divides :: Integer -> Integer -> Bool
n `divides` m = 0 == m `mod` n

primes :: [Integer]
primes = 2:(filter isPrime [3..])

isPrime :: Integer -> Bool 
isPrime n = [n] == (factor2 n)

factor :: Integer -> [Integer]
factor n = fhelp n primes
  where fhelp n (p:ps) = if (n < p*p) then [n] else 
                           if (p `divides` n) then p:(factor (div n p)) 
                           else fhelp n ps
        

findFactor :: Integer -> Maybe Integer
findFactor n = find (`divides` n) (takeWhile (\p -> n >= p^2) primes)

factor2 :: Integer -> [Integer]
factor2 n = case findFactor n of
  (Just p) -> p:(factor2 (n `div` p))
  Nothing -> [n]


foo n = Just (bar n)
  where bar n = bar (n-1)
        
isJust (Just _) = True
isJust Nothing = False

data List a = EmptyList | Node a (List a) deriving (Show)

myListMap :: (a -> b) -> List a -> List b
myListMap f EmptyList = EmptyList
myListMap f (Node x xs) = Node (f x) (myListMap f xs)

data Tree a = TreeNode a (Tree a) (Tree a) | Leaf deriving (Show)

binarySearch :: Int -> Tree Int -> Maybe (Tree Int)
binarySearch obj Leaf = Nothing
binarySearch obj (TreeNode obj2 left right) = if obj == obj2 then Just (TreeNode obj2 left right)
                                              else if obj < obj2 then binarySearch obj left
                                                   else binarySearch obj right

listToBinaryTree :: [Int] -> Tree Int
listToBinaryTree [] = Leaf
listToBinaryTree (x:xs) = TreeNode x (listToBinaryTree smaller) (listToBinaryTree bigger)
  where (smaller,bigger) = partition (<x) xs
        
binarySearchExists :: Int -> Tree Int -> Bool
binarySearchExists obj tree = case binarySearch obj tree of
  Nothing -> False
  _ -> True

data Suit = Club | Diamond | Heart | Spade  deriving (Ord,Enum, Bounded)
data Rank = Two | Three | Four | Five | King | Ace deriving (Eq, Show) -- too lazy to write em all out....
data Card = Card Rank Suit | Joker1 | Joker2 deriving (Eq)
data Hand = Hand Card Card Card Card Card deriving (Eq)

instance Show Suit where
  show Club = "C"
  show Diamond = "D"
  show Heart = "H"
  show Spade = "S"

instance Eq Suit where
  Club == Club = True
  Club == _ = False
  Diamond == Diamond = True
  Diamond == _ = False
  Heart == Heart = True
  Heart == _ = False
  Spade == Spade = True
  Spade == _ = False
  
myLess :: (Ord a) => a -> a -> Bool
myLess x y = x < y

myPlus :: (Num a) => a -> a -> a
myPlus x y = x + y

data Foo = Foo Int | Bar Double

instance Show Foo where
  show (Foo n) = "weee " ++ (show n)
  show (Bar n) = "I am bar " ++ (show n)

data Vect3d a = Vect3d a a a 

instance (Show a) => Show (Vect3d a) where
  show (Vect3d x y z) = "<"++(show x) ++ "," ++ (show y) ++ "," ++ (show z) ++ ">"
  
instance (Eq a) => Eq (Vect3d a) where
  (Vect3d x y z) == (Vect3d x' y' z') = and (zipWith (==) [x,y,z] [x',y',z'])
  
vect3dToList (Vect3d a b c) = [a,b,c]
listToVect3d [a,b,c] = (Vect3d a b c)
  
instance (Num a) => Num (Vect3d a) where
  (Vect3d x y z) + (Vect3d x' y' z') = listToVect3d (zipWith (+) [x,y,z] [x',y',z'])
  negate (Vect3d x y z) = listToVect3d (map negate [x,y,z])
  (Vect3d x y z) * (Vect3d x' y' z') = error "this typeclass is wrong"
  abs _ = error "..."
  signum _ = error "..."
  fromInteger 0 = Vect3d 0 0 0
  fromInteger _ = error "no cannonical Z embedding"
    
class Group g where
  ($+$) :: g -> g -> g
  gzero :: g
  gnegate :: g -> g
  
instance  Group Int where
  x $+$ y = x + y
  gzero = 0
  gnegate = negate
  








  
whatever :: Int -> IO Int
whatever n = fmap (\_ -> n+1) (putStrLn ("Hey, the number was " ++ (show n)))

getLengthOfInput :: IO Int
getLengthOfInput = fmap length getLine

--fmap :: (a -> b) -> f a -> f b

instance Functor Tree where
  fmap f Leaf = Leaf
  fmap f (TreeNode x left right) = (TreeNode (f x) (fmap f left) (fmap f right))

safeDivide :: Double -> Double -> Maybe Double 
safeDivide _ 0 = Nothing
safeDivide a b = Just (a/b)

safeInvert x = safeDivide 1 x

pathA x = x + 2 
pathB x = x*2
pathC x = x-1

-- fmap :: (a -> b) -> (Maybe a) -> (Maybe b)
-- (>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b


fooy :: (Maybe Double) -> (Maybe Double) -> Maybe Double
fooy x y = x' >>= (\a -> y' >>= (\b -> safeDivide a b))
  where x' = fmap pathB (fmap pathA x)
        y' = fmap pathC y     
       
        
whatDidISay :: IO String
whatDidISay = getLine >>= (\line -> putStrLn ("you just said " ++ line) >> (return line))

promptSayWhat :: IO String
promptSayWhat = (putStrLn "please say something") >> whatDidISay

-- Functor takes a type gives a type
-- fmap :: (Functor f) => (a -> b) -> (f a) -> (f b)

-- Monad takes a type gives a type (a Monad is always a Functor)
-- (>>=) :: (Monad m) => (m a) -> (a -> m b) -> (m b)
-- return :: (Monad m) => a -> m a

-- fmap f a = a >>= (\x -> return (f x))


-- yaaay



instance Show (IO a) where
  show x = "I am an IO action"
  


mySequence :: (Monad m) => [m a] -> m [a]
mySequence [] = return []
mySequence (x:xs) = x >>= 
                    \x' -> mySequence xs >>=
                    \xs' -> return (x':xs')      
                            
myMapM f lst = mySequence (map f lst)
myMapM_ f lst = myMapM f lst >> return ()

data MyState s a = MyState (s -> (s,a))

instance Functor (MyState s) where
  fmap f (MyState sf) = MyState sf'
    where sf' s = (a, f b)
            where (a,b) = sf s

instance Monad (MyState s) where
  (MyState curstate) >>= f = MyState newstate
    where newstate s = state' s'
            where (s',a') = curstate s
                  (MyState state') = f a'
  return a = MyState (\s -> (s,a))
  
myGet :: MyState a a
myGet = MyState (\s -> (s,s))

myPut :: b -> (MyState b ())
myPut x = MyState (\s->(x,()))

myModify :: (a -> a) -> MyState a ()
myModify f = myGet >>= (\x -> myPut (f x))

getCounter :: MyState Int Int
getCounter = myGet

incCounter = myModify (+1)

nextCounter :: MyState Int Int
nextCounter = getCounter >>= 
              \c -> incCounter >>
              return c
              
myRunState :: MyState a b -> a -> (a,b)
myRunState (MyState s) init = s init
myEvalState :: MyState a b -> a -> b
myEvalState s i = snd(myRunState s i)
                              
countAs str = (myEvalState (someState >> myGet) 0)
  where someState = mapM_ (\x -> if x=='a' then incCounter else return ()) str