CODEWITHSUNDEEP
dictionaryocaml
elvara
elvara

Reputation: 23

OCaml Self-Referential Map

I'm looking to add a cache to a simple compiler in OCaml. I have created a simpler version of the code that I had that reproduces the same issue. What I need for the cache is to be able to create a Map with A's as keys, so I can lookup the compile output. Here is the code:

module A
= struct

  type ineq =
  | LT
  | EQ
  | GT

  type t =
  ...

  module ACacheMapKey
  = struct

    type t = t

    let compare a b =
      match cmp a b with
      | LT -> -1
      | EQ -> 0
      | GT -> 1

  end

  module CMap = Map.Make(ACacheMapKey)
  let cache_map = CMap.empty

  let cmp a b =
    ...

end

In module A, type t is a recursive AST-like type. cmp a b returns a ineq. The compile function was left out for brevity, but it just uses the cache before running through a computationally expensive process. In order to create a cache map in A, I need a compatible key module. My attempt at that is ACacheMapKey, but the type t = t doesn't refer to the parent. The error it gives is Error: The type abbreviation t is cyclic. So, is there a better way to make a cache over A? Or is there an easy way to reference the parent and make my current structure work?

Upvotes: 2

Views: 122

Answers (1)

glennsl
glennsl

Reputation: 29126

Type definitions, unlike let bindings, are recursive by default. So similarly to how you would make a let binding recursive by using the rec keyword:

let rec f = ...

you can make a type definition non-recursive by using the nonrec keyword:

type nonrec t = t

Upvotes: 2

Related Questions