import Control.Applicative

data Expr = Con Float
          | Add Expr Expr | Sub Expr Expr
          | Mul Expr Expr | Div Expr Expr
          deriving (Eq, Show)

eval0 :: Expr -> Float
eval0 (Con x) = x
eval0 (Add x y) = eval0 x + eval0 y
eval0 (Sub x y) = eval0 x - eval0 y 
eval0 (Mul x y) = eval0 x * eval0 y
eval0 (Div x y) = eval0 x / eval0 y

eval1 :: Expr -> Maybe Float
eval1 (Con x) = Just x
eval1 (Add x y) = apply (+) (eval1 x) (eval1 y)
eval1 (Sub x y) = apply (-) (eval1 x) (eval1 y)
eval1 (Mul x y) = apply (*) (eval1 x) (eval1 y)
eval1 (Div x y) = apply (/) (eval1 x) yy
  where yy = if eval1 y == Just 0 
                then Nothing
                else eval1 y

apply :: (Float -> Float -> Float) -> Maybe Float -> Maybe Float -> Maybe Float
apply f (Just x) (Just y) = Just $ f x y
apply _ _ _ = Nothing

eval2 :: Expr -> Maybe Float
eval2 (Con x) = Just x
eval2 (Add x y) = (+) <$> eval2 x <*> eval2 y
eval2 (Sub x y) = (-) <$> eval2 x <*> eval2 y 
eval2 (Mul x y) = (*) <$> eval2 x <*> eval2 y
eval2 (Div x y) = (/) <$> eval2 x <*> yy
  where yy = if eval2 y == Just 0
                then Nothing
                else eval2 y

eval3 :: Expr -> Maybe Float
eval3 (Con x) = Just x
eval3 (Add x y) = liftA2 (+) (eval3 x) (eval3 y)
eval3 (Sub x y) = liftA2 (-) (eval3 x) (eval3 y)
eval3 (Mul x y) = liftA2 (*) (eval3 x) (eval3 y)
eval3 (Div x y) = liftA2 (/) (eval3 x) yy
  where yy = if eval3 y == Just 0
                then Nothing
                else eval3 y

data Possibly a = None
                | Once a
                | Twice a a
                deriving (Eq, Ord, Show, Read)

instance Functor Possibly where
  fmap _ None = None
  fmap f (Once x) = Once (f x)
  fmap f (Twice x y) = Twice (f x) (f y)

instance Applicative Possibly where
  pure = Once
  None <*> _ = None
  (Once f) <*> x = fmap f x
  (Twice _ _) <*> None = None
  (Twice f g) <*> (Once x) = Twice (f x) (g x)
  (Twice f g) <*> (Twice x y) = Twice (f x) (g y)