Implémentation d'un cache

Question

J'essaie d'implémenter un cache transparent qui peut charger un objet spécifique lorsqu'il n'est pas disponible ou retourner un objet déjà existant indexé par (name).

J'ai essayé de courir ceci:

loader' objs name = case findObj objs name of 
    Nothing → (new_obj, loader' new_objs) 
    Just obj → (obj, loader' objs) 
    where 
    new_objs = [(name, new_obj)] ++ objs 
    new_obj = readObj name 
loader = loader' [] 

mais je reçois un

 
Occurs check: cannot construct the infinite type: 
    t = (ObjType, String -> t) 

qui ressemble exactement à ce que je veux :)

Comment puis-je fixer la fonction pour qu'il compile?

Clarifications:

Comme demandé, les signatures (findObj renvoie soit une valeur connue trouvée via une clé, ou rien, readObj crée une nouvelle obj pour une clé):

findObj :: [(String, ObjType)] -> String -> Maybe ObjType 
readObj :: String -> ObjType 

Et oui - je besoin d'un cache, car les clés sont des noms de fichiers et je ne veux pas lire + analyser le fichier chaque fois qu'un objet est nécessaire.

Answer 1

Deux pensées (de vagues suppositions?), Il semble que si elle ne parvient pas à produire la signature de type droit dans la clause Just obj et/ou de readObj name, et il pourrait être intéressant d'essayer quelque chose comme ceci:

loader' :: [(String, ObjType)] -> String -> (ObjType, String -> ObjType) 
loader' objs name = case findObj objs name of 
    Nothing → (new_obj, loader' new_objs) where 
    new_objs = [(name, new_obj)] ++ objs 
    new_obj = readObj name 
    Just obj → (obj, loader' objs) 
loader = loader' [] 

Je ne dis pas que cela va le réparer (mais je suppose que cela pourrait); Je dis plutôt que cela peut transformer le problème en un problème plus logique ou éclaircir la situation.

Edit:

Application de la suggestion de Tom Lokhorst de nommer le type de cache nous amène à ceci:

type Cache = [(String, ObjType)] 
loader' :: Cache -> String -> (ObjType, ????) 
loader' objs name = case findObj objs name of 
    Nothing → (new_obj, loader' new_objs) where 
    new_objs = [(name, new_obj)] ++ objs 
    new_obj = readObj name 
    Just obj → (obj, loader' objs) 
loader = loader' [] 

qui le rend évident que le problème est. Le type du deuxième résultat du chargeur 'est une fonction qui prend une chaîne et produit une paire composée d'un ObjType et une fonction qui prend une chaîne et produit une paire composée d'un ObjType et une fonction qui prend une chaîne et produit une paire consistant en un ObjType et une fonction qui prend une chaîne et produit une paire composée d'un ObjType et ... vous obtenez l'image.

Si vous réécrivez comme ceci:

type Cache = [(String, ObjType)] 
loader' :: Cache -> String -> (ObjType, Cache) 
loader' objs name = case findObj objs name of 
    Nothing → (new_obj, new_objs) where 
    new_objs = [(name, new_obj)] ++ objs 
    new_obj = readObj name 
    Just obj → (obj, objs) 

il devrait compiler, mais vous devrez changer la façon dont vous l'utilisez.

Answer 2

Vous pouvez regarder this implementation de la mise en cache dans haskell.

Answer 3

Pourquoi pas simplement memoize findObj?

Answer 4

Haskell ne supporte pas les types comme ceci:

type t = Int -> t 

En effet, le compilateur essaie de se dérouler ce type, pour saisir le vérifier. Comme le système de type est strict, cela se traduira par une boucle infinie lors du contrôle de type.Maintenant, ce serait bien d'avoir un système de type plus paresseux, que ce que vous seriez capable de faire, mais ce n'est pas Haskell pour le moment. Toutefois, comme le dit MarkusQ, il est plus facile de changer simplement ce que fait la fonction loader'. Je pense que je l'écrire quelque chose comme ceci:

type Cache = [(String, ObjType)] 

loader' :: Cache -> String -> (ObjType, Cache) 

C'est une fonction qui prend le cache et la chaîne de recherche, de retour à la fois la réponse et le cache (peut-être mis à jour).