Graph Walks

We can think of a function g of type 'a -> 'a -> bool as a graph in which there is an edge between i and j exactly when g i j is true.

A function p of type 'a -> 'a generates a list of values by repeated application from a given starting point. We will call this a potential path and we will call p a path generator. For example, the list [x; p x; p (p x)] is a potential path of length 2 starting at x.

A potential path is valid for a given graph g if every pair of adjacent elements forms an edge in g. Continuing the above example, the potential path [x; p x; p (p x)] is valid for g if g x (p x) && g (p x) (p (p x)) is true.

Implement the function

val walks : ('a -> 'a -> bool) -> int -> (('a -> 'a) * 'a) list -> 'a list

so that walks g len paths_starts is the list of endpoints of all valid paths which have length len generated by each path generator on its associated starting point. The order of endpoints in the output should be consistent with the order of the starting points, even if some potential paths are dropped because they are not valid in g. The behavior of the function is undefined if len is negative.

You should use the functions List.map and List.filter. It may also be useful to try to use the pipelining operator |>.

let g1 (i : int) (j : int) = i < j && i <= 10 && j <= 10
let g2 (i : int) (j : int) = i <= 10 && j <= 10

let p1 i = i + 1
let p2 i = i - 1
let p3 i = i + 2

let _ = assert (walks g1 0 [(p1, 0); (p2, 0); (p3, 0)] = [0;0;0])
let _ = assert (walks g1 1 [(p1, 0); (p2, 0); (p3, 0)] = [1;2])
let _ = assert (walks g1 3 [(p1, 0); (p2, 0); (p3, 0)] = [3;6])
let _ = assert (walks g1 6 [(p1, 0); (p2, 0); (p3, 0)] = [6])
let _ = assert (walks g2 2 [(p1, 3); (p2, 5); (p3, 3)] = [5; 3; 7])
let _ = assert (walks g2 4 [(p1, -10); (p2, -20); (p3, 8)] = [-6; -24])
let _ = assert (walks g2 6 [(p1, 5); (p2, 11); (p3, -10)] = [2])