The goal of this lecture note is to play some more with lists.
Dana: Funny how these map functions enumerate all the elements of a given list.
Alfrothul: Well, yes. Then they apply the function they are also given to each of these elements and they collect the results in a list.
Dana: Right. And if we were nesting two calls to a map function...
Alfrothul: ...we would nest the enumeration, yes:
let nested_enumeration_2 v1s v2s =
List.map
(fun v1 ->
List.map
(fun v2 ->
...)
v2s)
v1s;;
Dana: Yup. Likewise if we nest three calls to the map function:
let nested_enumeration_3 v1s v2s v3s =
List.map
(fun v1 ->
List.map
(fun v2 ->
List.map
(fun v3 ->
...)
v3s)
v2s)
v1s;;
Anton: Hum. I see the principle, but how about some practice. Instead of ..., let’s group the enumerated elements into a tuple:
let nested_enumeration_2 v1s v2s =
List.map
(fun v1 ->
List.map
(fun v2 ->
(v1, v2))
v2s)
v1s;;
let nested_enumeration_3 v1s v2s v3s =
List.map
(fun v1 ->
List.map
(fun v2 ->
List.map
(fun v3 ->
(v1, v2, v3))
v3s)
v2s)
v1s;;
Alfrothul: The types reflect the nestings, look:
Anton: Yes they do. And the result is indeed an enumeration:
# nested_enumeration_2 [1; 2; 3] [10; 20];;
- : (int * int) list list =
[[(1, 10); (1, 20)]; [(2, 10); (2, 20)]; [(3, 10); (3, 20)]]
# nested_enumeration_3 [1; 2] [10; 20] [100; 200];;
- : (int * int * int) list list list =
[[[(1, 10, 100); (1, 10, 200)]; [(1, 20, 100); (1, 20, 200)]];
[[(2, 10, 100); (2, 10, 200)]; [(2, 20, 100); (2, 20, 200)]]]
#
Muggsy: That’s the same dame. I can tell by the way...
Dana: To just obtain one list rather than a nested list of lists, how about we adjust the map function to append instead of cons the results of applying the function to map?
Alfrothul: That simple, eh:
let list_appendmap f vs =
(* list_appendmap : ('a -> 'b list) -> 'a list -> 'b list *)
let rec visit vs =
match vs with
| [] ->
[]
| v :: vs' ->
f v @ visit vs'
in visit vs;;
Dana: Looks like. But then the function to map must return a list.
Anton: I think I can arrange that:
let nested_enumeration_2 v1s v2s =
list_appendmap
(fun v1 ->
list_appendmap
(fun v2 ->
[(v1, v2)])
v2s)
v1s;;
let nested_enumeration_3 v1s v2s v3s =
list_appendmap
(fun v1 ->
list_appendmap
(fun v2 ->
list_appendmap
(fun v3 ->
[(v1, v2, v3)])
v3s)
v2s)
v1s;;
Alfrothul: And the types reflect the flattening of the resulting lists, look:
Anton: Neat. And the result is still an enumeration, but now in a flat list:
# nested_enumeration_2 [1; 2; 3] [10; 20];;
- : (int * int) list = [(1, 10); (1, 20); (2, 10); (2, 20); (3, 10); (3, 20)]
# nested_enumeration_3 [1; 2] [10; 20] [100; 200];;
- : (int * int * int) list =
[(1, 10, 100); (1, 10, 200); (1, 20, 100); (1, 20, 200); (2, 10, 100); (2, 10, 200); (2, 20, 100); (2, 20, 200)]
#
Muggsy: Positively the same dame!
Dana: And instead of listing all the tuples, we could just list tuples that satisfy a certain property.
Anton: Beg pardon?
Dana: Take Pythagorean triples, for example.
Anton: What’s that now?
Alfrothul: Three integers a, b, and c form a Pythagorean triple whenever a^2 + b^2 = c^2.
Anton: Ah, that. Thanks.
Dana: So there we go:
let square n =
n * n;;
let pythagorean_triples n1s n2s n3s =
list_appendmap
(fun n1 ->
list_appendmap
(fun n2 ->
list_appendmap
(fun n3 ->
if square n1 + square n2 = square n3
then [(n1, n2, n3)]
else [])
n3s)
n2s)
n1s;;
Alfrothul: Ah, clever—if the three enumerated numbers do not form a Pythagorean triple, the result is the empty list.
Dana: ...which is neutral for list concatenation, yes:
# let ns = List.init 10 (fun i -> i) in pythagorean_triples ns ns ns;;
- : (int * int * int) list =
[(0, 0, 0); (0, 1, 1); (0, 2, 2); (0, 3, 3); (0, 4, 4); (0, 5, 5); (0, 6, 6);
(0, 7, 7); (0, 8, 8); (0, 9, 9); (1, 0, 1); (2, 0, 2); (3, 0, 3); (3, 4, 5);
(4, 0, 4); (4, 3, 5); (5, 0, 5); (6, 0, 6); (7, 0, 7); (8, 0, 8); (9, 0, 9)]
#
Dana: Wait, that’s a lot of zeroes:
# let ns = List.init 10 succ in pythagorean_triples ns ns ns;;
- : (int * int * int) list = [(3, 4, 5); (4, 3, 5); (6, 8, 10); (8, 6, 10)]
#
Alfrothul: Awesome, Dana.
Dana: Thanks. We might as well generalize, though:
let enumerate_3 f v1s v2s v3s =
list_appendmap
(fun v1 ->
list_appendmap
(fun v2 ->
list_appendmap
(fun v3 ->
f v1 v2 v3)
v3s)
v2s)
v1s;;
Alfrothul: Even better indeed:
let pythagorean_triples n1s n2s n3s =
enumerate_3
(fun n1 n2 n3 ->
if square n1 + square n2 = square n3
then [(n1, n2, n3)]
else [])
n1s
n2s
n3s;;
Pablito: And it works too:
# let ns = List.init 50 succ in pythagorean_triples ns ns ns;;
- : (int * int * int) list =
[(3, 4, 5); (4, 3, 5); (5, 12, 13); (6, 8, 10); (7, 24, 25); (8, 6, 10);
(8, 15, 17); (9, 12, 15); (9, 40, 41); (10, 24, 26); (12, 5, 13);
(12, 9, 15); (12, 16, 20); (12, 35, 37); (14, 48, 50); (15, 8, 17);
(15, 20, 25); (15, 36, 39); (16, 12, 20); (16, 30, 34); (18, 24, 30);
(20, 15, 25); (20, 21, 29); (21, 20, 29); (21, 28, 35); (24, 7, 25);
(24, 10, 26); (24, 18, 30); (24, 32, 40); (27, 36, 45); (28, 21, 35);
(30, 16, 34); (30, 40, 50); (32, 24, 40); (35, 12, 37); (36, 15, 39);
(36, 27, 45); (40, 9, 41); (40, 30, 50); (48, 14, 50)]
#
Anton: Let me check something:
# list_andmap (fun (a, b, c) -> square a + square b = square c) (let ns = List.init 100 succ in pythagorean_triples ns ns ns);;
- : bool = true
#
Mimer: Checking the soundness of pythagorean_triples, Anton?
Anton: Harrumph.
The goal of this exercise is to implement an OCaml function that, given a list, constructs a list of its sublists such that in the resulting list, each sublist at index i contains all the elements of the given list except the one at index i.
This OCaml function should pass the following unit tests:
let test_list_project_int candidate =
let b3 = (candidate [3; 2; 1] = [[2; 1]; [3; 1]; [3; 2]])
and b4 = (candidate [4; 3; 2; 1] = [[3; 2; 1]; [4; 2; 1]; [4; 3; 1]; [4; 3; 2]])
in b3 && b4;;
The goal of this exercise is to implement an OCaml function that, given a value and a list of values (of length n), constructs a list of n lists where in each sublist is like the given list except that the given value now occurs at index 0, 1, ..., n-1.
This OCaml function should pass the following unit tests:
let test_list_inject_int candidate =
let b0 = (candidate 1 [] =
[[1]])
and b1 = (candidate 2 [1] =
[[2; 1]; [1; 2]])
and b2 = (candidate 3 [2; 1] =
[[3; 2; 1]; [2; 3; 1]; [2; 1; 3]])
and b3 = (candidate 4 [3; 2; 1] =
[[4; 3; 2; 1]; [3; 4; 2; 1]; [3; 2; 4; 1]; [3; 2; 1; 4]])
and b4 = (candidate 5 [4; 3; 2; 1] =
[[5; 4; 3; 2; 1]; [4; 5; 3; 2; 1]; [4; 3; 5; 2; 1]; [4; 3; 2; 5; 1]; [4; 3; 2; 1; 5]])
in b0 && b1 && b2 && b3 && b4;;
Hint: this unit-test function was not written randomly.
The goal of this exercise is to implement an OCaml function that, given a list, constructs a list of lists where each of these lists is a distinct permutation of the given list.
This OCaml function should pass the following unit tests:
let test_list_permutations_int candidate =
let b0 = (candidate [] =
[[]])
and b1 = (candidate [1] =
[[1]])
and b2 = (candidate [2; 1] =
[[2; 1];
[1; 2]])
and b3 = (candidate [3; 2; 1] =
[[3; 2; 1]; [2; 3; 1]; [2; 1; 3];
[3; 1; 2]; [1; 3; 2]; [1; 2; 3]])
and b4 = (candidate [4; 3; 2; 1] =
[[4; 3; 2; 1]; [3; 4; 2; 1]; [3; 2; 4; 1]; [3; 2; 1; 4];
[4; 2; 3; 1]; [2; 4; 3; 1]; [2; 3; 4; 1]; [2; 3; 1; 4];
[4; 2; 1; 3]; [2; 4; 1; 3]; [2; 1; 4; 3]; [2; 1; 3; 4];
[4; 3; 1; 2]; [3; 4; 1; 2]; [3; 1; 4; 2]; [3; 1; 2; 4];
[4; 1; 3; 2]; [1; 4; 3; 2]; [1; 3; 4; 2]; [1; 3; 2; 4];
[4; 1; 2; 3]; [1; 4; 2; 3]; [1; 2; 4; 3]; [1; 2; 3; 4]])
in b0 && b1 && b2 && b3 && b4;;
Hint: this unit-test function was not written randomly.
Observation: as implicitly specified in test_permutations, the result of the candidate function should be a palindrome of sorts:
let test_two_level_list_palindromep_int candidate =
let ns = List.init (Random.int 10) (fun _ -> random_int 1000)
in let ps = candidate ns
in List.rev (List.map List.rev ps) = ps;;
Created [06 Oct 2022]