-- Aufgabe 19

import Control.Monad

list1 = [ (x,y,z) | x <- [1..], let y = [1..x], z <- map (+1) y, 2*x >= z ]

list2 = do
  x <- [1..]
  let y = [1..x]
  z <- map (+1) y
  guard (2*x >= z)
  return (x,y,z)

list3 = 
  [1..] >>= \x -> 
  let y = [1..x] in
  map (+1) y >>= \z ->
  guard (2*x >= z) >>
  return (x,y,z)

-- Aufgabe 21

data Exp = Var Int | Abs Int Exp | App Exp Exp

eval :: Exp -> Exp
eval e
  = case reduce e of
      Nothing -> e
      Just e' -> eval e'    

reduce :: Exp -> Maybe Exp
reduce (Var n) = Nothing
reduce (Abs n e) = reduce e >>= return . Abs n
reduce (App (Abs n e1) e2) = return (subst n e2 e1)
reduce (App e1 e2)
  = case reduce e1
      Nothing -> reduce e2 >>= return . App e1
      Just e -> return (App e e2)

subst :: Int -> Exp -> Exp -> Exp
subst v f (Var n) = if n == v then f else Var n
subst v f (App e e') = App (subst v f e) (subst v f e')
subst v f (Abs x e)
  | x == v = Abs x e
  | not (x `elem` free f) = Abs x (subst v f e)
  | otherwise = let y = fresh (v:free e++free f)
                 in Abs y (subst v f (subst x (Var y) e))

free :: Exp -> [Int]
free (Var x) = [x]
free (Abs x e) = filter (/=x) $ free e
free (App e1 e2) = free e1 ++ free e2

fresh :: [Int] -> Int
fresh ns = head $ filter (not . (`elem` ns)) [0..]