How do I create a ListIsomorphic instance for gene

问题:

Given the following class:

class ListIsomorphic l where
    toList   :: l a -> [a]
    fromList :: [a] -> l a

How can I write a instance for vector types using Data.Vector.Generic? This doesn't work:

instance (V.Vector v a) => ListIsomorphic v where
    toList   = V.toList
    fromList = V.fromList

Giving me:

test.hs:31:10:
    Variable ‘a’ occurs more often than in the instance head
      in the constraint: V.Vector v a
    (Use UndecidableInstances to permit this)
    In the instance declaration for ‘ListIsomorphic v’

回答1:

Don't. Adding an instance for all v to your Listable class will become cumbersome to use due to overlapping instances.

A Vector v a => v isn't isomorphic to a list because it is constrained by which items can be elements of the list. You'd need a class that captures this constraint, something like

{-# LANGUAGE ConstraintKinds #-}
{-# LANGUAGE TypeFamilies #-}

import Data.Constraint

class ConstrainedList l where
    type Elem l a :: Constraint
    toList   :: Elem l a => l a -> [a]
    fromList :: Elem l a => [a] -> l a

Instead of adding ConstrainedList instances for all types Vector v a => v which would get us into overlapping instances territory, instead we'll define it only for the types we're interested in. The following will cover all the types with a Vector instance in the vector package.

import qualified Data.Vector.Primitive as VP
import qualified Data.Vector.Generic as VG

instance ConstrainedList VP.Vector where
    type Elem VP.Vector a = VG.Vector VP.Vector a
    toList   = VG.toList
    fromList = VG.fromList

Instances for other types

You can write a ConstrainedList instance for regular lists [] that requires only the empty constraint for its elements.

instance ConstrainedList [] where
    type Elem [] a = ()
    toList   = id
    fromList = id

Anywhere that uses toList or fromList will also require an Elem l a instance.

cmap :: (ConstrainedList l, Elem l a, Elem l b) => (a -> b) -> l a -> l b
cmap f = fromList . map f . toList

When we know concrete types for the lists and elements these functions will be easy to use without messing around with constraints.

cmap (+1) [1,2,3,4]

Here Be Dragons

Don't try what follows. If you are interested in the class of things that are isomorphic to lists without additional constraints, just make another class for it. This just demonstrates what you can do when you've designed yourself into a corner: summon a dragon.

You can also write functions that require a proof that there is no constraint on the elements of a ConstrainedList. This is way off into the realms of the constraints package and programming styles that aren't really supported by GHC, but there aren't enough constraints examples so I'll leave this one here.

{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE ScopedTypeVariables #-}

map' :: forall l a b. (ConstrainedList l, () :=> Elem l a, () :=> Elem l b) =>
                      (a -> b) -> l a -> l b
map' f = case (ins :: () :- Elem l a) of { Sub Dict ->
         case (ins :: () :- Elem l b) of { Sub Dict ->
         fromList . map f . toList
         }}

We could check that a ConstrainedList has no constraint by just checking that Elem l a ~ (), but that wouldn't work if its constraint was written in a different way.

{-# LANGUAGE FlexibleInstances #-}

class Any a
instance Any a

data AList a = AList {getList :: [a]}
    deriving (Show)

instance ConstrainedList AList where
    type Elem AList a = Any a
    toList   = getList
    fromList = AList

() isn't the same type as Any a even though () implies Any a. The constraints package captures relationships like this by reifying them to the type classes Class and :=>

{-# LANGUAGE MultiParamTypeClasses #-}

--       class () => Any a
instance Class ()   (Any a) where
    cls = Sub Dict

-- instance ()  => Any a
instance    () :=> Any a where
    ins = Sub Dict

All of that work lets us easily reuse functions without providing all those dictionaries when a concrete list type is known.

map'' :: (a -> b) -> AList a -> AList b
map'' = map'

回答2:

I frequently run into this problem. Here are two solutions I've come up with:

1. Change the class parameters:

   class ListIsomorphic l a where
     toList :: l a -> [a]
     fromList :: [a] -> l a
   
   instance (V.Vector v a) => Listable v a where
     ...
   

2. Use constraint kinds

   class ListIsomorphic l where
     type C l a :: Constraint
     toList :: l a -> [a]
     fromList :: [a] -> l a
   
   instance Listable v where
     type C v a = (V.Vector v a)
     ...