[Haskell-cafe] Type families again

[Robert Greayer]

On Thu, Dec 2, 2010 at 4:39 PM, Antoine Latter <aslatter at gmail.com> wrote:
> On Thu, Dec 2, 2010 at 3:29 PM, Andrew Coppin
> <andrewcoppin at btinternet.com> wrote:
>> Yes, it's me. And yes, I come with yet more questions.
>>
>> With Haskell 98 (or, indeed, Haskell 2010) it is impossible to define a
>> polymorphic version of "head" that works for [], Set and ByteString. You can
>> use a higher-kinded type class for [], but that fails for Set (because you
>> can't specify the Ord constraint) and fails spectacularly for ByteString
>> (because it has the wrong kind). The basic problem is that the function's
>> type needs to refer to the type of the container and the type of elements it
>> contains, but the relationship between these types can be arbitrary.
>>
>> Type families allow you to neatly and cleanly fix the problem:
>>
>>  class Head c where
>>    type Element c :: *
>>    head :: c -> Element c
>>
>> It's simple, comprehensible, and it /actually works/.
>>
>> Following this success, we can define functions such as tail, join, and so
>> forth.
>>
>> What we /can't/ do is define a polymorphic map function. One might try to do
>> something like
>>
>>  class Functor f where
>>    type Element f :: *
>>    fmap :: (Element f2 ~ y) => (x -> y) -> f -> f2
>>
>>  instance Functor [x] where
>>    type Element [x] = x
>>    fmap = map
>>
>> However, this fails. Put simply, the type for fmap fails to specify that f
>> and f2 must be /the same type of thing/, just with different element types.
>>
>> The trouble is, after spending quite a bit of brainpower, I literally cannot
>> think of a way of writing such a constraint. Does anybody have any
>> suggestions?
>>
>
> Does this do what you need?
>
> http://hackage.haskell.org/packages/archive/rmonad/0.6/doc/html/Control-RMonad.html#t:RFunctor
>
> Antoine
>

I think this doesn't handle the ByteString case (wrong kind).  Here's
another mostly unsatisfactory (injectivity issues) solution that may
possibly not even work though it does compile:

import qualified Data.ByteString as B
import Data.Word

type family P c z

class Mappable1 c1 c2 where
    type E1 c1 c2
    type E2 c1 c2
    map1 :: (P c1 a ~ P c2 a) => (E1 c1 c2 -> E2 c1 c2) -> c1 -> c2

instance Mappable1 [a] [b] where
    type E1 [a] [b] = a
    type E2 [a] [b] = b
    map1 = map

type instance P [a] b = [b]

instance Mappable1 B.ByteString B.ByteString where
    type E1 B.ByteString B.ByteString = Word8
    type E2 B.ByteString B.ByteString = Word8
    map1 = B.map

type instance P B.ByteString b = B.ByteString