Ok cool. These both make sense to me then.  and sound like a good idea!

It would be nice to know what public instances would break as is with the change: and if they do, how many need the extra constraint david suggests on their instance.  As long as those are easy to rectify and we get such a nice asymptotic win, this sounds great! 

An idea I’ve mentioned before is that 
a simple "fast" way to to approximate / see where things might be impacted is the following work flow:

>  cabal list --simple | awk '{print ($1)}' |  uniq | time xargs -P20  -n1 cabal get
and then grep around for uses of MonadFree to see what might be impacted by such a change

its a really simple way to evaluate an "over approximation"  in terms of usage of an interface, or namespace/syntax (by no means complete, esp since the above only pulls down the most recent version of every package), but also pretty zippy all things considered

On Sat, Jul 17, 2021 at 10:20 AM Edward Kmett <ekmett@gmail.com> wrote:

On Sat, Jul 17, 2021 at 5:32 AM Carter Schonwald <carter.schonwald@gmail.com> wrote:
What about having the class head be 

Monad m, Functor f=> … MonadFree f m .. 
?
 
Requiring f to be a Functor would be too strong. Plenty of these are not.
 
Is the motivation here to have a more performant liftF?

What are some examples of more efficient implementations for current instances and what’s the performance delta? 

Often the difference can be a walk of the entire structure. I'm not allergic to the idea of just adding the method to the class as proposed, it already has a superclass, so it is already a record internally, etc. 

 
On Fri, Jul 16, 2021 at 6:53 PM David Feuer <david.feuer@gmail.com> wrote:
Another flavor would be to leave liftF alone and add a method that does the same thing with a different name. This would preserve performance characteristics for instances like FT, for situations where the current implementation is faster.

On Fri, Jul 16, 2021, 4:55 PM David Feuer <david.feuer@gmail.com> wrote:
We have

class Monad m => MonadFree f m | m -> f where
  wrap :: f (m a) -> m a

liftF :: (Functor f, MonadFree f m) => f a -> m a
liftF = wrap . fmap pure

I propose we change this to

class Monad m => MonadFree f m | m -> f where
  wrap :: f (m a) -> m a

  liftF :: f a -> m a
  default liftF :: Functor f => f a -> m a
  liftF = wrap . fmap pure

and add a function

defaultWrap :: MonadFree f m => f (m a) -> m a
defaultWrap = join . liftF

This change is not strictly backwards compatible. Some instances might, hypothetically, have to add a Functor constraint. For example, the classic Control.Monad.Free and Control.Monad.Trans.Free would need them. However, those instances already have (currently redundant) Functor constraints, so that doesn't seem like a big deal.

An alternative would be to hew more strictly to backwards compatibility by placing a Functor f constraint on liftF. This seems a bit sad for "freer" instances that don't need it. For example, we have

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

for which

liftF :: f a -> FT f m a
liftF fa = FT $ \pur bndf -> bndf pur fa

_______________________________________________
Libraries mailing list
Libraries@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
Libraries@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries