module Partial where

data D a = Now a | Later (D a) -- codata

instance Show a => Show (D a) where
   show (Now a) = show a
   show (Later d) = "." ++ show d

never :: D a
never = Later never

instance Monad D where
    return = Now
    Now a   >>= k = k a
    Later d >>= k = Later (d >>= k)

rep :: (a -> D (Either b a)) -> a -> D b
rep k a = k a >>= \ ba ->
		      case ba of
		        Left b -> Now b
			Right a -> Later (rep k a)

while :: (a -> D Bool) -> (a -> D a) -> a -> D a
while g k = rep (\ a -> g a >>= \ b ->
                        if b then (k a >>= \ a' -> return (Right a')) 
                        else return (Left a))

untl :: (a -> D a) -> (a -> D Bool) -> a -> D a 
untl k g = rep (\ a -> k a >>= \ a' ->
                       g a' >>= \ b ->  
                       return (if b then Left a' else Right a')) 

lfp :: ((a -> D b) -> (a -> D b)) -> a -> D b
-- to be completed

-- some examples using lfp


fib :: Integer -> D Integer
fib = lfp (\ fib -> \ n -> 
              if n == 0 then return 0
              else if n == 1 then return 1
	      else do x <- fib (n-1)
		      y <- fib (n-2)
		      return (x+y)
           )

fact :: Integer -> D Integer
fact = lfp (\ fact -> \ n -> 
              if n == 0 then return 1
	      else do x <- fact (n-1)
		      return (x * n)
           )