recursion in ocaml nested lists

Question

I am new to Ocaml and am writing code to substitute elements in nested Ocaml lists. My code is as follows:

type 'a sexp = S of 'a | L of 'a sexp list

My substitution function(it replaces all occurrences of element a with b in nested lists) is as follows:

let rec subst a b list = 
  match list with
  | [] -> list
  | S s :: t -> 
      if s = a then (S b) :: (subst a b t) 
      else (S s) :: (subst a b t)
  | L l :: t -> (subst a b l) :: (subst a b t)

Despite multiple attempts(for nearly 6 hours), I have not been able to compile this code.. Please help!

Answer 1

Can I suggest to first write a function subst of type 'a -> 'a -> 'a sexp -> 'a sexp instead? It would read

let subst x y sexp =
  let rec visit = function
    | S z -> S (if z = x then y else z)
    | L sexps -> L (List.map visit sexps)
  in
  visit sexp

and arguably nicely and idiomatically captures the idea of recursing over an sexp.

Now, to obtain a function to operate on lists rather than single sexps, you can easily define a function subst_list of type 'a -> 'a -> 'a sexp list -> 'a sexp list:

let subst_list x y sexps = List.map (subst x y) sexps

---

Even nicer is to abstract away from substitution and have a more generally applicable function map of type ('a -> 'b) -> 'a sexp -> 'b sexp for performing structure-preserving mappings of sexps:

let map f sexp =
  let rec visit = function
    | S x -> S (f x)
    | L sexps -> L (List.map visit sexps)
  in
  visit sexp

And then define subst in terms of map and subst_list, as before, in terms of subst:

let subst x y sexp = map (fun z -> if z = x then y else z) sexp
let subst_list x y sexps = List.map (subst x y) sexps