4

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.

3
  • I think we'll need to see the definitions of findObj and readObj Mar 7, 2009 at 0:49
  • Do you even need the concept of a cache in a functional language? I always thought it would an imperative optimization. Mar 7, 2009 at 0:56
  • added signatures for findObj, readObj
    – viraptor
    Mar 7, 2009 at 1:05

4 Answers 4

2

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.

2

Why not just memoize findObj?

2

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.

1
  • The combination of your renaming and my restructuring shows very clearly what the problem is. I amended my answer to use your idea of naming the Cache, credited you & also voted your answer up.
    – MarkusQ
    Mar 7, 2009 at 16:30
0

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

1
  • I don't think I need something that heavy - I need a single-thread file loader... Also - I wanted to know how to solve my problem in general (a function returning itself, partially applied)
    – viraptor
    Mar 7, 2009 at 1:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.