listrecursionocaml

Iterate through nested list data type in OCaml


I'm trying to iterate through the Sexp.t data type, defined in the Jane Street Sexplib module. I want to print out the data type in a way that shows its recursive structure for debugging. So far, this is what I have:

type sexp =
  | Atom of string
  | List of sexp list

(* pretty prints an sexp *)
let rec to_str (se : sexp) : string =
  match se with
  | Atom s -> s
  | List [] -> ""
  | List (hd :: tl) -> to_str hd ^ to_str (List tl)

let () =
  let se = List [Atom "a"; List [Atom "b"; Atom "c"]; Atom "d"; Atom "e"] in
  print_endline (to_str se)

The output is abcde, a flattened list. I'm hoping to print it out as something similar to:

List [Atom "a"; List [Atom "b"; Atom "c"]; Atom "d"; Atom "e"]

I've made a few attempts that got messy fast. I'm just not sure what the recursive case is supposed to look like. Can someone please help me out?


Solution

  • This isn't very efficient, but makes very few changes to your function, and should hopefully be easy to understand:

    let rec to_str (se : sexp) : string =
      match se with
      | Atom s -> Printf.sprintf "Atom \"%s\"" s
      | List [] -> ""
      | List items ->
        let items = items |> List.map to_str |> String.concat "; " in
        Printf.sprintf "List [%s]" items
    

    which prints

    List [Atom "a"; List [Atom "b"; Atom "c"]; Atom "d"; Atom "e"]
    

    It uses Printf.sprintf for convenience, but could still use plain string concatenation if you want to. A more efficient version could use Format.fprintf instead.