Wie soll ich einen typsicheren Index in Purescript modellieren?

Question

In meiner Anwendung möchte ich Gruppen von Objekten in einer typsicheren Weise mit einer Struktur indexieren, die einem relationalen Datenbankindex ähnelt. Zum Beispiel könnte ich eine Reihe von Benutzerobjekten indizieren möge, basierend auf Alter und Namen:

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

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

Außerdem würde Ich mag Operationen wie union und difference auf Indizes effizient zu tun, zum Beispiel:

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 

ich habe versucht, dies zu modellieren wie folgt:

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 

Allerdings ist die PURESCRIPT-Compiler wie das nicht:

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. 

Mein Verständnis dieser Nachricht ist, dass ich nicht richtig festgestellt, dass Kennfeldwerte in der mapIndex Instanz selbst Index Instanzen, aber ich weiß nicht, wie das zu beheben. Wo kann ich eine Typannotation hinzufügen, um diese Kompilierung durchzuführen? Oder bin ich angesichts dessen, was ich zu tun versuche, sogar auf dem richtigen Weg?

Answer 1

Dies ist fast sicher, weil PureScript derzeit keine funktionalen Abhängigkeiten (oder Typenfamilien) aufweist, die diese Art von Informationen uninterferabel machen. Es gibt eine Beschreibung des Problems hier: https://github.com/purescript/purescript/issues/1580 - es ist etwas, was wir unterstützen möchten.

Es gibt eine Diskussion über einen Fall sehr ähnlich wie diese heute war, wie es geschieht: https://github.com/purescript/purescript/issues/2235

Wesentlichen hier das Problem ist, dass die Funktionen der Klasse nicht alle der Typ-Variablen verwenden, was bedeutet, dass es keine ist Möglichkeit, die Information an die Bedingung weiterzugeben, um eine geeignete Instanz nachzuschlagen.

Ich habe nicht wirklich einen Vorschlag, wie man das macht, was man hier mit den Dingen machen will, abgesehen davon, dass man die Klasse vermeidet und sie mit bestimmten Typen implementiert.