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

Question

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

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

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

此外，我想有效地对索引进行 union 和 difference 等操作，例如：

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

我试过如下建模：

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

但是，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.

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

Answer 1

这几乎可以肯定是因为 PureScript 当前缺少功能依赖项（或类型族），这使得此类信息无法推断。这里有一篇关于这个问题的文章：https://github.com/purescript/purescript/issues/1580 - 这是我们想要支持的东西。

今天发生了一个与此非常相似的案例讨论：https://github.com/purescript/purescript/issues/2235

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

除了避免 class 并在考虑特定类型的情况下实现它之外，我真的没有关于如何按原样做你想做的事情的建议。

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

How should I model a type-safe index in Purescript?

indexing

typeclass

data-structures

purescript