使用IxSet,我可以围绕任意Indexable类型构建一个Indexable包装器吗？

Question

我希望能够做的事情如下:

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_

我的想法是,如果某些数据结构是Indexable,我应该能够Keyed用相同的类型(加上索引Key a)来索引它.

应该很容易将传递给ixFun包装类型索引的函数转换为使用Keyed而不是a:只需要编写value.但我找不到任何方法来实际掌握这些功能.

我也看了一下ixset类型的包; Indexable的版本实际上提供了一个索引列表,而不是一个空的IxSet.这似乎更适合重用索引,但"索引列表"是一个自定义类型,它不会导出它的构造函数,所以我似乎无法得到它们.

我错过了任何支持这种用法的东西吗？

Answer 1

该ixset库似乎将“密钥生成函数”与“索引”混为一谈，这使得该类Indexable比作者预期的更强大。（特别是，empty允许​​其中已经有一些元素——这使得这个名字empty有点奇怪！）您可以通过一些工作来修复这个客户端，通过引入一个仅用于函数的新类型（因此不能包含任何元素）：

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

然后您可以构建一些类型类支持，如下所示：

class IndexableFun a where funs :: [IxFun a]

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

此类的实例看起来与 的实例非常相似Indexable，但empty = ixSet [ixFun foo, ...]您现在编写的是funs = [ixFun' foo, ...]. 现在很容易编写您的实例：

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

您甚至可以轻松地将 的实现调整ixGen为这种类型：

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

将这种方法集成到ixset包本身中将是一个非常好的接触，并且应该不会太难。不过，请先联系维护者，因为这可能是一个有点侵入性的更改：人们可能想要修改类Indexable本身，而不是像上面描述的那样创建一个复杂的额外类加默认实例设置，这不会向后兼容。