{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE Rank2Types #-}
module BaseEffect where
import Data.Functor
import Control.Applicative
import Control.Monad
newtype Parameter = Parameter ()
newtype Return = Return ()
data ExampleEffect a where
IdentitiyBehaviour :: a -> ExampleEffect a
DoSomething :: Parameter (Return -> ExampleEffect a) -> ExampleEffect a
instance Functor (ExampleEffect) where
fmap f x = x >>= \y -> return $ f y
instance Applicative (ExampleEffect) where
pure x = IdentitiyBehaviour $ pure x
(<*>) fab fa = fab >>= \ab -> fa >>= \a -> return $ ab a
instance Monad (ExampleEffect) where
return = pure
(>>=) (DoSomething parameter cc) f =
DoSomething parameter (\ret -> (cc ret) >>= f)
(>>=) (IdentitiyBehaviour ca) f = f ca
doSomething :: Parameter -> ExampleEffect Return
doSomething parameter = DoSomething parameter (\ret -> f ret)
isPendingDoSomething :: forall a. ExampleEffect a -> Bool
isPendingDoSomething (DoSomething _ _) = True
isPendingDoSomething (IdentitiyBehaviour _) = False
getDoSomethingParameter :: forall a. ExampleEffect a -> Maybe Parameter
getDoSomethingParameter (IdentitiyBehaviour _) = Nothing
getDoSomethingParameter (DoSomething parameter _) = Just parameter
resolveDoSomething :: forall c. (Parameter -> Return) -> ExampleEffect c -> Maybe (ExampleEffect c)
resolveDoSomething _ (IdentitiyBehaviour _) = Nothing
resolveDoSomething p2b (DoSomething parameter cc') = Just $ cc' $ p2b parameter
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE Rank2Types #-}
module BaseEffect where
import Data.Functor
import Control.Applicative
import Control.Monad
newtype Parameter = Parameter ()
newtype Return = Return ()
data CommandF next = CommandF Parameter (Return -> CommandF next)
instance Functor (CommandF) where
fmap f (CommandF parameter nexter) = CommandF parameter (f . nexter)
type ExampleEffectFree a = Free CommandF a
Then I note that with equational reasoning the ExampleEffectFreebecomes basically the same as ExampleEffect. Thus I expect the final output of both implementations would have the same performance characteristics.
And makes me think that the complains about Free Monad bad performance is pure nonsense, as for every encoding of a free monad, there is an equivalent regular monad, which has the same performance.
Thus is not the complains about free monad performance nonsense?
data CommandF next = CommandF Parameter (Return -> next)
Free Monads can be poorly performant if you overuse them, for example,
data StateF s a = Put s a | Get (s -> a) deriving Functor
type State = Free StateF
get = Get id
put s = Put s ()
This is much less efficient than the normal
data State = (s -> (s,a))
As it automatically frees up the Get and Put branches, so there is less overhead. However, in your case, and in many cases, what you want has the same structure as the Free monad so there is no reason not to use them. Also, you can use F, defined in the free package, to improve performance.
But the library free \ free-fransformers is not there, which is the base for my reasoning, against the standard library/conventional Monad, which is the claim that I am making: That free monad performance is the same as an standard Monad performance.
If certainly is not pointless with respect to other effect implementations to compare and complain.
Also I noted that different free monad implementations have different performance, and there is a free monad for every monad, where both have the same performance.
freer-simple is generally faster than free. (For details on the optimization techniques, see: Data.FTCQueue and Reflection without remorse: revealing a hidden sequence to speed up monadic reflection.) I have not looked at free-transformers, but I think the situation is probably the same as with free. As a benchmark fact, libraries in the effectful family are faster than freer-simple. In order of speed: free <freer-simple < effectful (greater means faster).
Exactly.
While this may be true, given an arbitrary monad m, I do not think we can mechanically find an f such that Free (Coyoneda f) has equivalent performance to m. If that were possible, we could use it to make free-based libraries as fast as mtl.
Ah, well, thinking it through, this is about a free monad based effect system when you try to use it like mtl, not about the performance of the Free Monad itself.
I will talk about what happens to performance when you try to use the free monad like mtl. When you stack multiple effects ExampleEffect1, ExampleEffect2, …, ExampleEffectN for simultaneous use, you write something like runExampleEffect1 $ runExampleEffect2 $ ... $ runExampleEffectN m. In a typical library implementation, at that point, whenever an instruction that appears in the program m such as DoSomething is executed, the system performs processing equivalent to a linear search over X = 1..N to determine which ExampleEffectX it is. Therefore, each instruction takes O(N) time.
If you do not use it like mtl, in other words you are not thinking of combining multiple effects extensibly and running them in multiple stages and it is enough to handle a single effect GADT at a time, then at least this O(N) slowness does not apply. Even in such single effect cases, whether it is still slower than mtl is not well established as far as I know, since most benchmarks are for effect system style use.