<div>On Thu, Apr 9, 2009 at 5:14 AM, Simon Peyton-Jones <span dir="ltr"><<a href="mailto:simonpj@microsoft.com">simonpj@microsoft.com</a>></span> wrote:<br></div><div><blockquote class="gmail_quote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; ">
<div class="im">| > 3) Is it possible to implement the following function?<br>| ><br>| >> mkMonoidInst :: a -> (a -> a -> a) -> MonoidInst a<br>| >> mkMonoidInst mempty mappend = ...<br><br></div>
No it's not possible. And now you know why!<br><font color="#888888"><br>Simon<br></font><div><div></div></div></blockquote></div><div><br></div><div><div>Simon, </div><div><br></div></div>While we can't give him exactly what he asked for, we can approximate the construction using Oleg and CC Shan's Implicit Configurations and fulfill the spirit of the request.<div>
<br></div><div><div>> {-# LANGUAGE ScopedTypeVariables, TypeOperators, MultiParamTypeClasses, FlexibleContexts, UndecidableInstances, Rank2Types, GeneralizedNewtypeDeriving #-}</div><div><br></div><div><div>Please, pardon the gratuitous use of extensions.</div>
<div><br></div></div><div>> import Data.Bits</div><div>> import Data.Monoid</div><div>> import Data.Reflection -- from package 'reflection'</div><div><br></div><div>First define the concept of a dictionary for a monoid.</div>
<div><br></div><div>> type M a = (a, a -> a -> a)</div><div><br></div><div>Then provide a type level brand that indicates which dictionary you are going to use.</div><div><br></div><div>> data (a `WithMonoid` s) = Mon { getWithMonoid :: a } deriving (Eq,Ord,Show)<br>
</div><div><br></div><div>Use reflection to access the dictionary</div><div><br></div><div>> instance (s `Reflects` M a) => Monoid (a `WithMonoid` s) where</div><div>> mempty = Mon (fst (reflect (undefined :: s)))</div>
<div>> Mon a `mappend` Mon b = Mon ((snd (reflect (undefined :: s))) a b)</div><div><br></div><div>Reify a monoid dictionary for use within a universally quantified world, ala ST.</div><div><br></div><div>> reifyMonoid :: a -> (a -> a -> a) -> (forall s. (s `Reflects` M a) => s -> w) -> w</div>
<div>> reifyMonoid = curry reify</div><div><br></div><div>Change the type of the above to avoid the spurious argument, and to automatically unwrap the result.</div><div><br></div><div>> withMonoid :: a -> (a -> a -> a) -> (forall s. (s `Reflects` M a) => w `WithMonoid` s) -> w</div>
<div>> withMonoid = withMonoid' undefined where</div><div>> withMonoid' :: w -> a -> (a -> a -> a) -> (forall s. (s `Reflects` M a) => w `WithMonoid` s) -> w</div><div>> withMonoid' (_::w) (i::a) f k = reifyMonoid i f (\(_::t) -> getWithMonoid (k :: w `WithMonoid` t))</div>
<div><br></div><div>And now we have some likely candidates to test:</div><div><br></div><div>> test :: Int</div><div>> test = withMonoid 0 (+) (mconcat [Mon 2,mempty,Mon 0])</div><div><br></div><div>> test2 :: Int</div>
<div>> test2 = withMonoid 1 (*) (mconcat [Mon 3,mempty,Mon 2])</div><div><br></div><div>> test3 :: Integer</div><div>> test3 = withMonoid 0 xor (mconcat [Mon 4,mempty,Mon 4])</div><div><br></div></div><div><div>*Main> test</div>
<div>Loading package reflection-0.1.1 ... linking ... done.</div><div>2</div><div><div>*Main> test2</div><div>6</div><div>*Main> test3</div><div>0</div><div><br></div><div>There you have it, everything works out.</div>
</div><div><br></div><div>Amusingly, I have a similar set of constructions for reifying other kinds of constructs in my 'monoids' library on Hackage, but I don't currently provide a reified Monoid type, mainly because the signature isn't enough to enforce its associativity.</div>
<div><br></div><div>However, I do allow you to reify an arbitrary function into a 'Reducer' using this trick to enable you to uniformly inject values into a particular monoid.</div><div><br></div><div>-Edward Kmett</div>
<div><br></div><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div><div class="h5">
<br>
| -----Original Message-----<br>
| From: <a href="mailto:haskell-cafe-bounces@haskell.org">haskell-cafe-bounces@haskell.org</a> [mailto:<a href="mailto:haskell-cafe-bounces@haskell.org">haskell-cafe-bounces@haskell.org</a>] On<br>
| Behalf Of Lennart Augustsson<br>
| Sent: 09 April 2009 09:54<br>
| To: Martijn van Steenbergen<br>
| Cc: Haskell Cafe<br>
| Subject: Re: [Haskell-cafe] Ambiguous reified dictionaries<br>
|<br>
| That program is incorrect, it contains two instances for Monoid Int,<br>
| and the compiler should flag it as illegal.<br>
|<br>
| -- Lennart<br>
|<br>
| On Thu, Apr 9, 2009 at 10:35 AM, Martijn van Steenbergen<br>
| <<a href="mailto:martijn@van.steenbergen.nl">martijn@van.steenbergen.nl</a>> wrote:<br>
| > Good morning,<br>
| ><br>
| > The [1]GHC user's guide, section 8.4.5 says:<br>
| ><br>
| > "The new feature is that pattern-matching on MkSet (as in the definition of<br>
| > insert) makes available an (Eq a) context. In implementation terms, the<br>
| > MkSet constructor has a hidden field that stores the (Eq a) dictionary that<br>
| > is passed to MkSet; so when pattern-matching that dictionary becomes<br>
| > available for the right-hand side of the match."<br>
| ><br>
| > But what happens if there are several dictionaries available?<br>
| ><br>
| > Consider these three modules:<br>
| ><br>
| > ReifyMonoid.hs:<br>
| ><br>
| >> {-# LANGUAGE GADTs #-}<br>
| >><br>
| >> module ReifyMonoid where<br>
| >><br>
| >> import Data.Monoid<br>
| >><br>
| >> data MonoidInst a where<br>
| >> MkMonoidInst :: Monoid a => MonoidInst a<br>
| ><br>
| > ReifySum.hs:<br>
| ><br>
| >> module ReifySum where<br>
| >><br>
| >> import ReifyMonoid<br>
| >> import Data.Monoid<br>
| >><br>
| >> instance Monoid Int where<br>
| >> mempty = 0<br>
| >> mappend = (+)<br>
| >><br>
| >> intSum :: MonoidInst Int<br>
| >> intSum = MkMonoidInst<br>
| ><br>
| > ReifyProd.hs:<br>
| ><br>
| >> module ReifyProd where<br>
| >><br>
| >> import ReifyMonoid<br>
| >> import Data.Monoid<br>
| >><br>
| >> instance Monoid Int where<br>
| >> mempty = 1<br>
| >> mappend = (*)<br>
| >><br>
| >> intProd :: MonoidInst Int<br>
| >> intProd = MkMonoidInst<br>
| ><br>
| > Now a function<br>
| ><br>
| >> emp :: MonoidInst a -> a<br>
| >> emp MkMonoidInst = mempty<br>
| ><br>
| > works as you'd expect:<br>
| ><br>
| > *ReifySum ReifyProd> emp intSum<br>
| > 0<br>
| > *ReifySum ReifyProd> emp intProd<br>
| > 1<br>
| ><br>
| > But what about this function?<br>
| ><br>
| >> empAmb :: MonoidInst a -> MonoidInst a -> a<br>
| >> empAmb MkMonoidInst MkMonoidInst = mempty<br>
| ><br>
| > Now there are two dictionaries available. GHC consistently picks the one<br>
| > from the second argument:<br>
| ><br>
| > *ReifySum ReifyProd> empAmb intProd intSum<br>
| > 1<br>
| > *ReifySum ReifyProd> empAmb intSum intProd<br>
| > 0<br>
| ><br>
| > My questions are:<br>
| ><br>
| > 1) Shouldn't GHC reject this as being ambiguous?<br>
| > 2) Should class constraints only be available on existentially qualified<br>
| > type variables to prevent this from happening at all?<br>
| > 3) Is it possible to implement the following function?<br>
| ><br>
| >> mkMonoidInst :: a -> (a -> a -> a) -> MonoidInst a<br>
| >> mkMonoidInst mempty mappend = ...<br>
| ><br>
| > Thank you,<br>
| ><br>
| > Martijn.<br>
| ><br>
| ><br>
| ><br>
| > [1]<br>
| > <a href="http://www.haskell.org/ghc/docs/latest/html/users_guide/data-type-" target="_blank">http://www.haskell.org/ghc/docs/latest/html/users_guide/data-type-</a><br>
| extensions.html#gadt-style<br>
| > _______________________________________________<br>
| > Haskell-Cafe mailing list<br>
| > <a href="mailto:Haskell-Cafe@haskell.org">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>
| ><br>
| _______________________________________________<br>
| Haskell-Cafe mailing list<br>
| <a href="mailto:Haskell-Cafe@haskell.org">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>
<br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">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><br></div>