cyclic types

[Radu Grigore <radugrigore@gmail.com>]

Why are cyclic types forbidden?

I was forced to use the definition:
  type forest = Forest of forest StringMap.t | Empty
where I would have rather used
  type forest = forest StringMap.t
The error is:
  The type abbreviation tree is cyclic

I can see that the later would require type annotations such as
  StringMap.empty : forest
because otherwise the compiler could never infer that some expression
has type forest.  But this is a rather minor nuisance compared to the
need to match Forest/Empty all over the place. You could write:

let rec make n sf = match n, sf with
  [], [] -> StringMap.empty : forest
| nh :: nt, sfh :: sft ->
  let m = make nt sft in
  StringMap.add nh sfh m
| _ -> failwith "n and sf should have the same number of elements";;

let rec iter func frst =
  let nf el sub_frst = func el; iter func sub_frst in
  StringMap.iter nf frst;;
 
Instead of what you need to write now:

let rec make n sf = match n, sf with
  [], [] -> Empty
| nh :: nt, sfh :: sft -> begin
    match make nt sft with
      Empty -> Forest (StringMap.add nh sfh StringMap.empty)
    | Forest m -> Forest (StringMap.add nh sfh m) end
| _ -> failwith "blabla..";;

let rec iter func frst =
  let nf el sub_frst = func el; iter func sub_frst in
  match frst with
    Empty -> ()
  | Forest m -> StringMap.iter nf m;;

It feels strange to be forced to explicitly treat the case of an empty
map, which is what actually happens in the code that compiles. The
first version of make/iter seems better, but it does not compile :(

Also, the type definition
  type forest = forest StringMap.t option
fails with the same error (cyclic type) although it looks a lot like
the version that works. Why?

-- 
regards,
 radu
http://rgrig.idilis.ro/