5

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

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。这似乎更适合重用索引，但“索引列表”是一种不导出其构造函数的自定义类型，所以我似乎无法理解它们。

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

4

1 回答 1

4

该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类本身，而不是像上面描述的那样创建一个复杂的额外类加默认实例设置，这不会向后兼容。

于 2015-09-09T22:32:35.507 回答