Container type classes

[Artem Pelenitsyn]

Hi Andrey,

FWIW, mono-traversable (http://hackage.haskell.org/package/mono-traversable)
suggests decoupling IsSet and Funtor-like.

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):

class MonoFunctor mono where
    omap :: (Element mono -> Element mono) -> mono -> mono

And gazillion of instances for both polymorphic containers with a fixed
type parameter and monomorphic ones.

--
Best wishes,
Artem

On Thu, 30 May 2019 at 20:11, Andrey Mokhov <andrey.mokhov at newcastle.ac.uk>
wrote:

> Hi all,
>
> 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.)
>
> 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
>
> memberInsertProperty x set = (member x (insert x set) == True)
>
> 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!
>
> 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:
>
> memberInsertProperty SetAPI{..} x set = (member x (insert x set) == True)
>
> where `member` and `insert` come from the SetAPI record via
> RecordWildCards.
>
> Finally, I'm not even sure how to create a type class covering Set and
> IntSet with the following two methods:
>
> singleton :: a -> Set a
> map :: Ord b => (a -> b) -> Set a -> Set b
>
> singleton :: Int -> IntSet
> map :: (Int -> Int) -> IntSet -> IntSet
>
> Could anyone please enlighten me about the right way to abstract over this
> using type classes?
>
> I tried a few approaches, for example:
>
> class IsSet s where
>     type Elem s
>     singleton :: Elem s -> s
>     map :: Ord (Elem t) => (Elem s -> Elem t) -> s -> t
>
> Looks nice, but I can't define the IntSet instance:
>
> instance IsSet IntSet where
>     type Elem IntSet = Int
>     singleton = IntSet.singleton
>     map = IntSet.map
>
> 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.
>
> ...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.
>
> Cheers,
> Andrey
>
> _______________________________________________
> ghc-devs mailing list
> ghc-devs at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/ghc-devs/attachments/20190530/d7a42043/attachment.html>