使用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_

这个想法是，如果一些数据结构是可索引的，我应该能够索引一个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类本身，而不是像上面描述的那样创建一个复杂的额外类加默认实例设置，这将不向后兼容。