haskell - 使用 IxSet，我可以围绕任意可索引类型构建可索引包装吗？

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-typed 包； Indexable 的版本实际上提供了一个索引列表，而不是一个空的 IxSet。这似乎更适合重用索引，但“索引列表”是一种自定义类型，它不导出其构造函数，因此我似乎无法获得它们。

我是否错过了支持这种用法的任何内容？

Answer 1

ixset库似乎将“ key 生成功能”与“索引”混为一谈，这使得 Indexable class 比作者预期的要强大一些。 (特别是，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类本身，而不是像上面描述的那样创建一个复杂的额外类加默认实例设置，这不会向后兼容。