Implementing a cache

Question

Hi,

I'm trying to implement a transparent cache that can load a specific object when it's not available, or return an already existing object indexed by (name).

I've tried running this:

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

but I'm getting a

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

which looks exactly like something I want :)

How can I fix the function so that it compiles?

Clarifications:

As requested, signatures (findObj either returns a known value found via a key, or Nothing, readObj creates a new obj for a key):

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

And yes - I need a cache, because the keys are filenames and I don't want to read+parse the file each time some object is needed.

Answer 1

You might want to look at this implementation of caching in haskell.

Answer 2

Why not just memoize findObj?

Answer 3

Two thoughts (wild guesses?) it looks as if it is failing to produce the right type signature in the Just obj clause and/or from readObj name, and it might be interesting to try something like this:

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

I'm not saying that that will fix it (but I suppose that it might); rather, I'm saying that it may transform the problem into one that makes more sense, or otherwise shed light on the situation.

Edit:

Applying Tom Lokhorst's suggestion of naming the cache type leads us to this:

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

which makes it obvious what the problem is. The type of the second result of loader' is a function that takes a string an produces a pair consisting of an ObjType and a function that takes a string an produces a pair consisting of an ObjType and a function that takes a string an produces a pair consisting of an ObjType and a function that takes a string an produces a pair consisting of an ObjType and ... you get the picture.

If you rewrite it like this:

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)

it should compile but you'll have to change how you use it.

Answer 4

Haskell doesn't support types like this:

type t = Int -> t

This is because the compiler tries to unfold this type, to type check it. Since the type system is quit strict, this would result in an infinite loop during type checking. Now it would be nice to have a more lazy type system, than you would be able to do this, but, that's not has Haskell at the moment.

However, as MarkusQ says, its easier just to change what the loader' function does. I think I would write it something like this:

type Cache = [(String, ObjType)]

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

That is a function taking the cache and the search string, returning both the answer and the (possibly updated) cache.