Git Product home page Git Product logo

free's Introduction

free

Hackage Build Status

This package provides a common definitions for working with free monads, free applicatives, and cofree comonads in Haskell.

Contact Information

Contributions and bug reports are welcome!

Please feel free to contact me through github or on the #haskell IRC channel on irc.freenode.net.

-Edward Kmett

free's People

Contributors

alexfmpe avatar aristidb avatar bafain avatar carbolymer avatar chowells79 avatar dalaing avatar ekmett avatar elvishjerricco avatar fizruk avatar fumieval avatar fuuzetsu avatar glguy avatar gurkenglas avatar hvr avatar jwiegley avatar mdimjasevic avatar mitchellwrosen avatar ocharles avatar phadej avatar pozorvlak avatar prophile avatar robrix avatar ryanglscott avatar strake avatar supki avatar taneb avatar ttuegel avatar tuplanolla avatar viercc avatar vlopezj avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

free's Issues

Faster Free Applicatives

Dave Menendez has written two articles on how to make faster free applicatives with Church encoding. He has benchmarks showing his final solution, B2, is much faster (O(n) instead of O(n²)). It can also become a free Alternative by changing z in the solution to (z -> z), the same way the CPS list monad works.

Add hoistCofree

Please forgive me if this is already defined somewhere--I couldn't find a precise match--but this function would be useful to have:

hoistCofree :: (Functor f) => (forall x . f x -> g x) -> Cofree f a -> Cofree g a
hoistCofree f (x :< y) = x :< f (hoistCofree f <$> y)

Add retractT

Pipes.Group has

concats :: Monad m => FreeT (Producer a m) m x -> Producer a m x

which could generalize to

retractT :: (MonadTrans t, Monad m) => FreeT (t m) m x -> t m x

Alternately we might work with a monad homomorphism instead.

Church-encoded free monad transformer + recursion schemes

Code here

This is a first attempt at a Church-encoded free monad transformer, represented by the type:

newtype FT f m a = FT { runFT :: forall r. (a -> m r) -> (f (m r) -> m r) -> m r }

The module includes equivalents of hoistFreeT and transFreeT from Control.Monad.Trans.Free.

There are also three recursion schemes:

cataFT :: (a -> m b) -> (f (m b) -> m b) -> FT f m a -> m b
cataFT kp kf ft = runFT ft kp kf

foldFT :: (Traversable f, Monad m) => (a -> m b) -> (f b -> m b) -> FT f m a -> m b
foldFT kp kf = cataFT kp $ kf <=< sequence

sequenceFT :: (Traversable f, Monad m, MonadFree f n) => FT f m a -> m (n a)
sequenceFT = foldFT (return . return) (return . wrap)

The code also adds analogues of these recursion schemes for the existing FreeT class. The isomorphism of FreeT and FT is witnessed by the functions toFreeT and fromFreeT.

If the cataFT and cataFreeT definitions can be moved to a type class for free monad transformers (the transformer version of MonadFree), the recursion schemes can be written generically. I'm not sure if this is a good design choice.

There are some more functions in the control-monad-free package not yet included in free. I think it would be worth porting over those that are likely to be useful.

(Note: This code is a first draft. There are only the bare minimum of type class instances, no documentation, and not very good names for the new types and functions.)

Change semantics for IterT's Alternative and MonadPlus instances

These are the current instances for IterT of Alternative and MonadPlus. Both of them were added when the Iter module was first commited; they are equivalent to the ones that would be created by GeneralizedNewtypeDeriving.

