<div dir="ltr">I was talking in general about why you don't find instances of Monad, etc. for Set or Map which require an additional constraint on the key.</div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, May 30, 2019 at 5:36 PM Andrey Mokhov <<a href="mailto:andrey.mokhov@newcastle.ac.uk">andrey.mokhov@newcastle.ac.uk</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div lang="EN-GB">
<div class="gmail-m_-2735312901803749493WordSection1">
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">Hi Brandon,<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">Could you show the code?
<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">I have no idea how indexed monads could possibly be related here. All I want is to have a type class that unifies these two methods:<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">singleton :: a -> Set a<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">map :: Ord b => (a -> b) -> Set a -> Set b<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">singleton :: Int -> IntSet<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">map :: (Int -> Int) -> IntSet -> IntSet<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">Cheers,<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">Andrey<u></u><u></u></span></p>
<p class="MsoNormal"><a name="m_-2735312901803749493__MailEndCompose"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)"><u></u> <u></u></span></a></p>
<p class="MsoNormal"><b><span lang="EN-US" style="font-size:11pt;font-family:Calibri,sans-serif">From:</span></b><span lang="EN-US" style="font-size:11pt;font-family:Calibri,sans-serif"> Brandon Allbery [mailto:<a href="mailto:allbery.b@gmail.com" target="_blank">allbery.b@gmail.com</a>]
<br>
<b>Sent:</b> 30 May 2019 22:32<br>
<b>To:</b> Andrey Mokhov <<a href="mailto:andrey.mokhov@newcastle.ac.uk" target="_blank">andrey.mokhov@newcastle.ac.uk</a>><br>
<b>Cc:</b> Artem Pelenitsyn <<a href="mailto:a.pelenitsyn@gmail.com" target="_blank">a.pelenitsyn@gmail.com</a>>; Andreas Klebinger <<a href="mailto:klebinger.andreas@gmx.at" target="_blank">klebinger.andreas@gmx.at</a>>; <a href="mailto:ghc-devs@haskell.org" target="_blank">ghc-devs@haskell.org</a><br>
<b>Subject:</b> Re: Container type classes<u></u><u></u></span></p>
<p class="MsoNormal"><u></u> <u></u></p>
<div>
<p class="MsoNormal">They can, with more work. You want indexed monads, so you can describe types that have e.g. an ordering constraint as well as the Monad constraint.<u></u><u></u></p>
</div>
<p class="MsoNormal"><u></u> <u></u></p>
<div>
<div>
<p class="MsoNormal">On Thu, May 30, 2019 at 5:26 PM Andrey Mokhov <<a href="mailto:andrey.mokhov@newcastle.ac.uk" target="_blank">andrey.mokhov@newcastle.ac.uk</a>> wrote:<u></u><u></u></p>
</div>
<blockquote style="border-top:none;border-right:none;border-bottom:none;border-left:1pt solid rgb(204,204,204);padding:0cm 0cm 0cm 6pt;margin-left:4.8pt;margin-right:0cm">
<div>
<div>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">Hi Artem,</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)"> </span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">Thanks for the pointer, but this doesn’t seem to be a solution to my challenge: they simply give up
on overloading `map` for both Set and IntSet. As a result, we can’t write polymorphic functions over Set and IntSet if they involve any mapping.</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)"> </span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">I looked at the prototype by Andreas Klebinger, and it doesn’t include the method `setMap` either.
</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)"> </span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">Perhaps, Haskell’s type classes just can’t cope with this problem.
</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)"> </span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">*ducks for cover*</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)"> </span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">Cheers,</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">Andrey</span><u></u><u></u></p>
<p class="MsoNormal"><a name="m_-2735312901803749493_m_-2238981805605833626__MailEndCompose"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)"> </span></a><u></u><u></u></p>
<p class="MsoNormal"><b><span lang="EN-US" style="font-size:11pt;font-family:Calibri,sans-serif">From:</span></b><span lang="EN-US" style="font-size:11pt;font-family:Calibri,sans-serif"> Artem
Pelenitsyn [mailto:<a href="mailto:a.pelenitsyn@gmail.com" target="_blank">a.pelenitsyn@gmail.com</a>]
<br>
<b>Sent:</b> 30 May 2019 20:56<br>
<b>To:</b> Andrey Mokhov <<a href="mailto:andrey.mokhov@newcastle.ac.uk" target="_blank">andrey.mokhov@newcastle.ac.uk</a>><br>
<b>Cc:</b> <a href="mailto:ghc-devs@haskell.org" target="_blank">ghc-devs@haskell.org</a>; Andreas Klebinger <<a href="mailto:klebinger.andreas@gmx.at" target="_blank">klebinger.andreas@gmx.at</a>><br>
<b>Subject:</b> Re: Container type classes</span><u></u><u></u></p>
<p class="MsoNormal"> <u></u><u></u></p>
<div>
<div>
<p class="MsoNormal">Hi Andrey,<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">FWIW, mono-traversable (<a href="http://hackage.haskell.org/package/mono-traversable" target="_blank">http://hackage.haskell.org/package/mono-traversable</a>) suggests decoupling
IsSet and Funtor-like. <u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">In a nutshell, they define the IsSet class (in Data.Containers) with typical set operations like member and singleton, union and intersection. And then they tackle a (seemingly)
independent problem of mapping monomorphic containers (like IntSet, ByteString, etc.) with a separate class MonoFunctor (in Data.MonoTraversable):<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">class MonoFunctor mono where<br>
omap :: (Element mono -> Element mono) -> mono -> mono<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">And gazillion of instances for both polymorphic containers with a fixed type parameter and monomorphic ones.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">--<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">Best wishes,<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">Artem<u></u><u></u></p>
</div>
</div>
<p class="MsoNormal"> <u></u><u></u></p>
<div>
<div>
<p class="MsoNormal">On Thu, 30 May 2019 at 20:11, Andrey Mokhov <<a href="mailto:andrey.mokhov@newcastle.ac.uk" target="_blank">andrey.mokhov@newcastle.ac.uk</a>> wrote:<u></u><u></u></p>
</div>
<blockquote style="border-top:none;border-right:none;border-bottom:none;border-left:1pt solid rgb(204,204,204);padding:0cm 0cm 0cm 6pt;margin:5pt 0cm 5pt 4.8pt">
<p class="MsoNormal">Hi all,<br>
<br>
I tried to use type classes for unifying APIs of several similar data structures and it didn't work well. (In my case I was working with graphs, instead of sets or maps.)<br>
<br>
First, you rarely want to be polymorphic over the set representation, because you care about performance. You really want to use that Very.Special.Set.insert because it has the right performance characteristics for your task at hand. I found only *one* use-case
for writing polymorphic functions operating on something like IsSet: the testsuite. Of course, it is very nice to write a single property test like<br>
<br>
memberInsertProperty x set = (member x (insert x set) == True)<br>
<br>
and then use it for testing all set data structures that implement `member` and `insert`. Here you don't care about performance, only about correctness!<br>
<br>
However, this approach leads to problems with type inference, confusing error messages, and complexity. I found that it is much nicer to use explicit dictionary passing and write something like this instead:<br>
<br>
memberInsertProperty SetAPI{..} x set = (member x (insert x set) == True)<br>
<br>
where `member` and `insert` come from the SetAPI record via RecordWildCards. <br>
<br>
Finally, I'm not even sure how to create a type class covering Set and IntSet with the following two methods:<br>
<br>
singleton :: a -> Set a<br>
map :: Ord b => (a -> b) -> Set a -> Set b<br>
<br>
singleton :: Int -> IntSet<br>
map :: (Int -> Int) -> IntSet -> IntSet<br>
<br>
Could anyone please enlighten me about the right way to abstract over this using type classes?<br>
<br>
I tried a few approaches, for example:<br>
<br>
class IsSet s where<br>
type Elem s<br>
singleton :: Elem s -> s<br>
map :: Ord (Elem t) => (Elem s -> Elem t) -> s -> t<br>
<br>
Looks nice, but I can't define the IntSet instance:<br>
<br>
instance IsSet IntSet where<br>
type Elem IntSet = Int <br>
singleton = IntSet.singleton<br>
map = IntSet.map<br>
<br>
This fails with: Couldn't match type `t' with `IntSet' -- and indeed, how do I tell the compiler that in the IntSet case s ~ t in the map signature? Shall I add more associated types, or "associated constraints" using ConstraintKinds? I tried and failed, at
various stages, repeatedly.<br>
<br>
...And then you discover that there is Set.cartesianProduct :: Set a -> Set b -> Set (a, b), but no equivalent in IntSet and things get even more grim.<br>
<br>
Cheers,<br>
Andrey<br>
<br>
_______________________________________________<br>
ghc-devs mailing list<br>
<a href="mailto:ghc-devs@haskell.org" target="_blank">ghc-devs@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs</a><u></u><u></u></p>
</blockquote>
</div>
</div>
</div>
<p class="MsoNormal">_______________________________________________<br>
ghc-devs mailing list<br>
<a href="mailto:ghc-devs@haskell.org" target="_blank">ghc-devs@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs</a><u></u><u></u></p>
</blockquote>
</div>
<p class="MsoNormal"><br clear="all">
<u></u><u></u></p>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<p class="MsoNormal">-- <u></u><u></u></p>
<div>
<div>
<div>
<div>
<div>
<p class="MsoNormal">brandon s allbery kf8nh<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><a href="mailto:allbery.b@gmail.com" target="_blank">allbery.b@gmail.com</a><u></u><u></u></p>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</blockquote></div><br clear="all"><div><br></div>-- <br><div dir="ltr" class="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div>brandon s allbery kf8nh</div><div><a href="mailto:allbery.b@gmail.com" target="_blank">allbery.b@gmail.com</a></div></div></div></div></div>