[Haskell-cafe] Making monadic code more concise

[Alberto G. Corona]

I like your autolifting stuff, and the runnable concept.


> 2010/11/15 Ling Yang <lyang at 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 at uptoisomorphism.net>
>> wrote:
>> > On Mon, Nov 15, 2010 at 12:43 PM, Ling Yang <lyang at 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 at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20101115/f5d7a3f9/attachment.html