## Exercises

### Resolution of Linear Systems

This exercise revisits the resolution of linear systems presented as an exercise in the chapter on imperative programming (3).
1. By using the Printf module, write a function print_system that aligns the columns of the system.
```# type` `vect` ``=`` `float` `array` `` `type` `mat` ``=`` `vect` `array` `` `type` `syst` ``=`` `{` `m`:`mat` `;` `v`:`vect` `}` `;;`type vect = float array``type mat = vect array``type syst = { m: mat; v: vect }`# let` `affiche_systeme` `s` ``=`` `` `` `let` `w` ``=`` `Array.length` `s`.`m`.`(`0`)` `` `` `` `and` `h` ``=`` `Array.length` `s`.`m` `in` `` `` `` `let` `` `c` ``=`` `h` ``/`` ``2`` `in` `` `` `` `` `` `for` `i` ``=`` ``0`` `to` `h` ``-`` ``1`` `do` `` `` `` `` `` `` `` `Printf.printf` ``"| "`;` `` `` `` `` `` `` `for` `j` ``=`` ``0`` `to` `w` ``-`` ``1`` `do` `` `` `` `` `` `` `` `` `` `Printf.printf` ``" %8.2f "`` `s`.`m`.`(i)`.`(j)` `` `` `` `` `` `` `done;` `` `` `` `` `` `` `Printf.printf` ``" |"`;` `` `` `` `` `` `` `if` `i` ``=`` `c` `then` `Printf.printf` ``" * "`` `else` `Printf.printf` ``"   "`;` `` `` `` `` `` `` `Printf.printf` ``"| x_%-2d |"`` `i;` `` `` `` `` `` `` `if` `i` ``=`` `c` `then` `Printf.printf` ``" = "`` `else` `Printf.printf` ``"   "`;` `` `` `` `` `` `` `Printf.printf` ``"| %8.2f |\n"`` `s`.`v`.`(i)` `` `` `done;` `` `` `Printf.printf` ``"\n"`` `;;`val affiche_systeme : syst -> unit = <fun>`

```

2. Test this function on the examples given on page ??.
```# let` `ax3` ``=`` `{` `m` ``=`` ``[|`` ``[|`` ``1``0``.``0`` `` `;` `` ``7``.``0`` `` `;` `` ``8``.``1`` `` `;` `` ``7``.``2`` `` ``|]`` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `;` ``[|`` `` ``7``.``0``8`` `;` `` ``5``.``0``4`` `;` `` ``6``.``0`` `` `;` `` ``5``.``0`` `` ``|]`` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `;` ``[|`` `` ``8``.``0`` `` `;` `` ``5``.``9``8`` `;` `` ``9``.``8``9`` `;` `` ``9``.``0`` `` ``|]`` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `;` ``[|`` `` ``6``.``9``9`` `;` `` ``4``.``9``9`` `;` `` ``9``.``0`` `` `;` `` ``9``.``9``8`` ``|]`` ``|]`` `;` `` `` `` `` `` `` `` `` `` `` `` `` `v` ``=`` `` `` `` ``[|`` ``3``2``.``0`` `` `;` ``2``3``.``0`` `` `;` ``3``3``.``0`` `;` ``3``1``.``0`` ``|]`` `` `` `}` `;;`val ax3 : syst =``  {m=``    [|[|10; 7; 8.1; 7.2|]; [|7.08; 5.04; 6; 5|]; [|8; 5.98; 9.89; ...|];``      ...|];``   v=...}`# affiche_systeme` `ax3` `;;`|     10.00      7.00      8.10      7.20  |   | x_0  |   |    32.00 |``|      7.08      5.04      6.00      5.00  |   | x_1  |   |    23.00 |``|      8.00      5.98      9.89      9.00  | * | x_2  | = |    33.00 |``|      6.99      4.99      9.00      9.98  |   | x_3  |   |    31.00 |``- : unit = ()`

```

### Search for Prime Numbers

The Sieve of Eratosthenes is an easily programmed algorithm that searches for prime numbers in a range of integers, given that the lower limit is a prime number. The method is:
1. Enumerate, in a list, all the values on the range.
2. Remove from the list all the values that are multiples of the first element.
3. Remove this first element from the list, and keep it as a prime.
4. Restart at step 2 as long as the list is not empty.
Here are the steps to create a program that implements this algorithm:
1. Write a function range that builds a range of integers represented in the form of a list. On reprend la fonction interval des exercices du chapitre précédent.
```# let` `interval` `order` `next` `a` `b` ``=`` `` `` `` `let` `rec` `aux` `a` ``=`` `` `` `` `` `` `if` `not` `(order` `a` `b)` `then` ``[`a`]`` `else` `` `a` `::` `aux` `` `(next` `a)` `` `` `` `in` `aux` `a` `;;`val interval : ('a -> 'b -> bool) -> ('a -> 'a) -> 'a -> 'b -> 'a list =``  <fun>`