instance MonadPlus m => Alternative (IterT m) where
  empty = IterT mzero
  {-# INLINE empty #-}
  IterT a <|> IterT b = IterT (mplus a b)
  {-# INLINE (<|>) #-}
instance MonadPlus m => MonadPlus (IterT m) where
  mzero = IterT mzero
  {-# INLINE mzero #-}
  IterT a `mplus` IterT b = IterT (mplus a b)
  {-# INLINE mplus #-}

In Capretta's slides, a race function is defined. It tries several approaches for the same result (some of them, maybe non terminating), and the earliest one to succeed is picked out. Venanzio b is equivalent to Iter b.

race :: Venanzio b -> Venanzio b -> Venanzio b 
race (Now b0) _ = Now b0
race (Later _) (Now b1) = Now b1
race (Later c0) (Later c1) = Later (race c0 c1)

If race is generalized to the IterT m b, the following instances can be defined. They are analogous to the ones for the MaybeT transformer, and satisfy the same subset of laws : namely, monad plus with left catch.

instance (Monad m) => Alternative (IterT m) where
  empty = never
  {-# INLINE empty #-}
  (<|>) = mplus 
  {-# INLINE (<|>) #-}
instance (Monad m) => MonadPlus (IterT m) where
  mzero = never
  x `mplus` y = IterT $ do
    x' <- runIterT x
    case x' of
      l@(Left _) -> return l
      Right a -> do
        y' <- runIterT y
        case y' of
          l@(Left _) -> return l
          Right b    -> return . Right $ a <|> b

These new semantics might be more useful, but they would break the API.

`free` does not compile against `base-4.5.0.0`

The error is pretty straightforward:

src/Control/Monad/Free.hs:222:3:
    foldl' is not a (visible) method of class `Foldable'

src/Control/Monad/Free.hs:227:14:
    foldl' is not a (visible) method of class `Foldable'

You would either need to increase the lower bound on base or guard the implementation of foldl' in a CPP pragma.

MonadWriter instances for IterT and FreeT

I am totally not sure about implementation of pass function.
Otherwise MonadWriter instance for IterT seems correct.
Perhaps it can be rewritten in more concise form.

instance (Functor m, MonadWriter w m) => MonadWriter w (IterT m) where
  tell = lift . tell
  listen (IterT m) = IterT . liftM concat' $ listen (fmap listen `liftM` m)
    where
      concat' (Left  x, w) = Left (x, w)
      concat' (Right y, w) = Right $ second (w <>) <$> y
  pass m = IterT . pass' . runIterT . hoistIterT clean $ listen m
    where
      clean = pass . fmap (\x -> (x, const mempty))
      pass' = fmap (either (\((x, f), w) -> Right $ tell (f w) >> return x) (Right . IterT . pass' . runIterT))

The idea behind pass is to clean output for each iteration and add extra tell (f w) iteration in the end. This can possibly break some laws, but maybe not.

The implementation for FreeT should be the same, so once IterT implementation is considered okay, we get MonadWriter and MonadRWS instances for both IterT and FreeT.

"No instance for (Comonad (Cofree Maybe)) ..."

Hi! Big fan; maybe I'm doing this wrong but the following code produces an error (Mac OS X 10.10.2, GHC 7.10.1 installed via homebrew, free-4.12.1):

import Control.Comonad
import Control.Comonad.Cofree
import Data.Functor.Identity

type Stream = Cofree Maybe

nums :: Stream Int
nums = unfold (\x -> (x, Just (x+1))) 0

firstNum :: Int
firstNum = extract nums -- error!

The error message is this:

<interactive>:1:1:
    No instance for (Comonad (Cofree Identity))
      arising from a use of ‘extract’
    In the expression: extract nums

I don't have this issue on my Arch setup, but that's at home and perhaps not as up-to-date. I get a similar issue with Data.Stream.Future (extract (Last True) produces a similar error).

makeOps for free!

Currently anyone using free monads is forced to write some boilerplate code, e.g.:

data Lang next
  = Output String next
  | Input (String -> next)
  | Done
  deriving (Functor)

-- here goes boilerplate code...
output :: (MonadFree Lang m) => String -> m ()
output s = liftF $ Output s ()

input :: (MonadFree Lang m) => m String
input = liftF $ Input id

done :: (MonadFree Lang m) => m a
done = liftF Done

I'd be happy to substitute that with:

data Lang next
  = Output String next
  | Input (String -> next)
  | Done
  deriving (Functor)
makeOps ''Lang

I'm not sure this can be done in general, but there certainly is some pattern we could probably use. I am not familiar with TH enough to implement the idea right now.

Also I guess this TH stuff should be placed in a separate package?

mtl-style reorganization

Now we have all the functionality for Free monad replicated for the its more general clone Free f = FreeT f Identity. The same is going to happen with F and FT (I believe we are gonna get that one soon). We can also have the same situation with Cofree and CofreeT.

So I propose to reorganize the library in a way transformers and mtl do it. So that Control.Monad.X will just reexport Control.Monad.Trans.X and type X = XT Identity.

Specifically:

  • Control.Monad.Free -> Control.Monad.Trans.Free
  • Control.Monad.Free.Church -> Control.Monad.Trans.Free.Church
  • Control.Comonad.Free -> Control.Comonad.Trans.Free
  • and perhaps also these two:
    • Control.Monad.Iter -> Control.Monad.Trans.Iter
    • Control.Comonad.Coiter -> Control.Comonad.Trans.Coiter

I can make a corresponding pull request if this is a desired situation.

Weird haddock error

Attempting to build the haddocks for the gh-pages branch, but I'm getting something I've never seen before.

Macintosh:free ekmett$ cabal haddock
Running Haddock for free-4.6...
Preprocessing library free-4.6...
Warning: The documentation for the following packages are not installed. No
links will be generated to these packages: bifunctors-4.1.1, comonad-4.0,
contravariant-0.4.4, distributive-0.4, hashable-1.2.1.0, mtl-2.1.2,
nats-0.1.2, profunctors-4.0.2, semigroupoids-4.0, semigroups-0.12.2,
tagged-0.7, text-1.1.0.1, transformers-compat-0.1.1.1,
unordered-containers-0.2.3.3

<no location info>:
    module ‘free-4.6:Main’ is defined in multiple files: dist/build/tmp-92156/src/Control/Applicative/Free.hs
                                                         dist/build/tmp-92156/src/Control/Alternative/Free.hs
                                                         dist/build/tmp-92156/src/Control/Comonad/Cofree.hs
                                                         dist/build/tmp-92156/src/Control/Comonad/Cofree/Class.hs
                                                         dist/build/tmp-92156/src/Control/Comonad/Trans/Cofree.hs
                                                         dist/build/tmp-92156/src/Control/Comonad/Trans/Coiter.hs
                                                         dist/build/tmp-92156/src/Control/Monad/Free.hs
                                                         dist/build/tmp-92156/src/Control/Monad/Free/Church.hs
                                                         dist/build/tmp-92156/src/Control/Monad/Free/Class.hs
                                                         dist/build/tmp-92156/src/Control/Monad/Free/TH.hs
                                                         dist/build/tmp-92156/src/Control/Monad/Trans/Free.hs
                                                         dist/build/tmp-92156/src/Control/Monad/Trans/Free/Church.hs
                                                         dist/build/tmp-92156/src/Control/Monad/Trans/Iter.hs
                                                         dist/build/tmp-92156/src/Control/MonadPlus/Free.hs

iterM analog for FreeT

For Free monad we have iterM that makes it easy to write arbitrary interpreters for the underlying functor. For FreeT we have iterT which is more like iter: we can't introduce an arbitrary monad and are forced to use the underlying one.

The problem with implementing iterM' for FreeT is that monads are not (easily) composable. But monad transformers are! This gave me the idea that iterM' should accept FreeT f (t Identity) a or (forall m. Monad m => FreeT f (t m) a as a second argument instead of FreeT f m a.

Using hoist from mmorph package iterM' can be implemented like this:

-- This is analog of 'iterM' for a 'Free' 'Monad' (@Free f = FreeT f Identity@)
iterM' :: (MFunctor t, Monad m, Functor f, Monad (t Identity), Monad (t m)) =>
  (f (t m a) -> t m a) -> FreeT f (t Identity) a -> t m a
iterM' phi = iterT phi . hoistFreeT (hoist $ return . runIdentity)

Note the similarity with iterM implementation:

-- | 'iterM' from 'Control.Monad.Trans.Free'
iterM :: (Functor f, Monad m) => (f (m a) -> m a) -> Free f a -> m a
iterM phi = iterT phi . hoistFreeT (return . runIdentity)

I believe this similarity suggests I'm on the right way at least.

Without any extra dependencies (e.g. mmorph) iterM' can be alternatively defined as follows:

iterM'' :: (Monad m, Functor f, Monad (t m)) =>
  (f (t m a) -> t m a) -> (forall n. Monad n => FreeT f (t n) a) -> t m a
iterM'' phi m = iterT phi m

But that last definition forces users to write values of higher rank types.

So I suggest to add iterM' (perhaps with a better name) to the library.

Add variation on `makeFree` without type signatures?

The reason I'm interested in a version of makeFree without type signatures is:

  • So that I can provide type signatures specialized to a particular monad
  • So that I can document auto-generated commands

As far as I can tell, the only way to document commands in haddocks is to put a comment above the type signature, but if I add my own type signature it conflicts with the auto-generated type signature.

Missing fold for Cofree

E.g.

foldCofree :: Functor f => (a -> f b -> b) -> Cofree f a -> b
foldCofree f = go where
    go (x :< ts) = f x (fmap go ts)

Two Improvements to Control.Monad.Free.Church

I was looking at Control.Monad.Free.Church, and I thought of two ways it could be improved.

  1. Add an explicit definition for foldMap of (F f): foldMap f x = runF x f fold

  2. Change the definition of cutoff:
    cutoff n _ | n <= 0 = return Nothing
    cutoff n (F m) = F $ \kp kf -> m (\a n -> kp (if n <= 0 then Nothing else Just a)) (\f n -> if n <= 0 then kp Nothing else let n' = n - 1 in n' seq kf (fmap ($ n') f)) n

I would submit these improvements, but my computer just died.

Add `foldFree`?

Would you be okay with adding this function?

foldFree :: (Functor m, Monad m) => (forall x . f x -> m x) -> Free f a -> m a
foldFree nat = retract . hoistFree nat

As you already know, this is basically one of the isomorphisms in the adjunction that defines the free monad. You have iterM, which is pretty close, but sometimes I find myself reaching for the above signature.

Type signature of hoistCofree too restrictive

The type signature of hoistCofree is currently:

hoistCofree :: Functor f => (forall x. f x -> g x) -> Cofree f a -> Cofree g a

However, it can be generalized to:

hoistCofree :: Functor f => (f (Cofree g a) -> g (Cofree g a)) -> Cofree f a -> Cofree g a

comonad-transformers dependency excludes 1.7

Cannot build projects that depend on both 'free' and 'pointed', because free excludes comonad-transformers >= 1.7 and pointed excludes comonad-transformers < 1.7.

When you get a chance, would you please update the dependency? 'free' builds fine for me with comonad-transformers 1.7.

Add specialization of `retract` for `Iter ~ IterT Identity`

When using the Iter monad, it is common to, at some point, run the computation until it terminates by using runIdentity . retract.

This could be implemented as a separate function, named, for example unsafeIter :: Iter a -> a, in the same spirit as fromMaybe :: Maybe a -> a or unsafePerformIO :: IO a -> a. The unsafe monicker warns that the safety guarantees from the Iter monad are lost, namely, evaluation might not terminate.

Any input on the name, the implementation or the usefulness of the proposed function is welcome.

Concoct a correct "Free Alternative"

My working assumption is it'd look something like:

data AltF f a where
  Pure :: a -> AltF f a
  Ap   :: f a -> Alt f (a -> b) -> AltF f b
#if __GLASGOW_HASKELL__ >= 707
  deriving Typeable
#endif

data Alt f a = Alt [AltF f a]
#if __GLASGOW_HASKELL__ >= 707
  deriving Typeable
#endif

-- | Given a natural transformation from @f@ to @g@, this gives a canonical monoidal natural transformation from @'Alt' f@ to @g@.
runAlt :: forall f g a. Alternative g => (forall x. f x -> g x) -> Alt f a -> g a
runAlt u xs0 = go xs0 where
  go :: Alt f a -> g a
  go (Alt xs) = foldr (\a r -> go2 a <|> r) empty xs

  go2 :: AltF f a -> g a
  go2 (Pure a) = pure a
  go2 (Ap f x) = flip id <$> u f <*> runAlt u x

instance Functor (AltF f) where
  fmap f (Pure a)   = Pure (f a)
  fmap f (Ap x y)   = Ap x (fmap f <$> y)

instance Functor (Alt f) where
  fmap f (Alt as)   = Alt (fmap f <$> as)

Thoughts?

Free Applicative+Monad+Alternative/MonadPlus

When trying to make a simple schema EDSL, I inadvertently recreated the Control.Applicative.Free part of this library. When someone directed me to this library, I was able to streamline mine, adding the equivalents of lift and runAp.

However, I went a bit further in my module: FList is a free Applicative functor, Monad, and Alternative functor. The interface barely changes, only requiring the result of runFList to be monadic as well. runFList also takes an additional sum function, so that the user can supply their own semantics for <|>.

Is there a chance the free library will be extended, so I can use that instead of my attempt to have free Alternative functors (plus Monad)?

CofreeT's Show instance does not work

It spins endlessly and produces an infinite string of repeating "CofreeT (". It's a one line fix but I added a test for it anyway:

diff --git a/free.cabal b/free.cabal
index 86df40e..30ff931 100644
--- a/free.cabal
+++ b/free.cabal
@@ -95,3 +95,12 @@ library
     Control.Monad.Trans.Iter

   ghc-options: -Wall
+
+test-suite CofreeTShowRead
+  hs-source-dirs: test/
+  default-language:   Haskell2010
+  type:           exitcode-stdio-1.0
+  main-is:        CofreeTShowRead.hs
+  build-depends:
+    base                 == 4.*,
+    free
diff --git a/src/Control/Comonad/Trans/Cofree.hs b/src/Control/Comonad/Trans/Cofree.hs
index bdf8ce7..20e6ad3 100644
--- a/src/Control/Comonad/Trans/Cofree.hs
+++ b/src/Control/Comonad/Trans/Cofree.hs
@@ -139,7 +139,7 @@ instance (Functor f, Comonad w) => ComonadCofree f (CofreeT f w) where
   unwrap = tailF . extract . runCofreeT

 instance Show (w (CofreeF f a (CofreeT f w a))) => Show (CofreeT f w a) where
-  showsPrec d w = showParen (d > 10) $
+  showsPrec d (CofreeT w) = showParen (d > 10) $
     showString "CofreeT " . showsPrec 11 w

 instance Read (w (CofreeF f a (CofreeT f w a))) => Read (CofreeT f w a) where
diff --git a/test/CofreeTShowRead.hs b/test/CofreeTShowRead.hs
new file mode 100644
index 0000000..dc471b7
--- /dev/null
+++ b/test/CofreeTShowRead.hs
@@ -0,0 +1,10 @@
+import Control.Comonad.Trans.Cofree
+import Control.Monad
+import System.Exit
+
+main = do
+  let x :: CofreeT Maybe [] Bool
+      x = CofreeT [True :< Nothing]
+      x' :: CofreeT Maybe [] Bool
+      x' = read . show $ x
+  when (x /= x') exitFailure

Interleaving IterT monad transformer

Some context: in issue #46, @fizruk suggested generalizing a function for interleaving in the IterT example into something more general, and came up with some implementations.

I've been playing with them; the concise version works quite well, even if already-computed values are traversed again and again.

interleave :: Monad m => [IterT m a] -> IterT m [a]
interleave ms = IterT $ do
  xs <- mapM runIterT ms
  if null (rights xs)
     then return . Left $ lefts xs
     else return . Right . interleave $ map (either return id) xs

With interleave, each step takes time linear in the total number of iterative computations, both finished and pending. One could make it take time linear in the number of pending computations by collapsing neighbouring values; this is a rough sketch:

interleave2 :: Monad m => [IterT m a] -> IterT m [a]
interleave2 = interleave' . map (Right . fmap (:[]))
  where
  interleave' :: (Monad m, Monoid a) => [Either a (IterT m a)] -> IterT m a
  interleave' ms = IterT $ do
    xs <- mapM (either (return . Left) runIterT) ms
    case compact xs of
      [l@(Left _)] -> return l
      xs'          -> return . Right $ interleave' xs'

  compact :: (Monoid a) => [Either a b] -> [Either a b]
  compact []               = []
  compact (r@(Right _):xs) = r:(compact xs)
  compact (l@(Left a) :xs)  = compact' a xs

  compact' a []               = [Left a] 
  compact' a (r@(Right _):xs) = (Left a):(r:(compact xs))
  compact' a (  (Left a'):xs) = compact' (a <> a') xs

And, if we are not interested in the return values:

interleave_ :: (Monad m) => [IterT m ()] -> IterT m ()
interleave_ [] = return ()
interleave_ xs = IterT $ liftM (Right . interleave_ . rights) $ 
                                            mapM runIterT xs

Some caveats:

  • Appending lists is costly; the (dlist)[http://hackage.haskell.org/package/dlist] package may provide a good alternative.
  • mapM overflows the stack if the number of iterative computations is larger than ~400000. This (thread)[https://groups.google.com/forum/#!topic/haskell-cafe/ey2k1aWmsKo] discusses some solutions.
  • Some benchmarks are due. In the example (drawing fractals), the main bottleneck is pushing pixels to the screen, and half of the IterT never finish execution; this may not correspond to other use cases.

Does MonadFree have enough firepower?

The statement that the monad m is free over the functor f corresponds to the following universal property:

Given a monad m' and a natural transformation n: f ~> m' there exists a unique monad morphism nhat: m ~> m' such that
nhat . wrap . fmap return == n.

So it should be possible to write the following generalization of foldFree:

phi :: (MonadFree f m, Monad m') => (forall x. f x -> m' x) -> m a -> m' a

but it appears to me that wrap :: f (m a) -> m a is not sufficient for this. I find myself itching for something like unwrap :: m a -> Either a (f m a).

Alternative instances

The following race-like Alternative instance insane? The corresponding instance for FreeT would make IterT really reduce to FreeT Identity , since IterT uses such an instance.

instance Applicative v => Alternative (Free v) where
  empty = Free (pure empty)
  {-# INLINE empty #-}
  l <|> r = case l of
    Pure a -> Pure a
    Free a -> case r of 
      Pure b -> Pure b
      Free b -> Free (liftA2 (<|>) a b)
  {-# INLINE (<|>) #-}

It makes clear sense for e.g. Free ((,)a) where it would require a to be a monoid, and empty would thus be the infinite stream of memptys. When you (<|>) them, you append the elements monoidally as you go along, but then stop when either of them stops. In the case of ((->) a) mempty would be an infinite sink of 'a's. Maybe it's nonsense in other cases?

MonadTrans instance for Free violates monad transformer laws

Like the title says, the MonadTrans instance for Free violates both monad transformer laws. I'll begin with the first law:

-- The first monad transformer law, written as a functor identity law
(lift .) return /= return

This is because the left-hand side creates a Pure embedded within a Free:

lift . return
= Free . liftM Pure . return
= Free . return . Pure

... but the right-hand side creates just a naked Pure:

return
= Pure

The MonadTrans instance for Free also violates the second monad transformer law:

-- The second monad transformer law, written as a functor composition law
(lift .) (f >=> g) /= (lift .) f >=> (lift .) g

The left-hand side comes out to:

lift . (f >=> g)
= Free . liftM Pure . (f >=> g)
= \x -> Free $ liftM Pure $ f x >>= g

... which gives a Pure embedded within a single Free, whereas the right-hand side:

lift . f >=> lift . g
= \x -> lift (f x) >>= lift . g
= \x -> Free (liftM Pure $ f x) >>= Free . liftM Pure . g
= \x -> Free (liftM (Free . liftM Pure . g) $ f x)

... gives a Pure embedded within two Frees.

The laws are only true if you apply retract to both sides of the equation, but retract is not a monomorphism.

Type signature of foldFree

In master/src/Control/Monad/Free.hs, line 323, it says:

 foldFree :: (Functor m, Monad m) => (forall x . f x -> m x) -> Free f a -> m a

It should probably be Functor f, not Functor m. It still typechecks because fmap isn't actually used in the definition, I think. (It would only be used in the proof of correctness, e.g. the naturality square.)

Move `Church` into `free` from `kan-extensions`.

The kan-extensions package provides the largely unrelated Church-encoded Free monad. Lets move it here where it seems to belong.

We're already adding Rank2Types in 3.2 in order to support natural transformations, and they are fairly non-controversial.

Drop 'either' dependency

The new 'either' package dependency drags in transitive dependencies on "transformers-base" "MonadRandom" "monad-control" into upstream packages like "lens".

This instance might not be worth the dependency cost.

Map natural transformation for FreeT

Would you be interested in adding the following function to FreeT:

mapFreeT :: (Functor f, Monad m) => (forall x . m x -> n x) -> FreeT f m r -> FreeT f n r
mapFreeT nat = FreeT . nat . liftM (fmap (mapFreeT nat)) . runFreeT

This greatly resembles an IFunctor instance, except for the (Monad m) (or (Functor m)) constraint. In the longer run, when working on your indexed package you might consider N versions of all the indexed classes (i.e. NFunctor, NMonad) that have functor constraints on the last type variable that are appropriate for the world of natural transformations.

This kind of transformation is generally useful for all monad transformers since it allows you to change the base monad for a pre-existing function. For example, if I write a pipe like:

fileReader :: Producer ByteString IO ()

... and let's say I have another pipe that folds its input:

someFold :: (Monad m) => Pipe a b (WriterT m) r

I could make them compatible just by writing:

pipe :: someFold <+< mapFreeT lift fileReader

This isn't a blocking issue for me switching to free for pipes, and I plan on switching soon regardless. This is more of a "nice to have" thing. Also, it doesn't have to be a named function. If you find an appropriate class for it you can use that, too.

Use `Eq1` in context heads.

When building with GHC-8.1.2017xxxx

[14 of 19] Compiling Control.Monad.Trans.Free.Church ( src/Control/Monad/Trans/Free/Church.hs, /home/ogre/Documents/kmettverse/dist-newstyle/build/x86_64-linux/ghc-8.1.20170123/free-5/build/Control/Monad/Trans/Free/Church.o )

src/Control/Monad/Trans/Free/Church.hs:83:10: warning: [-Wsimplifiable-class-constraints]
    The constraint ‘Eq (FreeT f m a)’ matches an instance declaration
    instance [safe] (Data.Functor.Classes.Eq1 f,
                     Data.Functor.Classes.Eq1 m, Eq a) =>
                    Eq (FreeT f m a)

We should rewrite those instances too, to use lifted classes, shouldn't we?

Better roles for Control.Monad.Trans.Free.Church.F

We wind up with a nominal role for the 'm' parameter, because it occurs inside f in the body of FT

newtype FT f m a = FT { runFT :: forall r. (a -> m r) -> (f (m r) -> m r) -> m r }

We should be able to achieve representational by smashing that occurrence of f with Yoneda.

newtype FT f m a = FT { runFT :: forall r. (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r }

This is the same trick that drives the Mendler-style catamorphism.

Control.Monad.Free.TH doesn't work with GADTs on GHC 8.0

The culprit are these two pieces of code in Control.Monad.Free.TH, which don't properly handle the new GadtC and RecGadtC constructors from template-haskell-2.11.0.0 (previously, all GADTs would be represented by ForallC, whereas this is no longer the case on GHC 8.0). I'm not sure what exactly the intended behavior for ForallC should be, but regardless, that behavior should be propagated through to GadtC and RecGadtC.

@fizruk, as the original author of Control.Monad.Free.TH, would you mind looking into this?

Representable instance for Cofree f is missing

I noticed that Cofree implements every superclass of Representable, but not Representable itself. Here's a possible instance:

instance Representable f => Representable (Cofree f) where
  tabulate f = f Seq.empty :< tabulate (\k -> tabulate (f . (k Seq.<|)))

foldFree id ≟ retract

When applying foldFree id I got

foldFree id :: Monad m => Free m a -> m a

same type as

retract :: Monad m => Free m a -> m a

and at a quick glance they appear to be equal: if so should that be added as a law? I googled foldFree id and didn't find much.

useful fold possibly

From "Monad transformers and modular algebraic effects: What binds them together"

fold :: Functor sig => (a -> b) -> (sig b -> b) -> (Free sig a -> b)
fold gen alg (Pure x) = gen x
fold gen alg (Free op) = alg (fmap (fold gen alg) op)

Add more documentation to how Alternative Free/MonadPlus Free violate the laws

The documentation for free states that these instances should be handled "with care", but provides no extra information as to what this means. For some people (e.g., me), it's not clear what could go wrong, and how I may shoot myself in the foot by using these instances. I think free should expand on its disclaimer a little bit more, so that it is actionable to users.

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.