type error in ocaml - This expression has type (string * 'a) list, but is used with type exp

Question

I, i have this simple program in ocaml

type tree = Node of string * exp * tree * tree | Empty 

and exp = Etree of tree |  EInt of int  | List of (string*exp);;

let rec evalNode.......



and rec eval (e:exp) =
(match e with
     | EInt _ -> e
     | Etree(tree) -> (match tree with 
         | Empty -> [] 
         | Node(s,i,t1,t2) -> (evalNode (tree)) )

  )

evalNode : tree -> (string * exp) list = fun

eval : exp -> exp = fun

but return this error but i don't undestand what does means, there aren't much information of ocaml in the web:

This expression has type (string * 'a) list, but is used with type exp.

Etree has a type Node inside, so is type tree, so i can call evalNode with this value because it want a tree type

evalNode return a list of (string*exp) but is a exp so eval can return this

I think you might confuse List of (string*exp) for (string*exp) list — glennsl
I believe @glennsl nailed it, but without the location of the error source, without the actual code, we can only guess your problem! — camlspotter

Keith Irwin Keith Irwin · Accepted Answer · 2018-01-22T20:28:15

Any expression in Ocaml has to return a single type. So, for example, you can't write something like if a>b then "a" else 7 because it doesn't know whether the type of that expression is string or int.

In your eval function, without meaning to, you're doing something similar. When e is an EInt the first matching option is triggered and it returns e which has type exp. When e is an Etree(Empty) it triggers the second matching option which in turn calls the second match statement and the first matching option within that is triggered, returning [], which is a list having type 'a list (meaning list of unknown type). When e is an Etree(Node(s,i,t1,t2)) the second matching option in the second match statement is triggered, returning evalnode(tree) which we know from what you've written to have type (string * exp) list.

So, the inner match, by itself is fine since it can unify a generic list with a specific list. But combining the outer match is problematic since the first case returns an exp and the second case returns a (string * exp) list so it doesn't know what type the expression should have. I'm not sure why the error says (string * 'a) list rather than (string * exp) list but I suspect you can fix things without having to work that out.

I do also want to note that you have a constructor List of (string*exp) whose subtype is not a list. You may wish this to be List of (string*exp) list and then to have your inner match return List([]) and List(evalNode(tree)) but that's just a guess.

type error in ocaml - This expression has type (string * 'a) list, but is used with type exp

2 Answers