What do you do when you have trouble grokking a recursive algorithm?

Learning
1

Learning OCaml has made me much more comfortable dealing with recursive functions. I thought I had a good grasp of them until recently.

I’ve been going through the 99 OCaml problems, available here: Exercises

And found exercise 26 - Generate the combinations of K distinct objects chosen from the N elements of a list. quite challenging actually.

After failing many times and giving it a few days, I realized I wasn’t making any significant progress so I peeked at the proposed solution for inspiration.

Side note, as I explored I also found that Haskell’s list comprehension feature could help, but in a static way so not quite satisfying.

ghci> [ (i,j) | i <- [1..4], j <- [i..4], i /= j ]
[(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)]

ghci> [ (i,j,k) | i <- [1..4], j <- [i..4], k <- [j..4], i /= j && j /= k ]
[(1,2,3),(1,2,4),(1,3,4),(2,3,4)]

This is what I came up with (I can only encourage you to give it a go before taking a look). Assume there may be spoilers after this opening post.

let extract n lst =
  let rec aux acc rest n =
    if n = 0 then
      [ List.rev acc ]
    else
      match rest with
      | [] -> []
      | x :: xs -> aux (x :: acc) xs (n - 1) @ aux acc xs n
  in
  aux [] lst n
;;

I wasn’t too pleased with the list append + the fact that the function didn’t look tail call optimized so I kept working on it and got this for a v2:

let extract n lst =
  let () = if n <= 0 then raise @@ Invalid_argument "n must be positive" in
  (* outer = [inner, inner, inner, ...] *)
  let rec aux n lst (inner : 'a list) (outer : 'a list list) : 'list list =
    if n = 0 then
      List.rev inner :: outer
    else
      match lst with
      | [] -> outer
      | x :: xs ->
          let new_outer = aux (n - 1) xs (x :: inner) outer in
          aux n xs inner new_outer
  in
  aux n lst [] [] |> List.rev

So far so good? Well not quite. I don’t know what it is about this exercise but I have a mental block on it. I feel that I haven’t really developed a complete understanding of it. If I were to give it a go again in a few weeks, I’d probably struggle with it just as much.

This is in contrast with simpler recursive problems, whereas I had an epiphany and internalized the solution.

I explored various ideas, such as trying to analyze the problem with fancy tools (not OCaml related), or simply typing out the steps of execution but then I kinda loose track and I’m back at square 1.

-(aux [] ['A','B','C','D'] 3)-
  -@-
    -aux (['A']) ['B','C','D'] 2-
      -@-
        -aux (['B','A']) ['C','D'] 1-
          -@-
            -aux (['C', 'B','A']) ['D'] 0-
              -@-
                -['A','B','C']- oops, I'm starting to loose track here
                -aux (['C', 'B','A']) ['D'] 1-
            -aux (['B','A']) ['D'] 1-
        -aux (['A']) ['C','D'] 2-
    -aux [] ['B','C','D'] 3-

I also tried to print values but that didn’t help much, I guess it’s because the relation of the log messages, the expansion of the tree, and the final product isn’t very clear to me.

So, do you have any tips? What do you do when you have a mental block like that? I mean, specifically related to recursion.

2 Likes
2

First, a caveat: I’m a mathematician.
The answer

We all know that there are C(12,3) = 220 possibilities

only holds true if the list consists of N pairwise distinct elements (is a set of N elements). If the list contains for example less than K pairwise distinct elements, the answer is (well, should be) the empty list [].
The proposed solution does not work for e.g.

# extract 4 [1; 1; 1; 1; 1];;
- : int list list =
[[1; 1; 1; 1]; [1; 1; 1; 1]; [1; 1; 1; 1]; [1; 1; 1; 1]; [1; 1; 1; 1]]

I do not think about recursion at all if the problem itself isn’t obviously recursive (like a recursive data structure: linked list, tree, unary number, …).

I just try to solve the problem at hand and see where that leads to.
Let’s pick 3 numbers out of 5 (WLOG we use the numbers 1 to 5), C(5,3) = 10, so we need to find 10 sets.

[1, 2, 3, 4, 5]

  • Let’s start with 1: How often can we choose 3 numbers that start with 1 out of 5? Well, that’s the same as 2 numbers out of 4, as we’ve already fixed the first number, 1. That’s C(4, 2) = 6 possibilities.
  • We can ignore 1, what’s left is [2, 3, 4, 5]. Oh, so now we can continue choosing 2 numbers out of 3 as 1 is ignored and 2 is fixed: C(3, 2) = 3
  • We already found 6 + 3 possibilities, so there is just one left. We can ignore 1 and 2 and choose 3. And there is really just one possibility left, [3, 4, 5]

So we see that the problem is recursive - actually “double” - and each step uses a shorter set. As soon as the number of elements of the set is the same as the number of elements we are supposed to choose, we are finished - which doesn’t work too well with lists, so we better calculate the length only once and subtract 1 from it at each recursion.

