CODEWITHSUNDEEP
treeocaml
qiubit
qiubit

Reputation: 4816

OCaml - converting trees with references to normal trees

I've got 2 types of trees:

type ref_tree = Node of int * ref_tree list ref
type tree = Node of int * tree list

I want to write a function convert: ref_tree -> tree which gets tree with neighbours saved as references to list containing them and outputs a tree where references are changed to normal lists. Here's what I tried:

let rec convert t =
        match t with
        | Node (x, l) ->
            if (!l = []) then Node (x, []) else
            Node (x, (List.map convert !l))

But OCaml returns an error when trying to compile it:

if (!l = []) then Node (x, []) else
Error: This expression has type 'a list
       but an expression was expected of type tree list ref

Where This expression points at empty list inside Node (x, []). Why is there a type mismatch?

Upvotes: 1

Views: 114

Answers (2)

Marth
Marth

Reputation: 24812

The problem here is that you define two constructor Node, with the second definition (type tree = Node of …) shadowing the first one.

This means that when you're matching against t and destructuring it as Node(x, l), OCaml sees this as a tree, not a ref_tree (and as a consequence sees l as a tree list instead of a ref_tree list ref)

One way to fix this is to change the ref_tree constructor :

# type ref_tree = Ref_node of int * ref_tree list ref;;
type ref_tree = Ref_node of int * ref_tree list ref

# let rec convert t =
          match t with
          | Ref_node (x, l) ->
              if (!l = []) then Node (x, []) else
              Node (x, (List.map convert !l));;
val convert : ref_tree -> tree = <fun>

(another way would be to define those types in modules Tree and RefTree and using Tree.Node and RefTree.Node)

Upvotes: 2

Ramon Snir
Ramon Snir

Reputation: 7560

The compiler gets confused between your two Node constructors (one of ref_tree and one of tree). You can help it out in various ways, including:

let rec convert t =
  match (t : ref_tree) with
  | Node (x, l) ->
     if (!l = []) then Node (x, []) else
       Node (x, (List.map convert !l))

Upvotes: 1

Related Questions