```

2. Write a function eras that calculates the prime numbers on a range of integers starting with 2, according to the algorithm of the Sieve of Eratosthenes.
```# let` `rec` `eras` `l` `` ``=`` `match` `l` `with` `` `` `` `[]` `->` `[]` ``|`` `p::q` `->` `p` `::` `(eras` `(List.filter` `(fun` `x` `->` `x` `mod` `p` ``<>`` ``0`)` `q))` `;;`val eras : int list -> int list = <fun>`

```

Write a function era_go that takes an integer and returns a list of all the prime numbers smaller than this integer.
```# let` `era_go` `n` ``=`` `eras` `(interval` `(`<`)` `(fun` `x` `->` `x` ``+`` ``1`)` ``2`` `n)` `;;`val era_go : int -> int list = <fun>`

```

3. We want to write an executable primes that one will launch by typing the command primes n, where n is an integer. This executable will print the prime numbers smaller than n. For this we must use the Sys module and check whether a parameter was passed. Fichier principal premiers.ml :
```# let` `usage` `()` ``=`` `Printf.printf` ``"Usage: premiers n\n"`;;`val usage : unit -> unit = <fun>`# let` `main` `()` ``=`` `` `` `` `if` `Array.length` `(Sys.argv)` ``<`` ``2`` `then` `usage()` `` `` `else` `` `` `` `` `` `let` `n` ``=`` `int_of_string` `Sys.argv`.`(`1`)` `in` `` `` `` `` `` `if` `n` ``<`` ``2`` `then` `usage()` `` `` `` `` `else` `` `` `` `` `` `` `` `let` `r` ``=`` `era_go` `n` `in` `` `` `` `` `` `` `` `List.iter` `(fun` `x` `->` `Printf.printf` ``"%d "`` `x)` `r;` `` `` `` `` `` `` `Printf.printf` ``"\n"`` `;;`val main : unit -> unit = <fun>`

```
```main()` `;;

```

Construction de l'exécutable :
```\$ ocamlc -o premiers premiers.ml
```
ou
```\$ ocamlopt -o premiers premiers.ml
```
Test de l'exécutable :
```\$ premiers
Usage: premiers n
\$ premiers 50
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
\$ premiers 100
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
```

### Displaying Bitmaps

Bitmaps saved as color array array are bulky. Since 24 bits of color are rarely used, it is possible to encode a bitmap in less space. For this we will analyze the number of colors in a bitmap. If the number is small (for example less than 256) we can encode each pixel in 1 byte, representing the number of the color in the table of colors of this bitmap.

1. Write a function analyze_colors exploring a value of type color array array and that returns a list of all the colors found in this image.
```# let` `analyse_couleurs` `c` ``=`` `` `` `` `let` `l` ``=`` `ref` `[]` `in` `` `` `` `for` `i` ``=`` ``0`` `to` `(Array.length` `c)` ``-`` ``1`` `do` `` `` `` `` `` `for` `j` ``=`` ``0`` `to` `(Array.length` `c`.`(`0`))` ``-``1`` `` `do` `` `` `` `` `` `` `` `if` `not(List.mem` `c`.`(i)`.`(j)` ``!`l)` `then` `l`:=`` `c`.`(i)`.`(j)` `::` ``!`l` `` `` `` `` `done` `;` `` `` `done` `;` `` `` `List.rev` ``!`l` `;;`val analyse_couleurs : 'a array array -> 'a list = <fun>`

```

2. From this list, construct a palette. We will take a vector of colors. The index in the table will correspond to the order of the color, and the contents are the color itself. Write the function find_index that returns the index of a value stored in the array.
```# let` `construire_table` `l` ``=`` `Array.of_list` `l` `;;`val construire_table : 'a list -> 'a array = <fun>`# exception` `Find` `of` `int;;`exception Find of int`# let` `trouve_indice` `c` `t` ``=`` `` `` `` `let` `aux` `()` ``=`` `` `` `` `` `` `for` `i`=``0`` `to` `Array.length` `t` `do` `` `` `` `` `` `` `` `if` `c` ``=`` `t`.`(i)` `then` `raise` `(Find` `i)` `` `` `` `` `done` `;` `` `` `` `` `raise` `Not_found` `` `` `in` `` `` `` `` `` `try` `aux` `()` `with` `Find` `i` `->` `i` `;;`val trouve_indice : 'a -> 'a array -> int = <fun>`