2 Likes
3

Thanks very much!

I like your demonstration of the stop condition. With that new hindsight, I tried to give the exercise another go but got confused again, in similar ways.

I’m slowly realizing that I missed a step by not learning about combinations in a more general form first.

I found this exercise to be clarifying:

Given a set of n things, there are 2n combinations.
Produce the combinations for the list [a, b, c]

1. []
2. [a]
3. [b]
4. [c]
5. [a,b]
6. [a,c]
7. [b,c]
8. [a,b,c]

This is what I got:

let rec combs lst =
  match lst with
  | [] -> [ [] ]
  | h :: t ->
      let left = combs t in
      let right = List.map (List.cons h) left in
      left @ right
;;

Mmm :thinking: this feels familiar

I graphed out the strategy first and that helped (a lot).

tmp
tmp760×461 23.7 KB

Graphiz is pretty nice to use, here’s the corresponding code snippet.

digraph {
    label = "Given a set of n things, there are 2n combinations.\nOur items='(a b c).\nWe discard on the left, cons on the right.";
    labelloc = "top";
    
    a1 -> {b1 b2} [label = "a";];
    
    b1 -> {c1 c2} [label = "b";];
    b2 -> {c3 c4} [label = "b";];
    
    c1 -> {d1 d2} [label = "c";];
    c2 -> {d3 d4} [label = "c";];
    c3 -> {d5 d6} [label = "c";];
    c4 -> {d7 d8} [label = "c";];
    
    a1 [label = "'()";];
    
    b1 [label = "'()";];
    b2 [label = "'(a)";];
    
    c1 [label = "'()";];
    c2 [label = "'(b)";];
    c3 [label = "'(a)";];
    c4 [label = "'(a b)";];
    
    d1 [label = "'()";];
    d2 [label = "'(c)";];
    d3 [label = "'(b)";];
    d4 [label = "'(b c)";];
    d5 [label = "'(a)";];
    d6 [label = "'(a c)";];
    d7 [label = "'(a b)";];
    d8 [label = "'(a b c)";];
}

I noticed I got surprised by the ordering. For instance, as I wrote the graph, I thought I would get at the last node ['C'; 'B'; 'A'] rather than ['A'; 'B'; 'C'].

So I think I’ll keep iterating on this simpler exercise. It’s just one step below difficulty wise and once mastered, I think I’ll probably understand problem 26 that much better.

4

Just a remark, this is called “the (number of) subsets of a given set” in mathematics.

Oh, and I forgot another important optimisation for combinations: for K > N the function should also return the empty list [] (or raise an exception).

If not, this happens:

# let repeat k n =
       let rec go acc k i = 
          match i with
          | 0 -> acc
          | i' -> go (k :: acc) k (i' - 1)
          in go [] k n ;; 
         
