EOPL - 1.2.4 - Exercise 1.18

Exercise 1.18 takes advantage of Scheme's uniform treatment of code and data, so the functions proposed should return lists that can be evaluated to get some effect. Furthermore, there are typing issues, so adaptations are needed. The first function, compose, is easy enough:

let compose p1 p2 = fun x -> p1 (p2 x)

Next, I defined a data type to represent list operations:

type ListOp = Car | Cdr | Compose of ListOp * ListOp | Error

So it's easy to define car_cdr, but it doesn't return a list to evaluate, rather a ListOp object. Also, because of typing it was easier to include a variant Error of type ListOp and eliminate parameter errval.

let rec car_cdr s slist =
    match slist with 
      [] -> Error 
    | s1 :: rslist when s1 = s -> Car
    | _ :: rslist -> Compose (car_cdr s rslist, Cdr)

Thus we get

> car_cdr "c" ["a"; "b"; "c"];;
val it : ListOp = Compose (Compose (Car,Cdr),Cdr)

So we have a description of the necessary list operations, but it's not directly executable as in Scheme. So we need a function to execute the list operations returned on a list, and this is run_listop

let rec run_listop op lst = 
    match op with
      Car -> List.hd lst
    | Compose (c1, Cdr) -> run_listop c1 (List.tl lst)
    | _ -> failwith "can't do"

The case that leads to an exception is to find a single Cdr without a previous Car. This is a good indication that the type was not designed properly, but we will not bother with this here. Function car_cdr2 doesn't need explicit Compose operations, and returns a list of list operations that must be applied in succession.

let car_cdr2 s slist errval =
    let rec loop lst =
        match lst with
          [] -> []
        | l :: rlst when s = l -> [Car]
        | _ :: rlst -> Cdr :: (loop rlst) in
    List.rev (loop slist)

It's quite easy to define a function to execute these ListOp lists, but not that interesting at this point.