```

3. From this table, write a conversion function, encode, that goes from a color array array to a string. Each pixel is thus represented by a character.
```# let` `encode` `caa` `t` ``=`` `` `` `if` `Array.length` `t` ``>`` ``2``5``5`` `then` `failwith` ``"trop de couleurs (> 255)"`` `` `` `else` `` `` `` `` `` `` `let` `h` ``=`` `Array.length` `caa` `` `` `` `` `` `and` `w` ``=`` `Array.length` `caa`.`(`0`)` `in` `` `` `` `` `` `let` `s` ``=`` `String.create` `(h` ``*`` `w)` `` `in` `` `` `` `` `` `let` `ns` ``=`` `ref` ``0`` `in` `` `` `` `` `` `for` `i` ``=`` ``0`` `to` `h`-``1`` `do` `` `` `` `` `` `` `` `for` `j` ``=`` ``0`` `to` `w`-``1`` `do` `` `` `` `` `` `` `` `` `` `let` `ci` ``=`` `trouve_indice` `caa`.`(i)`.`(j)` `t` `in` `` `` `` `` `` `` `` `` `` `s`.[!`ns`]`` ``<-`` `char_of_int` `ci` `;` `` `` `` `` `` `` `` `` `incr` `ns` `` `` `` `` `` `` `done` `` `` `` `` `done` `;` `` `` `` `` `s` `;;`val encode : 'a array array -> 'a array -> string = <fun>`

```

4. Define a type image_tdc comprising a table that matches colors to a vector of strings, allowing the encoding of a bitmap (or color array) using a smaller method.
```# type` `image_tdc` ``=`` `{` `tdc` ``:`` `Graphics.color` `array;` `image` ``:`` `string;` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `largeur` ``:`` `int;` `hauteur` ``:`` `int};;`type image_tdc =``  { tdc: Graphics.color array;``    image: string;``    largeur: int;``    hauteur: int }`

```

5. Write the function to_image_tdc to convert a color array array to this type.
```# let` `to_image_tdc` `caa` ``=`` `` `` `` `let` `t` ``=`` `construire_table` `(analyse_couleurs` `caa)` `` `in` `` `` `` `let` `s` ``=`` `encode` `caa` `t` `in` `` `` `` `` `` `{` `tdc` ``=`` `t;` `image` ``=`` `s;` `` `` `` `` `` `` `` `largeur` ``=`` `Array.length` `caa`.`(`0`);` `hauteur` ``=`` `Array.length` `caa}` `;;`val to_image_tdc : Graphics.color array array -> image_tdc = <fun>`

```

6. Write the function save_image_tdc to save the values to a file.
```# let` `sauve_image_tdc` `im` `nom` `` ``=`` `` `` `` `let` `oc` ``=`` `open_out` `nom` `in` `` `` `` `Marshal.to_channel` `oc` `im` `[]` `;;`val sauve_image_tdc : 'a -> string -> unit = <fun>`

```

7. Compare the size of the file obtained with the saved version of an equivalent palette. Elle est plus petite, d'un facteur 4!!!

8. Write the function from_image_tdc to do the reverse conversion.
```# let` `from_image_tdc` `im` ``=`` `` `` `` `let` `r` ``=`` `Array.create_matrix` `im`.`hauteur` `im`.`largeur` `Graphics.black` `in` `` `` `` `let` `ns` ``=`` `ref` ``0`` `in` `` `` `` `for` `i` ``=`` ``0`` `to` `im`.`hauteur` ``-``1`` `do` `` `` `` `` `` `for` `j` ``=`` ``0`` `to` `im`.`largeur` ``-``1`` `do` `` `` `` `` `` `` `` `r`.`(i)`.`(j)` ``<-`` `im`.`tdc`.`(int_of_char` `` `im`.`image`.[!`ns`]`)` `;` `` `` `` `` `` `` `incr` `ns` `` `` `` `` `done` `` `` `done` `;` `` `` `r` `;;`val from_image_tdc : image_tdc -> Graphics.color array array = <fun>`

```

9. Use it to display an image saved in a file. The file will be in the form of a value of type bitmap_tdc.
```# let` `visu` `name` `` ``=`` `` `` `` `let` `ic` ``=`` `open_in` `name` `in` `` `` `` `let` `im` ``=`` `Marshal.from_channel` `ic` `in` `` `` `` `let` `caa` ``=`` `from_image_tdc` `im` `in` `` `` `` `let` `b` ``=`` `Graphics.make_image` `caa` `in` `` `` `` `let` `size` ``=`` `(string_of_int` `(Array.length` `caa`.`(`0`)))` `` `` `` `` `` `` `` `` `` `` `` `` `` `` ``^`` ``"x"`` ``^`` `(string_of_int` `(Array.length` `caa))` `in` `` `` `Graphics.open_graph` `(`" "`` ``^`` `size)` `;` `` `` `Graphics.draw_image` `b` ``0`` ``0`` `;` `` `` `b` `;;`val visu : string -> Graphics.image = <fun>`

```