Another sample question on the hard side

In this problem, you are to write an interpreter for a small fragment of HTML. We are considering a tiny fragment of HTML that includes plain text, lists (numbered and plain), and sequences. The grammar for this fragment is:

type html = 
    Text of string
  | Sequence of html * html
  | Numbered_list of html list
  | Plain_list of html list

The interpreter takes HTML descriptions as above and produces formatted output. For example, running:

go (Sequence (Text "Hello...Testing lists",
    Plain_list
     [Text "one";
      Text "two";
      Sequence (Text "three", 
                Plain_list 
                 [Text "one nested one level";
                  Text "two nested one level";
                  Sequence (Text "three nested one level",
                            Numbered_list
                              [Text "one nested two levels";
                               Text "two nested two levels"]);
                  Text "four nested one level"])]))

should produce:

Hello...Testing lists
	one
	two
	three
		one nested one level
		two nested one level
		three nested one level
			1. one nested two levels
			2. two nested two levels
		four nested one level

Here is the beginning of that interpreter:

let go html = 
  let formatted_string = interp html "" [] in
  Printf.printf "%s\n" formatted_string 

and interp html indent nums = 
  match html with
    Text s -> s 
  | Sequence (h1,h2) -> interp h1 indent nums ^ interp h2 indent nums
  | Plain_list hs -> interp_plain hs (indent ^ "\t") nums 
  | Numbered_list hs -> interp_numbered hs (indent ^ "\t") (ref 1 :: nums) 

and interp_plain hs indent nums = 
  match hs with 
    [] -> ""
  | [h] -> "\n" ^ indent ^ interp h indent nums 
  | (h::hs) -> 
      "\n" ^ indent ^ interp h indent nums ^ 
      interp_plain hs indent nums

and interp_numbered hs indent nums = 
  match hs with 
  ...

Complete the implementation of interp_numbered. The idea here is that nums is acting like environment which keeps track of the current numbers of the list items. The following example illustrates the basic idea:

1. ...              env = ref 1 :: []
2. ...              env = ref 2 :: []
    1. ...          env = ref 1 :: ref 2 :: []
    2. ...          env = ref 2 :: ref 2 :: []
    3. ...          env = ref 3 :: ref 2 :: []
    4. ...          env = ref 4 :: ref 2 :: []
3. ...              env = ref 3 :: []

Ocaml hint: Given the int 3, you can produce the string "3. " by writing:

string_of_int 3 ^ ". "

Another sample question on the hard side

Solution