{- CSE 341.  Fixed point examples in Haskell. -}

-- the fix function finds the fixed point of another function
fix :: (t -> t) -> t
fix f = f (fix f)
-- examples to try:
-- fix (const "squid")
-- fix (*2)  ... be ready with control-c on this one

-- the standard factorial funtion
fact1 n = if n==0 then 1 else n*fact1 (n-1)

-- rewritten to use a lambda
fact2 = \n -> if n==0 then 1 else n*fact2 (n-1)

-- if we make fact2 into a parameter of a lambda we remove the recursion:
--       \f -> (\n -> if n==0 then 1 else n*f (n-1))

-- and now we can define a non-recursive version by finding the fixed
-- point of this (the fixed point is the factorial function!)
fact3 = fix (\f -> (\n -> if n==0 then 1 else n*f (n-1)))





-- Let's look at this in another way.  The function that we obtained
-- by making fact2 into a parameter of a lambda might be named
-- improver .... it takes a version of factorial that only
-- works on k inputs, and turns it into a function that works on
-- k+1 inputs.  Here goes:

improver :: (Integer -> Integer) -> (Integer -> Integer)
improver f = \n -> if n==0 then 1 else n*f (n-1)

-- so improver takes a function of type (Integer -> Integer) and returns 
-- another function of the same type.

-- In the type declaration remember that -> is right associative.  So we
-- didn't actually need the extra parens, but they may make it clearer
-- what's going on.  The type declaration could also have been written
-- improver :: (Integer -> Integer) -> Integer -> Integer



-- this function doesn't work on anything!
useless_factorial n = error "sorry, I don't know how to do that"

-- Let's improve it a little, and try it:
--   (improver useless_factorial) 0
--   (improver useless_factorial) 1
--   (improver useless_factorial) 2

-- let's improve it again:
--   (improver (improver useless_factorial)) 0
--   (improver (improver useless_factorial)) 1
--   (improver (improver useless_factorial)) 2

-- and again:
--   (improver (improver (improver useless_factorial))) 0
--   (improver (improver (improver useless_factorial))) 1
--   (improver (improver (improver useless_factorial))) 2
--   (improver (improver (improver useless_factorial))) 3

-- Each time we get a slightly better factorial that works on one more
-- case.  The fixed point of improver is the real factorial function ... if
-- we try to improve the real factorial function, we just get the real
-- factorial function again.