Iterate through nested list data type in OCaml-CodePudding

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?

CodePudding user response：

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.

CodePudding user response：

The answer provided by @glennsl is great, but let's look at what your code is doing to see why it gives you the result you saw.

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

You then evaluated to_str se where se is List [Atom "a"; List [Atom "b"; Atom "c"]; Atom "d"; Atom "e"].

to_str (List [Atom "a"; List [Atom "b"; Atom "c"]; Atom "d"; Atom "e"])

to_str (Atom "a") ^ to_str (List [List [Atom "b"; Atom "c"]; Atom "d"; Atom "e"])

"a" ^ (to_str (List [Atom "b"; Atom "c"]) ^ to_str (List [Atom "d"; Atom "e"]))

"a" ^ (to_str (Atom "b") ^ to_str (List [Atom "c"]))
    ^ (to_str (Atom "d") ^ to_str (List [Atom "e"]))

"a" ^ ("b" ^ (to_str (Atom "c") ^ to_str (List [])))
    ^ ("d" ^ (to_str (Atom "e") ^ to_str (List [])))

"a" ^ ("b" ^ ("c" ^ ""))
    ^ ("d" ^ ("e" ^ ""))

"a" ^ ("b" ^ "c") ^ ("d" ^ "e")

"a" ^ "bc" ^ "de"

"abcde"