val repeat : 'a -> int -> 'a list = <fun>
# let l = repeat 5 100000;;
val l : int list =
  [5; 5; 5; ...
# extract 100001 l;;
5

In terms of visualising OCaml code execution, @JohnWhitington built a fantastic expression-stepping interpreter for his PhD a few years ago called ocamli. It only works with OCaml 4.05, but that should be enough for many of the examples on the OCaml website.

OCamli is a proof-of-concept step-by-step interpreter for OCaml programs intended for teaching purposes and, eventually, as a debugger. It works by reading an OCaml program into an abstract syntax tree, then interpreting the AST one reduction at a time, optionally displaying each reduction and underlining the reducible expression.

2 Likes
6

Good to know, thank you.

It looks like a really cool tool! In this case, the output is quite overwhelming though.

    combs ['A'; 'B'; 'C']
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let rec combs lst = (match lst with | [] -> [[]] | h::t -> let left = combs t in let right = List.map (fun lst -> h::lst) left in left @ right ) in let lst = ['A'; 'B'; 'C'] in (match lst with | [] -> [[]] | h::t -> let left = combs t in let right = List.map (fun lst -> h::lst) left in left @ right )
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let rec combs lst = (match lst with | [] -> [[]] | h::t -> let left = combs t in let right = List.map (fun lst -> h::lst) left in left @ right ) in (match ['A'; 'B'; 'C'] with | [] -> [[]] | h::t -> let left = combs t in let right = List.map (fun lst -> h::lst) left in left @ right )
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let rec combs lst = (match lst with | [] -> [[]] | h::t -> let left = combs t in let right = List.map (fun lst -> h::lst) left in left @ right ) in (match ['A'; 'B'; 'C'] with | h::t -> let left = combs t in let right = List.map (fun lst -> h::lst) left in left @ right )
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let rec combs lst = (match lst with | [] -> [[]] | h::t -> let left = combs t in let right = List.map (fun lst -> h::lst) left in left @ right ) in let t = ['B'; 'C'] in let h = 'A' in let left = combs t in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let rec combs lst = (match lst with | [] -> [[]] | h::t -> let left = combs t in let right = List.map (fun lst -> h::lst) left in left @ right ) in let h = 'A' in let left = combs ['B'; 'C'] in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let rec combs lst = (match lst with | [] -> [[]] | h::t -> let left = combs t in let right = List.map (fun lst -> h::lst) left in left @ right ) in let lst = ['B'; 'C'] in (match lst with | [] -> [[]] | h::t -> let left = combs t in let right = List.map (fun lst -> h::lst) left in left @ right ) in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let rec combs lst = (match lst with | [] -> [[]] | h::t -> let left = combs t in let right = List.map (fun lst -> h::lst) left in left @ right ) in (match ['B'; 'C'] with | [] -> [[]] | h::t -> let left = combs t in let right = List.map (fun lst -> h::lst) left in left @ right ) in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let rec combs lst = (match lst with | [] -> [[]] | h::t -> let left = combs t in let right = List.map (fun lst -> h::lst) left in left @ right ) in (match ['B'; 'C'] with | h::t -> let left = combs t in let right = List.map (fun lst -> h::lst) left in left @ right ) in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let rec combs lst = (match lst with | [] -> [[]] | h::t -> let left = combs t in let right = List.map (fun lst -> h::lst) left in left @ right ) in let t = ['C'] in let h = 'B' in let left = combs t in let right = List.map (fun lst -> h::lst) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let rec combs lst = (match lst with | [] -> [[]] | h::t -> let left = combs t in let right = List.map (fun lst -> h::lst) left in left @ right ) in let h = 'B' in let left = combs ['C'] in let right = List.map (fun lst -> h::lst) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'B' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let rec combs lst = (match lst with | [] -> [[]] | h::t -> let left = combs t in let right = List.map (fun lst -> h::lst) left in left @ right ) in let lst = ['C'] in (match lst with | [] -> [[]] | h::t -> let left = combs t in let right = List.map (fun lst -> h::lst) left in left @ right ) in let right = List.map (fun lst -> h::lst) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'B' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let rec combs lst = (match lst with | [] -> [[]] | h::t -> let left = combs t in let right = List.map (fun lst -> h::lst) left in left @ right ) in (match ['C'] with | [] -> [[]] | h::t -> let left = combs t in let right = List.map (fun lst -> h::lst) left in left @ right ) in let right = List.map (fun lst -> h::lst) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'B' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let rec combs lst = (match lst with | [] -> [[]] | h::t -> let left = combs t in let right = List.map (fun lst -> h::lst) left in left @ right ) in (match ['C'] with | h::t -> let left = combs t in let right = List.map (fun lst -> h::lst) left in left @ right ) in let right = List.map (fun lst -> h::lst) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'B' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let rec combs lst = (match lst with | [] -> [[]] | h::t -> let left = combs t in let right = List.map (fun lst -> h::lst) left in left @ right ) in let t = [] in let h = 'C' in let left = combs t in let right = List.map (fun lst -> h::lst) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'B' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let rec combs lst = (match lst with | [] -> [[]] | h::t -> let left = combs t in let right = List.map (fun lst -> h::lst) left in left @ right ) in let h = 'C' in let left = combs [] in let right = List.map (fun lst -> h::lst) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'B' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'C' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let rec combs lst = (match lst with | [] -> [[]] | h::t -> let left = combs t in let right = List.map (fun lst -> h::lst) left in left @ right ) in let lst = [] in (match lst with | [] -> [[]] | h::t -> let left = combs t in let right = List.map (fun lst -> h::lst) left in left @ right ) in let right = List.map (fun lst -> h::lst) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'B' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'C' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let rec combs lst = (match lst with | [] -> [[]] | h::t -> let left = combs t in let right = List.map (fun lst -> h::lst) left in left @ right ) in (match [] with | [] -> [[]] | h::t -> let left = combs t in let right = List.map (fun lst -> h::lst) left in left @ right ) in let right = List.map (fun lst -> h::lst) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'B' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'C' in let left = [[]] in let right = List.map (fun lst -> h::lst) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'B' in let left = let h = 'C' in let left = [[]] in let right = (let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in function | [] -> [] | a::l -> let r = f a in r::map f l ) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'B' in let left = let h = 'C' in let left = [[]] in let right = (let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in function | [] -> [] | a::l -> let f lst = h::lst in let r = f a in r::map f l ) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'B' in let left = let h = 'C' in let left = [[]] in let right = (function | [] -> [] | a::l -> let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f a in r::map f l ) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'B' in let left = let h = 'C' in let left = [[]] in let right = (function | [] -> [] | a::l -> let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f a in r::map f l ) [[]] in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'B' in let left = let h = 'C' in let left = [[]] in let right = (function | a::l -> let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f a in r::map f l ) [[]] in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'B' in let left = let h = 'C' in let left = [[]] in let right = let l = [] in let a = [] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f a in r::map f l in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'B' in let left = let h = 'C' in let left = [[]] in let right = let l = [] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f [] in r::map f l in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'B' in let left = let h = 'C' in let left = [[]] in let right = let l = [] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = let lst = [] in h::lst in r::map f l in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'B' in let left = let h = 'C' in let left = [[]] in let right = let l = [] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = let lst = [] in 'C'::lst in r::map f l in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'B' in let left = let h = 'C' in let left = [[]] in let right = let l = [] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = ['C'] in r::map f l in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'B' in let left = let h = 'C' in let left = [[]] in let right = let l = [] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in ['C']::map f l in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'B' in let left = let h = 'C' in let left = [[]] in let right = let l = [] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in ['C']::map (fun lst -> h::lst) l in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'B' in let left = let h = 'C' in let left = [[]] in let right = let l = [] in ['C']::(let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in function | [] -> [] | a::l -> let r = f a in r::map f l ) l in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'B' in let left = let h = 'C' in let left = [[]] in let right = let l = [] in ['C']::(let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in function | [] -> [] | a::l -> let f lst = h::lst in let r = f a in r::map f l ) l in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'B' in let left = let h = 'C' in let left = [[]] in let right = let l = [] in ['C']::(function | [] -> [] | a::l -> let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f a in r::map f l ) l in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'B' in let left = let h = 'C' in let left = [[]] in let right = ['C']::(function | [] -> [] | a::l -> let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f a in r::map f l ) [] in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'B' in let left = let left = [[]] in let right = [['C']] in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'B' in let left = let right = [['C']] in [[]] @ right in let right = List.map (fun lst -> h::lst) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'B' in let left = [[]] @ [['C']] in let right = List.map (fun lst -> h::lst) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'B' in let left = [[]; ['C']] in let right = List.map (fun lst -> h::lst) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let h = 'B' in let left = [[]; ['C']] in let right = (let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in function | [] -> [] | a::l -> let r = f a in r::map f l ) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let h = 'B' in let left = [[]; ['C']] in let right = (let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in function | [] -> [] | a::l -> let f lst = h::lst in let r = f a in r::map f l ) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let h = 'B' in let left = [[]; ['C']] in let right = (function | [] -> [] | a::l -> let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f a in r::map f l ) left in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let h = 'B' in let left = [[]; ['C']] in let right = (function | [] -> [] | a::l -> let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f a in r::map f l ) [[]; ['C']] in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let h = 'B' in let left = [[]; ['C']] in let right = (function | a::l -> let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f a in r::map f l ) [[]; ['C']] in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let h = 'B' in let left = [[]; ['C']] in let right = let l = [['C']] in let a = [] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f a in r::map f l in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let h = 'B' in let left = [[]; ['C']] in let right = let l = [['C']] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f [] in r::map f l in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let h = 'B' in let left = [[]; ['C']] in let right = let l = [['C']] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = let lst = [] in h::lst in r::map f l in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let h = 'B' in let left = [[]; ['C']] in let right = let l = [['C']] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = let lst = [] in 'B'::lst in r::map f l in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let h = 'B' in let left = [[]; ['C']] in let right = let l = [['C']] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = ['B'] in r::map f l in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let h = 'B' in let left = [[]; ['C']] in let right = let l = [['C']] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in ['B']::map f l in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let h = 'B' in let left = [[]; ['C']] in let right = let l = [['C']] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in ['B']::map (fun lst -> h::lst) l in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let h = 'B' in let left = [[]; ['C']] in let right = let l = [['C']] in ['B']::(let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in function | [] -> [] | a::l -> let r = f a in r::map f l ) l in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let h = 'B' in let left = [[]; ['C']] in let right = let l = [['C']] in ['B']::(let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in function | [] -> [] | a::l -> let f lst = h::lst in let r = f a in r::map f l ) l in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let h = 'B' in let left = [[]; ['C']] in let right = let l = [['C']] in ['B']::(function | [] -> [] | a::l -> let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f a in r::map f l ) l in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let h = 'B' in let left = [[]; ['C']] in let right = ['B']::(function | [] -> [] | a::l -> let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f a in r::map f l ) [['C']] in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let h = 'B' in let left = [[]; ['C']] in let right = ['B']::(function | a::l -> let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f a in r::map f l ) [['C']] in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let h = 'B' in let left = [[]; ['C']] in let right = ['B']::let l = [] in let a = ['C'] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f a in r::map f l in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let h = 'B' in let left = [[]; ['C']] in let right = ['B']::let l = [] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f ['C'] in r::map f l in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let h = 'B' in let left = [[]; ['C']] in let right = ['B']::let l = [] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = let lst = ['C'] in h::lst in r::map f l in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let h = 'B' in let left = [[]; ['C']] in let right = ['B']::let l = [] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = let lst = ['C'] in 'B'::lst in r::map f l in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let h = 'B' in let left = [[]; ['C']] in let right = ['B']::let l = [] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = ['B'; 'C'] in r::map f l in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let h = 'B' in let left = [[]; ['C']] in let right = ['B']::let l = [] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in ['B'; 'C']::map f l in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let h = 'B' in let left = [[]; ['C']] in let right = ['B']::let l = [] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in ['B'; 'C']::map (fun lst -> h::lst) l in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let h = 'B' in let left = [[]; ['C']] in let right = ['B']::let l = [] in ['B'; 'C']::(let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in function | [] -> [] | a::l -> let r = f a in r::map f l ) l in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let h = 'B' in let left = [[]; ['C']] in let right = ['B']::let l = [] in ['B'; 'C']::(let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in function | [] -> [] | a::l -> let f lst = h::lst in let r = f a in r::map f l ) l in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let h = 'B' in let left = [[]; ['C']] in let right = ['B']::let l = [] in ['B'; 'C']::(function | [] -> [] | a::l -> let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f a in r::map f l ) l in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let h = 'B' in let left = [[]; ['C']] in let right = ['B']::['B'; 'C']::(function | [] -> [] | a::l -> let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f a in r::map f l ) [] in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let left = [[]; ['C']] in let right = [['B']; ['B'; 'C']] in left @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = let right = [['B']; ['B'; 'C']] in [[]; ['C']] @ right in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = [[]; ['C']] @ [['B']; ['B'; 'C']] in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let rec List.map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = List.map (fun lst -> h::lst) left in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = (let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in function | [] -> [] | a::l -> let r = f a in r::map f l ) left in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = (let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in function | [] -> [] | a::l -> let f lst = h::lst in let r = f a in r::map f l ) left in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = (function | [] -> [] | a::l -> let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f a in r::map f l ) left in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = (function | [] -> [] | a::l -> let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f a in r::map f l ) [[]; ['C']; ['B']; ['B'; 'C']] in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = (function | a::l -> let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f a in r::map f l ) [[]; ['C']; ['B']; ['B'; 'C']] in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = let l = [['C']; ['B']; ['B'; 'C']] in let a = [] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f a in r::map f l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = let l = [['C']; ['B']; ['B'; 'C']] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f [] in r::map f l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = let l = [['C']; ['B']; ['B'; 'C']] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = let lst = [] in h::lst in r::map f l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = let l = [['C']; ['B']; ['B'; 'C']] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = let lst = [] in 'A'::lst in r::map f l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = let l = [['C']; ['B']; ['B'; 'C']] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = ['A'] in r::map f l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = let l = [['C']; ['B']; ['B'; 'C']] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in ['A']::map f l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = let l = [['C']; ['B']; ['B'; 'C']] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in ['A']::map (fun lst -> h::lst) l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = let l = [['C']; ['B']; ['B'; 'C']] in ['A']::(let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in function | [] -> [] | a::l -> let r = f a in r::map f l ) l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = let l = [['C']; ['B']; ['B'; 'C']] in ['A']::(let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in function | [] -> [] | a::l -> let f lst = h::lst in let r = f a in r::map f l ) l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = let l = [['C']; ['B']; ['B'; 'C']] in ['A']::(function | [] -> [] | a::l -> let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f a in r::map f l ) l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = ['A']::(function | [] -> [] | a::l -> let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f a in r::map f l ) [['C']; ['B']; ['B'; 'C']] in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = ['A']::(function | a::l -> let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f a in r::map f l ) [['C']; ['B']; ['B'; 'C']] in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = ['A']::let l = [['B']; ['B'; 'C']] in let a = ['C'] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f a in r::map f l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = ['A']::let l = [['B']; ['B'; 'C']] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f ['C'] in r::map f l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = ['A']::let l = [['B']; ['B'; 'C']] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = let lst = ['C'] in h::lst in r::map f l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = ['A']::let l = [['B']; ['B'; 'C']] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = let lst = ['C'] in 'A'::lst in r::map f l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = ['A']::let l = [['B']; ['B'; 'C']] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = ['A'; 'C'] in r::map f l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = ['A']::let l = [['B']; ['B'; 'C']] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in ['A'; 'C']::map f l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = ['A']::let l = [['B']; ['B'; 'C']] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in ['A'; 'C']::map (fun lst -> h::lst) l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = ['A']::let l = [['B']; ['B'; 'C']] in ['A'; 'C']::(let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in function | [] -> [] | a::l -> let r = f a in r::map f l ) l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = ['A']::let l = [['B']; ['B'; 'C']] in ['A'; 'C']::(let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in function | [] -> [] | a::l -> let f lst = h::lst in let r = f a in r::map f l ) l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = ['A']::let l = [['B']; ['B'; 'C']] in ['A'; 'C']::(function | [] -> [] | a::l -> let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f a in r::map f l ) l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = ['A']::['A'; 'C']::(function | [] -> [] | a::l -> let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f a in r::map f l ) [['B']; ['B'; 'C']] in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = ['A']::['A'; 'C']::(function | a::l -> let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f a in r::map f l ) [['B']; ['B'; 'C']] in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = ['A']::['A'; 'C']::let l = [['B'; 'C']] in let a = ['B'] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f a in r::map f l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = ['A']::['A'; 'C']::let l = [['B'; 'C']] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f ['B'] in r::map f l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = ['A']::['A'; 'C']::let l = [['B'; 'C']] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = let lst = ['B'] in h::lst in r::map f l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = ['A']::['A'; 'C']::let l = [['B'; 'C']] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = let lst = ['B'] in 'A'::lst in r::map f l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = ['A']::['A'; 'C']::let l = [['B'; 'C']] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = ['A'; 'B'] in r::map f l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = ['A']::['A'; 'C']::let l = [['B'; 'C']] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in ['A'; 'B']::map f l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = ['A']::['A'; 'C']::let l = [['B'; 'C']] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in ['A'; 'B']::map (fun lst -> h::lst) l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = ['A']::['A'; 'C']::let l = [['B'; 'C']] in ['A'; 'B']::(let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in function | [] -> [] | a::l -> let r = f a in r::map f l ) l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = ['A']::['A'; 'C']::let l = [['B'; 'C']] in ['A'; 'B']::(let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in function | [] -> [] | a::l -> let f lst = h::lst in let r = f a in r::map f l ) l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = ['A']::['A'; 'C']::let l = [['B'; 'C']] in ['A'; 'B']::(function | [] -> [] | a::l -> let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f a in r::map f l ) l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = ['A']::['A'; 'C']::['A'; 'B']::(function | [] -> [] | a::l -> let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f a in r::map f l ) [['B'; 'C']] in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = ['A']::['A'; 'C']::['A'; 'B']::(function | a::l -> let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f a in r::map f l ) [['B'; 'C']] in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = ['A']::['A'; 'C']::['A'; 'B']::let l = [] in let a = ['B'; 'C'] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f a in r::map f l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = ['A']::['A'; 'C']::['A'; 'B']::let l = [] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f ['B'; 'C'] in r::map f l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = ['A']::['A'; 'C']::['A'; 'B']::let l = [] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = let lst = ['B'; 'C'] in h::lst in r::map f l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = ['A']::['A'; 'C']::['A'; 'B']::let l = [] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = let lst = ['B'; 'C'] in 'A'::lst in r::map f l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = ['A']::['A'; 'C']::['A'; 'B']::let l = [] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = ['A'; 'B'; 'C'] in r::map f l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = ['A']::['A'; 'C']::['A'; 'B']::let l = [] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in ['A'; 'B'; 'C']::map f l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = ['A']::['A'; 'C']::['A'; 'B']::let l = [] in let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in ['A'; 'B'; 'C']::map (fun lst -> h::lst) l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = ['A']::['A'; 'C']::['A'; 'B']::let l = [] in ['A'; 'B'; 'C']::(let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in function | [] -> [] | a::l -> let r = f a in r::map f l ) l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = ['A']::['A'; 'C']::['A'; 'B']::let l = [] in ['A'; 'B'; 'C']::(let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in function | [] -> [] | a::l -> let f lst = h::lst in let r = f a in r::map f l ) l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = ['A']::['A'; 'C']::['A'; 'B']::let l = [] in ['A'; 'B'; 'C']::(function | [] -> [] | a::l -> let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f a in r::map f l ) l in left @ right
=>  let h = 'A' in let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = ['A']::['A'; 'C']::['A'; 'B']::['A'; 'B'; 'C']::(function | [] -> [] | a::l -> let rec map f = function | [] -> [] | a::l -> let r = f a in r::map f l  in let f lst = h::lst in let r = f a in r::map f l ) [] in left @ right
=>  let left = [[]; ['C']; ['B']; ['B'; 'C']] in let right = [['A']; ['A'; 'C']; ['A'; 'B']; ['A'; 'B'; 'C']] in left @ right
=>  let right = [['A']; ['A'; 'C']; ['A'; 'B']; ['A'; 'B'; 'C']] in [[]; ['C']; ['B']; ['B'; 'C']] @ right
=>  [[]; ['C']; ['B']; ['B'; 'C']] @ [['A']; ['A'; 'C']; ['A'; 'B']; ['A'; 'B'; 'C']]
=>  [[]; ['C']; ['B']; ['B'; 'C']; ['A']; ['A'; 'C']; ['A'; 'B']; ['A'; 'B'; 'C']]

Prior to posting, I had tried to use similar tools, such as those 2 from the Python world:

I had thought maybe visualizing the stack would help (it didn’t).

To use those tools, I would have to rewrite my functions in Python and so that’s what I did, something like this:

def rev(lst):
    def aux(acc, lst):
        if lst is None:
            return acc
        else:
            (x, xs) = lst
            return aux((x, acc), xs)
    return aux(None, lst)


def append(a, b):
    """
    >>> append((1, (2, (3, None))), (4, (5, (6, None))))
    (1, (2, (3, (4, (5, (6, None))))))

    >>> append((1, (2, (3, None))), None)
    (1, (2, (3, None)))

    >>> append(None, (1, (2, (3, None))))
    (1, (2, (3, None)))

    >>> append((0, None), (1, (2, (3, None))))
    (0, (1, (2, (3, None))))
    """
    def aux(acc, a, b):
        if a is None:
            if b is None:
                return rev(acc)
            else:
                return aux(acc, b, None)
        else:
            (x, xs) = a
            return aux((x, acc), xs, b)
    return aux(None, a, b)


def map(f, lst):
    """
    >>> map(lambda n: n*2, (1, (2, (3, None))))
    (2, (4, (6, None)))
    """
    if lst is None:
        return None
    else:
        (x, xs) = lst
        return (f(x), map(f, xs))


def sub_sets(lst):
    """
    >>> sub_sets(None)
    (None, None)

    >>> sub_sets(('a', ('b', ('c', None))))
    (None, (('c', None), (('b', None), (('b', ('c', None)), (('a', None), (('a', ('c', None)), (('a', ('b', None)), (('a', ('b', ('c', None))), None))))))))
    """
    if lst is None:
        return (None, None)
    else:
        (x, xs) = lst
        left = sub_sets(xs)
        right = map(lambda t: (x, t), left)
        return append(left, right)


sub_sets(('a', ('b', ('c', None))))

I used tuples to implement linked lists, kinda lisp style. That’s because I wanted to visualize the execution in a similar way to what I would expect from OCaml.

However, the output was quite massive there too so that’s when I thought I should ask for advice.

You can copy/paste these Python functions to see the execution. It’s pretty cool, however probably more useful for simpler examples

7

You do know about the REPL’s (utop’s) #trace?
It’s also quite noisy and doesn’t show polymorphic arguments, but it’s usable.

# let rec extract (k: int) (list: int list) =
    if k <= 0 then [[]]
    else match list with
         | [] -> []
         | h :: tl ->
            let with_h = List.map (fun l -> h :: l) (extract (k - 1) tl) in
            let without_h = extract k tl in
            with_h @ without_h;;
val extract : int -> int list -> int list list = <fun>

# #trace extract;;
extract is now traced.

# extract 4 [1;2;3;4;5];;
extract <-- 4
extract --> <fun>
extract* <-- [1; 2; 3; 4; 5]
extract <-- 3
extract --> <fun>
extract* <-- [2; 3; 4; 5]
extract <-- 2
extract --> <fun>
...
extract* --> [[2; 3; 4; 5]]
extract* -->
  [[1; 2; 3; 4]; [1; 2; 3; 5]; [1; 2; 4; 5]; [1; 3; 4; 5]; [2; 3; 4; 5]]
- : int list list =
[[1; 2; 3; 4]; [1; 2; 3; 5]; [1; 2; 4; 5]; [1; 3; 4; 5]; [2; 3; 4; 5]]
2 Likes
8

Yes I did know about it, but I never found it that useful before today actually.

I knew that I could temporarily make the arguments less generic to get better output. But I failed to realize that I should probably rewrite some of my functions to also get better output.

Here for example, I introduce tupled arguments to remove the currying that makes the output unecessarily noisy. I also introduce some ad hoc types for clarity.

type prepend_args = { elem : char; coll : char list list }

let prepend { elem; coll } : char list list = List.map (List.cons elem) coll

type append_args = { left : char list list; right : char list list }

let append { left; right } = left @ right

let rec sub_sets (lst : char list) =
  match lst with
  | [] -> [ [] ]
  | h :: t ->
      let left = sub_sets t in
      let right = prepend { elem = h; coll = left } in
      append { left; right }
;;

#trace sub_sets
#trace prepend
#trace append;;

sub_sets [ 'A'; 'B'; 'C' ]

If I pipe the output into a generic colorizer, I get this output:

image
image1253×625 59.8 KB

Quite satisfying!

What I wish I’d have though, is the ability to see the depth of the recursion, it’d look something like this

image
image1299×509 60.6 KB

I can probably hack something together for myself but I’d be interested to know if something similar already exists.

9

Shameless plug: you could try ppx_minidebug (it’s in the opam repository now).

10

Interesting tool!

For reference, given this file:

module Debug_runtime = Minidebug_runtime.PrintBox (struct
  let debug_ch = stdout
  let time_tagged = false
end)

let%debug_show rec sub_sets (input : char list) : char list list =
  match input with
  | [] -> [ [] ]
  | h :: t ->
      let left : char list list = sub_sets t in
      let right : char list list = List.map (List.cons h) left in
      left @ right
;;

let () =
  let _ = sub_sets [ 'A'; 'B'; 'C' ] in
  print_endline "Done!"
;;

I get the following output:

BEGIN DEBUG SESSION
"bin/wip2.ml":6:28-12:18: sub_sets
├─input = ['A'; 'B'; 'C']
├─"bin/wip2.ml":10:10: 
│ ├─"bin/wip2.ml":6:28-12:18: sub_sets
│ │ ├─input = ['B'; 'C']
│ │ ├─"bin/wip2.ml":10:10: 
│ │ │ ├─"bin/wip2.ml":6:28-12:18: sub_sets
│ │ │ │ ├─input = ['C']
│ │ │ │ ├─"bin/wip2.ml":10:10: 
│ │ │ │ │ ├─"bin/wip2.ml":6:28-12:18: sub_sets
│ │ │ │ │ │ ├─input = []
│ │ │ │ │ │ └─sub_sets = [[]]
│ │ │ │ │ └─left = [[]]
│ │ │ │ ├─"bin/wip2.ml":11:10: 
│ │ │ │ │ └─right = [['C']]
│ │ │ │ └─sub_sets = [[]; ['C']]
│ │ │ └─left = [[]; ['C']]
│ │ ├─"bin/wip2.ml":11:10: 
│ │ │ └─right = [['B']; ['B'; 'C']]
│ │ └─sub_sets = [[]; ['C']; ['B']; ['B'; 'C']]
│ └─left = [[]; ['C']; ['B']; ['B'; 'C']]
├─"bin/wip2.ml":11:10: 
│ └─right = [['A']; ['A'; 'C']; ['A'; 'B']; ['A'; 'B'; 'C']]
└─sub_sets = [[]; ['C']; ['B']; ['B'; 'C']; ['A']; ['A'; 'C']; ['A'; 'B']; ['A'; 'B'; 'C']
    ]
Done!

I feel the traditional trace tool’s output is a bit easier to analyze in this case because it’s sequential. But it’s nice to have another way to visualize the execution tree thanks :+1:

1 Like
11

Do you mean you’d prefer to hide the headers of function calls? Manually deleting the “noise” lines:

BEGIN DEBUG SESSION
├─input = ['A'; 'B'; 'C']
│ │ ├─input = ['B'; 'C']
│ │ │ │ ├─input = ['C']
│ │ │ │ │ │ ├─input = []
│ │ │ │ │ │ └─sub_sets = [[]]
│ │ │ │ │ └─left = [[]]
│ │ │ │ │ └─right = [['C']]
│ │ │ │ └─sub_sets = [[]; ['C']]
│ │ │ └─left = [[]; ['C']]
│ │ │ └─right = [['B']; ['B'; 'C']]
│ │ └─sub_sets = [[]; ['C']; ['B']; ['B'; 'C']]
│ └─left = [[]; ['C']; ['B']; ['B'; 'C']]
│ └─right = [['A']; ['A'; 'C']; ['A'; 'B']; ['A'; 'B'; 'C']]
└─sub_sets = [[]; ['C']; ['B']; ['B'; 'C']; ['A']; ['A'; 'C']; ['A'; 'B']; ['A'; 'B'; 'C'] ]

Then, it’s clear that there’s some duplication, so maybe:

BEGIN DEBUG SESSION
├─input = ['A'; 'B'; 'C']
│ │ ├─input = ['B'; 'C']
│ │ │ │ ├─input = ['C']
│ │ │ │ │ │ ├─input = []
│ │ │ │ │ ├─┴left = sub_sets = [[]]
│ │ │ │ │ ├─right = [['C']]
│ │ │ ├─┴left = sub_sets = [[]; ['C']]
│ │ │ ├─right = [['B']; ['B'; 'C']]
│ ├─┴left = sub_sets = [[]; ['C']; ['B']; ['B'; 'C']]
│ ├─right = [['A']; ['A'; 'C']; ['A'; 'B']; ['A'; 'B'; 'C']]
└─┴sub_sets = [[]; ['C']; ['B']; ['B'; 'C']; ['A']; ['A'; 'C']; ['A'; 'B']; ['A'; 'B'; 'C'] ]

(This requires extending the functionality of PrintBox though.)
I’ll do another release (there’s a broken link in the documentation landing page), I could try to figure out such setting.

12

No, I meant that reading the tracing output top-down matches pretty well reading the last level of the tree left to right (which is the output we want in my Graphiz example).

With the minidebug output, we have to read the output “inside out” to make sens of the final output, which feels a little harder to track.

But I like your idea to make the header optional :slight_smile:

13

I don’t quite get what you meant, and probably it’s not it, but ppx_minidebug 1.0 has a setting values_first_mode, which brings the result of a computation to the header of the computation (or just below the header in a <returns> subtree if it’s multi-line).

P.S. ppx_minidebug 1.0 is in opam repo since today.

14

Thanks for the heads up!

I like this latest change. With values_first_mode set to true, we can now easily see that left(blue) + right(red) = sub_sets(purple)

image
image1092×668 60.7 KB

:+1:

1 Like