2010/11/15 Ling Yang <lyang@cs.stanford.edu>

See my reply to Alex's post for my perspective on how this relates to
applicative functors, reproduced here:

>> This, to me, is a big hint that applicative functors could be useful.
>

>Indeed, the ideas here also apply to applicative functors; it is just the lifting primitives that will be different; instead of having liftM<N>, we can use <$> and <*> to lift the functions. We could have done this for Num and Maybe (suppose Maybe is an instance of Applicative):
>
>instance (Num a) => Num (Maybe a) where
>       (+) = \x y -> (+) <$> x <*> y
>       (-) = \x y -> (-) <$> x <*> y
>       (*) = \x y -> (+) <$> x <*> y
>       abs = abs <$>
>       signum = signum <$>
>       fromInteger = pure . fromInteger
>
>The larger goal remains the same: autolifting in a principled manner.
>
>However, you actually bring up a very good point; what if it is really only the applicative functors that this method works on in general, that there is no 'use case' for considering this autolifting for monads in particular?
>I think the answer lies in the fact that monads can be 'flattened;' that is, realizations of the type m (m a) -> m a are mechanical (in the form of 'join') given that >>= is defined. This is important when we have a typeclass that also has monadic signatures. To be more concrete, consider how this function could be used in a 'monadic DSL':
>
>enter x = case x of
>       0 -> Nothing
>       _ -> Just "hi"
>
>The type of 'enter' is one case of the general from 'a -> M b'. If we were instancing a typeclass that had an 'a -> M b' function, we'd need a function of type 'M a -> M b'. This would be accomplished by
>
>enter' = join . liftM enter
>
>So the set of lifting primitives must include at least some way to get M a -> M b from 'a -> M b'---which requires that M is a monad, not just an applicative functor.
>
>Thanks for the mention of applicative functors; I should have included them in the original post.

>
>Lingfeng Yang
>lyang at cs dot stanford dot edu
>

I should have included a mention of Applicative in my original post.

> Part of the reason Num was so easy is that all the functions produce
> values whose type is the class parameter. Your Num instance could
> almost be completely generic for any ((Applicative f, Num a) => f a),
> except that Num demands instances of Eq and Show, neither of which can
> be blindly lifted the way the numeric operations can.

> I imagine it should be fairly obvious why you can't write a
> non-trivial generic instance (Show a) => Show (M a) that would work
> for any possible monad M--you'd need a function (show :: M a ->
> String) which is impossible for abstract types like IO, as well as
> function types like the State monad. The same applies to (==), of
> course. Trivial instances are always possible, e.g. show _ = "[not
> showable]", but then you don't get sensible behavior when a
> non-trivial instance does exist, such  as for Maybe or [].

Good point. This is where we can start defining restrictions for when
this automatic lifting can or cannot take place. I reference the
concept of 'runnable monads' here, from

"[Erwig and Ren 2004] Monadification of Functional Programs"

A 'runnable monad' is a monad with an exit function:

class (Monad m) => Runnable m where
       exit : m a -> a

And yes, for monads like IO, no one would really have a need for
'exit' outside of the cases where they need unsafePerformIO. However,
for Maybe and Prob, 'exit' is extremely useful. In fact, in the
probability monad, if you could not exit the monad, you could not get
anything done, as the real use is around sampling and computing
probabilities, which are of non-monadic types.

Provided M is a runnable monad,

class (Show a) => Show (M a) where
       show = show . exit

I'm aware of the limitations of this approach; I just want to come up
with a set of primitives that characterize the cases where
autolifting/monadic instancing is useful.

