With IxSet, can I build an Indexable wrapper around an arbitrary Indexable type?

Question

What I'd like to be able to do is something like the following:

import Data.IxSet

newtype Key a = Key Integer
  deriving (Eq, Ord, Show)

data Keyed a = Keyed { key :: (Key a), value :: a }
  deriving (Eq, Ord, Show)

instance Indexable a => Indexable (Keyed a)
    where empty = ixSet $ ixFun (\k -> [key k]) : _somehow_reuse_indices_of_a_

The idea is that if some data structure is Indexable, I should be able to index a Keyed wrapping it by the same types (plus an index on Key a).

It should be easy to convert the functions passed to ixFun in the wrapped type's indices to work with Keyed instead of a: just compose with value. But I can't find any way of actually getting at those functions.

I also had a look at the ixset-typed package; the version of Indexable there actually provides a list of indices, rather than an empty IxSet. This would appear to be much more amenable to reusing the indices, but the "list of indices" is a custom type which doesn't export its constructors, so I don't appear to be able to get at them.

Have I missed anything that would support this kind of usage?

Answer 1

The ixset library seems to conflate "key generation functions" with "indices", which makes the Indexable class a bit more powerful than the author probably intended. (In particular, empty is allowed to already have some elements in it -- which makes the name empty a bit weird!) You can fix this client-side with a little work, by introducing a new type that is just for the functions (and therefore cannot contain any elements):

data IxFun a = forall key. (Typeable key, Ord key) => IxFun (a -> [key])

ixFun' :: (Typeable key, Ord key) => (a -> [key]) -> IxFun a
ixFun' = IxFun

instance Contravariant IxFun where
    contramap f (IxFun g) = IxFun (g . f)

ixFromIxFun :: IxFun a -> Ix a
ixFromIxFun (IxFun f) = ixFun f

Then you can build some typeclass support, as in:

class IndexableFun a where funs :: [IxFun a]

-- turn any IndexableFun into an Indexable
defaultEmpty :: IndexableFun a => IxSet a
defaultEmpty = ixSet (map ixFromIxFun funs)

Instances of this class look very similar to instances of Indexable, but instead of empty = ixSet [ixFun foo, ...] you now write funs = [ixFun' foo, ...]. Now it is easy to write your instance:

instance (IndexableFun a, Typeable a) => IndexableFun (Keyed a) where
    funs = ixFun' (\v -> [key v]) : map (contramap value) funs

instance (IndexableFun a, Typeable a) => Indexable (Keyed a) where
    empty = defaultEmpty

You can even readily adapt the implementation of ixGen to this type:

 ixGen' :: forall proxy a b. (Data a, Ord b, Typeable b) => proxy b -> IxFun a
 ixGen' _ = ixFun' (flatten :: a -> [b])

Integrating this kind of approach into the ixset package itself would be a very nice touch, and shouldn't be too hard. Though do contact the maintainer first, as this could potentially be a somewhat invasive change: one would presumably want to modify the Indexable class itself rather than creating a convoluted extra-class-plus-default-instance setup like the one described above, which would not be backwards compatible.