{- CSE 341 - answers for Mini-exercises #3 -}

fix :: (t -> t) -> t
fix f = f (fix f)


-- Questions 1 and 2 -- try them and see!

-- Question 3 -- the range function in Haskell (recursive version)

range 0 = []
range n = n : range (n-1)

-- Question 4 -- non-recursive version of range in Haskell
range2 = fix (\f -> (\n -> if n==0 then [] else n : f (n-1)))

{- Racket versions (Questions 5 and 6):

(define (range n)
  (if (zero? n) '() (cons n (range (- n 1)))))



(define Y
  (lambda (f)
    ((lambda (x) (f (lambda (v) ((x x) v))))
     (lambda (x) (f (lambda (v) ((x x) v)))))))


(let ((range (Y (lambda (f)
                 (lambda (n)
                   (if (zero? n)
                       '()
                       (cons n (f (- n 1)))))))))
      (range 4))
  
-}

-- here are the functions used for Question 7:

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

fact3 = fix improver

pathetic_factorial n = case n of
        0 -> 1
        1 -> 1
        2 -> 2
        3 -> 6
        4 -> 24
        _ -> error "sorry, I don't know how to compute that"

{- Then you can copy and paste these expressions into Haskell to see
what they evaluate to: 

  improver pathetic_factorial 0
  improver pathetic_factorial 1
  improver pathetic_factorial 2
  improver pathetic_factorial 3
  improver pathetic_factorial 4
  improver pathetic_factorial 5
  improver pathetic_factorial 6

Ta-da!  We get a slightly less pathetic factorial function, that also
works on 5.  If we feed our slightly less pathetic function into
improver again, we'd get a factorial that also works on 6.  If you
keep doing this indefinitely, you get the fixed point, which is the
actual factorial function.

-}