On Mon, Nov 15, 2010 at 11:19 AM, C. McCann <cam@uptoisomorphism.net> wrote:
> On Mon, Nov 15, 2010 at 12:43 PM, Ling Yang <lyang@cs.stanford.edu> wrote:
>> Specifically: There are some DSLs that can be largely expressed as monads,
>> that inherently play nicely with expressions on non-monadic values.
>> We'd like to use the functions that already work on the non-monadic
>> values for monadic values without calls to liftM all over the place.
>
> It's worth noting that using liftM is possibly the worst possible way
> to do this, aesthetically speaking. To start with, liftM is just fmap
> with a gratuitous Monad constraint added on top. Any instance of Monad
> can (and should) also be an instance of Functor, and if the instances
> aren't buggy, then liftM f = (>>= return . f) = fmap f.
>
> Additionally, in many cases readability is improved by using (<$>), an
> operator synonym for fmap, found in Control.Applicative, I believe.
>
>> The probability monad is a good example.
>>
> [snip]
>> I'm interested in shortening the description of 'test', as it is
>> really just a 'formal addition' of random variables. One can use liftM
>> for that:
>>
>> test = liftM2 (+) (coin 0.5) (coin 0.5)
>
> Also on the subject of Control.Applicative, note that independent
> probabilities like this don't actually require a monad, merely the
> ability to lift currying into the underlying functor, which is what
> Applicative provides. The operator ((<*>) :: f (a -> b) -> f a -> f b)
> is convenient for writing such expressions, e.g.:
>
> test = (+) <$> coin 0.5 <*> coin 0.5
>
> Monads are only required for lifting control flow into the functor,
> which in this case amounts to conditional probability. You would not,
> for example, be able to easily use simple lifted functions to write
> "roll a 6-sided die, flip a coin as many times as the die shows, then
> count how many flips were heads".
>
>> I think a good question as a starting point is whether it's possible
>> to do this 'monadic instance transformation' for any typeclass, and
>> whether or not we were lucky to have been able to instance Num so
>> easily (as Num, Fractional can just be seen as algebras over some base
>> type plus a coercion function, making them unusually easy to lift if
>> most typeclasses actually don't fit this description).
>
> Part of the reason Num was so easy is that all the functions produce
> values whose type is the class parameter. Your Num instance could
> almost be completely generic for any ((Applicative f, Num a) => f a),
> except that Num demands instances of Eq and Show, neither of which can
> be blindly lifted the way the numeric operations can.
>
> I imagine it should be fairly obvious why you can't write a
> non-trivial generic instance (Show a) => Show (M a) that would work
> for any possible monad M--you'd need a function (show :: M a ->
> String) which is impossible for abstract types like IO, as well as
> function types like the State monad. The same applies to (==), of
> course. Trivial instances are always possible, e.g. show _ = "[not
> showable]", but then you don't get sensible behavior when a
> non-trivial instance does exist, such  as for Maybe or [].
>
>> Note that if we consider this in a 'monadification' context, where we
>> are making some choice for each lifted function, treating it as
>> entering, exiting, or computing in the monad, instancing the typeclass
>> leads to very few choices for each: the monadic versions of +, -, *
>> must be obtained with "liftM2",the monadic versions of negate, abs,
>> signum must be obtained with "liftM", and the monadic version of
>> fromInteger must be obtained with "return . "
>
> Again, this is pretty much the motivation and purpose of
> Control.Applicative. Depending on how you want to look at it, the
> underlying concept is either lifting multi-argument functions into the
> functor step by step, or lifting tuples into the functor, e.g. (f a, f
> b) -> f (a, b); the equivalence is recovered using fmap with either
> (curry id) or (uncurry id).
>
> Note that things do get more complicated if you have to deal with the
> full monadic structure, but since you're lifting functions that have
> no knowledge of the functor whatsoever they pretty much have to be
> independent of it.
>
>> I suppose I'm basically suggesting that the 'next step' is to somehow
>> do this calculation of types on real type values, and use an inductive
>> programming tool like Djinn to realize the type signatures. I think
>> the general programming technique this is getting at is an orthogonal
>> version of LISP style where one goes back and forth between types and
>> functions, rather than data and code. I would also appreciate any
>> pointers to works in that area.
>
> Well, I don't think there's any good way to do this in Haskell
> directly, in general. There's a GHC extension that can automatically
> derive Functor for many types, but nothing to automatically derive
> Applicative as far as I know (other than in trivial cases with newtype
> deriving)--I suspect due to Applicative instances being far less often
> uniquely determined than for Functor. And while a fully generic
> instance can be written and used for any Applicative and Num, the
> impossibility of sensible instances for Show and Eq, combined with the
> context-blind nature of Haskell's instance resolution, means that it
> can't be written directly in full generality. It would, however, be
> fairly trivial to manufacture instance declarations for specific types
> using some sort of preprocessor, assuming Show/Eq instances have been
> written manually or by creating trivial ones.
>
> Anyway, you may want to read the paper that introduced Applicative,
> since that seems to describe the subset of generic lifted functions
> you're after: http://www.soi.city.ac.uk/~ross/papers/Applicative.html
>
> If for some reason you'd rather continue listening to me talk about
> it, I wrote an extended ode to Applicative on Stack Overflow some time
> back that was apparently well-received:
> http://stackoverflow.com/questions/3242361/haskell-how-is-pronounced/3242853#3242853
>
> - C.
>
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe