Реализация кеша

Question

Я пытаюсь реализовать прозрачный кеш, который может загружать определенный объект, когда он недоступен, или возвращать уже существующий объект, проиндексированный (name).

Я пытался запустить это:

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' []

но я получаю

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

, который выглядит именно так, как я хочу :)

Как я могу исправить функцию, чтобы она компилировалась?

Разъяснения:

По запросу подписи (findObj либо возвращает известное значение, найденное с помощью ключа, либо Nothing, readObj создает новый объект для ключа):

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

И да - мне нужен кеш, потому что ключи - это имена файлов, и я не хочу читать + анализировать файл каждый раз, когда нужен какой-то объект.

Answer 1

Haskell не поддерживает такие типы:

type t = Int -> t

Это потому, что компилятор пытается развернуть этот тип, чтобы проверить его. Поскольку система типов достаточно строгая, это может привести к бесконечному циклу во время проверки типа. Теперь было бы неплохо иметь более ленивую систему типов, чем вы могли бы сделать, но на данный момент у нее нет Haskell.

Однако, как говорит MarkusQ, проще просто изменить то, что делает функция loader'. Я думаю, что написал бы что-то вроде этого:

type Cache = [(String, ObjType)]

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

Это функция, которая берет кеш и строку поиска, возвращая как ответ, так и (возможно, обновленный) кеш.

Answer 2

Почему бы просто не запомнить findObj?

Answer 3

Две мысли (дикие догадки?) Выглядит так, как будто не удается создать правильную сигнатуру типа в предложении Just obj и / или из readObj name, и может быть интересно попробовать что-то вроде этого:

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' []

Я не говорю, что это исправит (но я полагаю, что это может); скорее я говорю, что это может превратить проблему в проблему, которая имеет больше смысла, или иным образом пролить свет на ситуацию.

Edit:

Применение предложенного Томом Локхорстом названия типа кэша приводит нас к следующему:

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' []

что делает очевидным, в чем проблема. Тип второго результата loader '- это функция, которая принимает строку, и создает пару, состоящую из ObjType, и функцию, которая принимает строку, и создает пару, состоящую из ObjType, и функция, которая принимает строку, и создает пару. состоящий из ObjType и функции, которая принимает строку и создает пару, состоящую из ObjType и ... вы получите картинку.

Если переписать это так:

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)

он должен скомпилироваться, но вам придется изменить способ его использования.

Answer 4

Возможно, вы захотите взглянуть на эту реализацию кэширования в haskell.