CODEWITHSUNDEEP
functional-programmingocaml
user2352241
user2352241

Reputation: 81

recursion in ocaml nested lists

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!

Upvotes: 0

Views: 2220

Answers (3)

Stefan Holdermans
Stefan Holdermans

Reputation: 8050

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

Upvotes: 3

Shredderroy
Shredderroy

Reputation: 2920

Note: using an F# compiler here; I don't have an OCaml compiler on this computer.

The last line of your subst function has an error: It should be as follows:

| L l :: t -> L (subst a b l) :: (subst a b t)

So the complete code would look like this:

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

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

let test () =
    let (lst : int Sexp list) = [S 1; L [S 2; L [S 3]; S 4]; S 5]
    let a = 2
    let b = 3
    subst a b lst

The output of test() is

[S 1; L [S 3; L [S 3]; S 4]; S 5]

The reason is that your function subst returns a 'a Sexp list. If you omit the L constructor from the last line, then subst a b l is of type 'a Sexp list, which you are attempting to cons with another list of type 'a Sexp list. This does not work.

Nor was this your intention, since you wanted to end up with an entity of type 'a Sexp list, which means you must cons an element of type 'a Sexp with a list of type 'a Sexp list. By specifying the L constructor, you are creating an element of type 'a Sexp list, which you can now cons with the rest of the list.

Upvotes: 2

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66823

It looks like your function subst is supposed to return something of type 'a sexp list. That's what the first and second match cases return.

In the third match case, then, your returned value is:

(subst a b l) :: (subst a b t)

Since your function returns 'a sexp list, this type doesn't make a lot of sense. The head of the list is of type 'a sexp list and the tail of the list is also of type 'a sexp list. It's very difficult to come up with any lists that have this kind of structure. I think what you want is for the head of the list to be of type 'a sexp.

If you want the head of the list to be of type 'a sexp, you need some way of packaging up a list of things into a single 'a sexp. If this isn't enough of a hint, look at your L constructor. That's exactly what it does.

Upvotes: 1

Related Questions