{-# OPTIONS_GHC -Werror #-}
{-# LANGUAGE Trustworthy #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE TupleSections #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE DataKinds #-}

{-# LANGUAGE CPP #-}

-- | Original work available at <http://okmij.org/ftp/Haskell/extensible/tutorial.html>.
-- This module implements extensible effects as an alternative to monad transformers,
-- as described in <http://okmij.org/ftp/Haskell/extensible/exteff.pdf> and
-- <http://okmij.org/ftp/Haskell/extensible/more.pdf>.
--
-- Extensible Effects are implemented as typeclass constraints on an Eff[ect] datatype.
-- A contrived example can be found under "Control.Eff.Example". To run the
-- effects, consult the tests.
module Control.Eff where

#if __GLASGOW_HASKELL__ < 710
import Control.Applicative
#endif
import safe Data.OpenUnion
import safe Data.FTCQueue
import GHC.Exts (inline)

-- ------------------------------------------------------------------------
-- | A monadic library for communication between a handler and
-- its client, the administered computation
--
-- Effectful arrow type: a function from a to b that also does effects
-- denoted by r
type Arr r a b = a -> Eff r b

arr :: (a -> b) -> Arrs r a b
arr f = tsingleton (Val . f)

ident :: Arrs r a a
ident = arr id

single :: Arr r a b -> Arrs r a b
single = tsingleton

-- FIXME: convert to 'Arrs'
first :: Arr r a b -> Arr r (a, c) (b, c)
first x = \(a,c) -> (, c) `fmap` x a

comp :: Arrs r a b -> Arrs r b c -> Arrs r a c
comp = (><)

-- | An effectful function from 'a' to 'b' that is a composition
-- of several effectful functions. The paremeter r describes the overall
-- effect.
-- The composition members are accumulated in a type-aligned queue
type Arrs r a b = FTCQueue (Eff r) a b

-- | The Eff monad (not a transformer!). It is a fairly standard coroutine monad
-- where the type @r@ is the type of effects that can be handled, and the
-- missing type @a@ (from the type application) is the type of value that is
-- returned.  It is NOT a Free monad! There are no Functor constraints.
--
-- The two constructors denote the status of a coroutine (client): done with the
-- value of type a, or sending a request of type Union r with the continuation
-- Arrs r b a. Expressed another way: an `Eff` can either be a value (i.e.,
-- 'Val' case), or an effect of type @`Union` r@ producing another `Eff` (i.e.,
-- 'E' case). The result is that an `Eff` can produce an arbitrarily long chain
-- of @`Union` r@ effects, terminated with a pure value.
--
-- Potentially, inline Union into E
data Eff r a = Val a
             | forall b. E  (Union r b) (Arrs r b a)

-- | Application to the `generalized effectful function' Arrs r b w
{-# INLINABLE qApp #-}
qApp :: Arrs r b w -> b -> Eff r w
qApp q x =
  case inline tviewl q of
    TOne k  -> k x
    k :| t -> case k x of
      Val y -> qApp t y
      E u q0 -> E u (q0 >< t)

{-
-- A bit more understandable version
qApp :: Arrs r b w -> b -> Eff r w
qApp q x = case tviewl q of
   TOne k  -> k x
   k :| t -> bind' (k x) t
 where
   bind' :: Eff r a -> Arrs r a b -> Eff r b
   bind' (Pure y) k     = qApp k y
   bind' (Impure u q) k = Impure u (q >< k)
-}

-- | Compose effectful arrows (and possibly change the effect!)
{-# INLINE qComp #-}
qComp :: Arrs r a b -> (Eff r b -> Eff r' c) -> Arr r' a c
-- qComp g h = (h . (g `qApp`))
qComp g h = \a -> h $ qApp g a

-- | Eff is still a monad and a functor (and Applicative)
-- (despite the lack of the Functor constraint)
instance Functor (Eff r) where
  {-# INLINE fmap #-}
  fmap f (Val x) = Val (f x)
  fmap f (E u q) = E u (q |> (Val . f)) -- does no mapping yet!

instance Applicative (Eff r) where
  pure = Val
  Val f <*> Val x = Val $ f x
  Val f <*> E u q = E u (q |> (Val . f))
  E u q <*> Val x = E u (q |> (Val . ($ x)))
  E u q <*> m     = E u (q |> (`fmap` m))

instance Monad (Eff r) where
  {-# INLINE return #-}
  {-# INLINE [2] (>>=) #-}
  return x = Val x
  Val x >>= k = k x
  E u q >>= k = E u (q |> k)          -- just accumulates continuations
{-
  Val _ >> m = m
  E u q >> m = E u (q |> const m)
-}

-- | Send a request and wait for a reply (resulting in an effectful
-- computation).
{-# INLINE [2] send #-}
send :: Member t r => t v -> Eff r v
send t = E (inj t) (tsingleton Val)
-- This seems to be a very beneficial rule! On micro-benchmarks, cuts
-- the needed memory in half and speeds up almost twice.
{-# RULES
  "send/bind" [~3] forall t k. send t >>= k = E (inj t) (tsingleton k)
 #-}


{-
-- The opposite of admin, occasionally useful
-- See the soft-cut for an example
-- It is currently quite inefficient. There are better ways
reflect :: VE a r -> Eff r a
reflect (Val x) = return x
reflect (E u) = Eff (\k -> E $ fmap (loop k) u)
 where
 loop :: (a -> VE w r) -> VE a r -> VE w r
 loop k (Val x) = k x
 loop k (E u)   = E $ fmap (loop k) u
-}


-- ------------------------------------------------------------------------
-- | The initial case, no effects. Get the result from a pure computation.
--
-- The type of run ensures that all effects must be handled:
-- only pure computations may be run.
run :: Eff '[] w -> w
run (Val x) = x
-- | the other case is unreachable since Union [] a cannot be
-- constructed.
-- Therefore, run is a total function if its argument terminates.
run (E _ _) = error "extensible-effects: the impossible happened!"

-- | A convenient pattern: given a request (open union), either
-- handle it or relay it.
{-# INLINE handle_relay #-}
handle_relay :: (a -> Eff r w) ->
                (forall v. t v -> Arr r v w -> Eff r w) ->
                Eff (t ': r) a -> Eff r w
handle_relay ret h m = loop m
 where
  loop (Val x)  = ret x
  loop (E u q)  = case decomp u of
    Right x -> h x k
    Left  u0 -> E u0 (tsingleton k)
   where k = qComp q loop

-- | Parameterized handle_relay
{-# INLINE handle_relay_s #-}
handle_relay_s :: s ->
                (s -> a -> Eff r w) ->
                (forall v. s -> t v -> (s -> Arr r v w) -> Eff r w) ->
                Eff (t ': r) a -> Eff r w
handle_relay_s s ret h m = loop s m
  where
    loop s0 (Val x)  = ret s0 x
    loop s0 (E u q)  = case decomp u of
      Right x -> h s0 x k
      Left  u0 -> E u0 (tsingleton (k s0))
     where k s1 x = loop s1 $ qApp q x

-- | Add something like Control.Exception.catches? It could be useful
-- for control with cut.
--
-- Intercept the request and possibly reply to it, but leave it unhandled
-- (that's why we use the same r all throuout)
{-# INLINE interpose #-}
interpose :: Member t r =>
             (a -> Eff r w) -> (forall v. t v -> Arr r v w -> Eff r w) ->
             Eff r a -> Eff r w
interpose ret h m = loop m
 where
   loop (Val x)  = ret x
   loop (E u q)  = case prj u of
     Just x -> h x k
     _      -> E u (tsingleton k)
    where k = qComp q loop