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

这个想法是，如果某个数据结构是可索引的，我应该能够通过相同类型（加上对Key a的索引）来索引一个包装它的Keyed。

将传递给ixFun的函数在包装类型的索引中转换为使用Keyed而不是a应该很容易：只需与value组合即可。但我找不到任何实际访问这些函数的方法。

我还看了一下ixset-typed包；那里的Indexable版本实际上提供了索引列表，而不是空的IxSet。这似乎更适合重用索引，但“索引列表”是一种自定义类型，其不导出其构造函数，因此我似乎无法获取它们。

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

- Ben

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的实例非常相似，但是你现在需要写funs = [ixFun' foo, ...]，而不是empty = ixSet [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类本身，而不是像上面描述的那样创建一个复杂的额外类加默认实例设置，这将不兼容以前版本。

- Daniel Wagner

---

是的，这就是我的备选方案。它不允许我重用现有的“Indexable”实例，但实际上我并没有立即使用它的情况。你说得对，它看起来相当不错；也许我会尝试看看能否将其包含在上游中。 - Ben