我应该如何在Purescript中建模类型安全索引？

In my application, I'd like to index sets of objects in a type-safe way using a structure similar to a relational database index. For example, I might want to index a set of User objects based on age and name:

在我的应用程序中，我想使用类似于关系数据库索引的结构以类型安全的方式索引对象集。例如，我可能想要根据年龄和名称索引一组User对象：

import Data.Map as M
import Data.Set as S

type AgeNameIndex = M.Map Int (M.Map String (S.Set User))

Furthermore, I'd like to do operations like union and difference on indexes efficiently, e.g.:

此外，我想有效地执行联合和差异等操作，例如：

let a = M.singleton 42 $ M.singleton "Bob" $ S.singleton $ User { ... }
    b = M.singleton 42 $ M.singleton "Tim" $ S.singleton $ User { ... }
    c = union a b -- contains both Bob and Tim

I've tried to model this as follows:

我试图将其建模如下：

module Concelo.Index
  ( index
  , union
  , subtract
  , lastValue
  , subIndex ) where

import Prelude (($), (>>>), flip, Unit, unit, class Ord)
import Control.Monad ((>>=))
import Data.Map as M
import Data.Set as S
import Data.Maybe (Maybe(Nothing, Just), fromMaybe)
import Data.Tuple (Tuple(Tuple))
import Data.Foldable (foldl)
import Data.Monoid (mempty)

class Index index key value subindex where
  isEmpty :: index -> Boolean
  union :: index -> index -> index
  subtract :: index -> index -> index
  lastValue :: index -> Maybe value
  subIndex :: key -> index -> subindex

instance mapIndex :: (Index subindex subkey value subsubindex) =>
                     Index (M.Map key subindex) key value subindex where
  isEmpty = M.isEmpty

  union small large =
    foldl (m (Tuple k v) -> M.alter (combine v) k m) large (M.toList small)
    where
      combine v = case _ of
        Just v' -> Just $ union v v'
        Nothing -> Just v

  subtract small large =
    foldl (m (Tuple k v) -> M.alter (minus v) k m) large (M.toList small)
    where
      minus v = (_ >>= v' ->
                  let subindex = subtract v v' in
                  if isEmpty subindex then Nothing else Just subindex)

  lastValue m = M.findMax m >>= (_.value >>> lastValue)

  subIndex k m = fromMaybe mempty $ M.lookup k m

instance setIndex :: (Ord value) => Index (S.Set value) Unit value Unit where
  isEmpty = S.isEmpty

  union = S.union

  subtract = flip S.difference

  lastValue s = Nothing -- todo: S.findMax

  subIndex _ _ = unit

index f = foldl (acc v -> union (f v) acc) mempty

However, the Purescript compiler doesn't like that:

但是，Purescript编译器不喜欢这样：

Compiling Concelo.Index
Error found:
in module Concelo.Index
at /home/dicej/p/pssync/src/Concelo/Index.purs line 24, column 1 - line 44, column 49

  No type class instance was found for

    Concelo.Index.Index subindex0
                        t1       
                        t2       
                        t3       

  The instance head contains unknown type variables. Consider adding a type annotation.

in value declaration mapIndex

where subindex0 is a rigid type variable
      t1 is an unknown type
      t2 is an unknown type
      t3 is an unknown type

See https://github.com/purescript/purescript/wiki/Error-Code-NoInstanceFound for more information,
or to contribute content related to this error.

My understanding of this message is that I haven't properly stated that map values in the mapIndex instance are themselves Index instances, but I don't know how to fix that. Where might I add a type annotation to make this compile? Or am I even on the right track given what I'm trying to do?

我对这条消息的理解是，我没有正确说明mapIndex实例中的map值本身就是Index实例，但我不知道如何修复它。我可以在哪里添加类型注释来进行编译？考虑到我正在尝试做什么，我还是在正确的轨道上？

1 个解决方案

#1

This is almost certainly because PureScript currently lacks functional dependencies (or type families) which makes this kind of information un-inferrable. There's a writeup of the issue here: https://github.com/purescript/purescript/issues/1580 - it is something we want to support.

这几乎可以肯定，因为PureScript目前缺少功能依赖（或类型系列），这使得这种信息无法推断。这里有一个问题的写法：https：//github.com/purescript/purescript/issues/1580 - 这是我们想要支持的。

There was a discussion about a case very similar to this today as it happens: https://github.com/purescript/purescript/issues/2235

今天有一个与今天非常相似的案例的讨论：https：//github.com/purescript/purescript/issues/2235

Essentially, the problem here is that the functions of the class do not use all of the type variables, which means there's no way to propagate the information to the constraint for looking up a suitable instance.

本质上，这里的问题是类的函数不使用所有类型变量，这意味着无法将信息传播到约束以查找合适的实例。

I don't really have a suggestion for how to do what you're after here with things as they are, aside from avoiding the class and implementing it with specific types in mind.

我并没有真正的建议，除了避免课程并以特定类型实现它之外，如何在这里完成你所做的事情。

#1