The puzzle of the week, for beginners

Learning
,
1

Hello, Dear List,

I would like to propose a small list puzzle with nested List.fold_left, and cartesian-product, for beginners who would like to practice functional programming.

The task is to make a filter of 2 input lists, based on iterating their elements as a cartesian-product.

Functions to create cartesian-products from 2 input lists can be found in containers, and look like this:

let chars = ['A'; 'B'; 'C']
let nums = [1; 2; 3; 4]

let cp =
  List.fold_left (fun acc c ->
    List.fold_left (fun acc n ->
      (c, n) :: acc
    ) acc nums
  ) [] chars

the value cp will look like:

[ ('A', 1); ('A', 2); ('A', 3); ('A', 4);
  ('B', 1); ('B', 2); ('B', 3); ('B', 4);
  ('C', 1); ('C', 2); ('C', 3); ('C', 4); ]

The puzzle is now to create filter and map functions, with interface:

val cart_prod_map :
  ('a -> 'b -> 'a * 'b) -> 'a list -> 'b list -> 'a list * 'b list

val cart_prod_filter :
  ('a -> 'b -> bool * bool) -> 'a list -> 'b list -> 'a list * 'b list

So that we get the result:

let chars = ['A'; 'B'; 'C']
let nums = [1; 2; 3; 4]

let cs1, ns1 =
  cart_prod_map (fun c n ->
    if (c, n) = ('A', 3)
    then ('a', 30)
    else (c, n)
  ) chars nums

returns:

val cs1 : char list = ['a'; 'B'; 'C']
val ns1 : int list = [1; 2; 30; 4]

and:

let cs2, ns2 =
  cart_prod_filter (fun c n ->
    if (c, n) = ('A', 3)
    then (false, false)
    else (true, true)
  ) chars nums

returns:

val cs2 : char list = ['B'; 'C']
val ns2 : int list = [1; 2; 4]

Solution: cart_prod.ml / cart_prod.mli

2 Likes