<div class="gmail_quote">I like your autolifting stuff, and the runnable concept. <br><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div class="gmail_quote">

2010/11/15 Ling Yang <span dir="ltr">&lt;<a href="mailto:lyang@cs.stanford.edu" target="_blank">lyang@cs.stanford.edu</a>&gt;</span><div><div></div><div class="h5"><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">


See my reply to Alex&#39;s post for my perspective on how this relates to<br>
applicative functors, reproduced here:<br>
<div><br>
&gt;&gt; This, to me, is a big hint that applicative functors could be useful.<br>
&gt;<br>
</div>&gt;Indeed, the ideas here also apply to applicative functors; it is just the lifting primitives that will be different; instead of having liftM&lt;N&gt;, we can use &lt;$&gt; and &lt;*&gt; to lift the functions. We could have done this for Num and Maybe (suppose Maybe is an instance of Applicative):<br>



&gt;<br>
&gt;instance (Num a) =&gt; Num (Maybe a) where<br>
&gt;       (+) = \x y -&gt; (+) &lt;$&gt; x &lt;*&gt; y<br>
&gt;       (-) = \x y -&gt; (-) &lt;$&gt; x &lt;*&gt; y<br>
&gt;       (*) = \x y -&gt; (+) &lt;$&gt; x &lt;*&gt; y<br>
&gt;       abs = abs &lt;$&gt;<br>
&gt;       signum = signum &lt;$&gt;<br>
&gt;       fromInteger = pure . fromInteger<br>
&gt;<br>
&gt;The larger goal remains the same: autolifting in a principled manner.<br>
&gt;<br>
&gt;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 &#39;use case&#39; for considering this autolifting for monads in particular?<br>



&gt;I think the answer lies in the fact that monads can be &#39;flattened;&#39; that is, realizations of the type m (m a) -&gt; m a are mechanical (in the form of &#39;join&#39;) given that &gt;&gt;= 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 &#39;monadic DSL&#39;:<br>



&gt;<br>
&gt;enter x = case x of<br>
&gt;       0 -&gt; Nothing<br>
&gt;       _ -&gt; Just &quot;hi&quot;<br>
&gt;<br>
&gt;The type of &#39;enter&#39; is one case of the general from &#39;a -&gt; M b&#39;. If we were instancing a typeclass that had an &#39;a -&gt; M b&#39; function, we&#39;d need a function of type &#39;M a -&gt; M b&#39;. This would be accomplished by<br>



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