ex-lists

# LiP assignment #4

## 1. Fibonacci sequence

Write a fuction that, given as input a natural `n`, outputs the list of the first `n` Fibonacci numbers. You must use a linear-time complexity algorithm to compute Fibonacci numbers. For instance, for n=10 you must obtain the following output:

```# fib 10;;
- : int list = [0; 1; 1; 2; 3; 5; 8; 13; 21; 34]```

## 2. Prime numbers

Write a function that outputs the list of the prime numbers lower or equal to n. For instance, for n=20 you must obtain the following output:

```# primes 20;;
- : int list = [2; 3; 5; 7; 11; 13; 17; 19]```

## 3. Palindromes

Write a function that output the list of the first n palindrome numbers greater or equal to m. For instance, if n=10 and m=150, you must obtain the following output:

```# palseq 150 10;;
- : int list = [151; 161; 171; 181; 191; 202; 212; 222; 232; 242]```

Hint. You can use the function `string_of_int` to transform an integer into a string, and the following code snippet to transform such a string into a list of integers:

```# let rec list_of_string s =
if s="" then []
else let s' = (String.sub s 1 ((String.length s)-1))
in  (String.get s 0)::(list_of_string s');;```

## 4. Merge sort

Write a function that sorts the elements of a list according to a given comparison function, using the merge sort algorithm. The comparison function must return 0 if its arguments compare as equal, a positive integer if the first is greater, and a negative integer if the first is smaller. For instance, you must have:

```# sort [3;4;5;1;2;7;6] compare;;
- : int list = [1; 2; 3; 4; 5; 6; 7]```

## 5. Permutations

Write a function that, taken as input a list `l`, produces a list contaning all the permutations of the elements of the `l`. For instance, you must obtain:

```# perm [1;2;3];;
- : int list list = [[1; 2; 3]; [2; 1; 3]; [2; 3; 1]; [1; 3; 2]; [3; 1; 2]; [3; 2; 1]]```

## 6. Letter frequency

Write a function `freq` that takes as input a name `f` of a text file, and outputs a list of pairs `(x,d)`, where `x` is a letter occurring in the text file, and `d` is the associated frequency (`d` = number of occurrences of `x` / total number of letters). The list must be ordered by frequency (in decreasing order).

Hint. Use the following functions for opening/closing files, and for reading text lines:

```open_in : string -> in_channel
close_in : in_channel -> unit
input_line : in_channel -> string```
• `open_in f` opens the file named f for reading, and returns a new input channel on that file, positioned at the beginning of the file. Raises `Sys_error` if the file could not be opened.
• `close_in ch` closes the channel `ch`. Input functions raise a `Sys_error` exception when they are applied to a closed input channel, except close_in, which does nothing when applied to an already closed channel. Note that `close_in` may raise `Sys_error` if the operating system signals an error.
• `input line ch` reads characters from the input channel `ch`, until a newline character is encountered. Returns the string of all characters read, without the newline character at the end. Raises `End_of_file` if the end of the file is reached at the beginning of line.

## 7. Random permutation

Write a function `genperm` that, taken as input an integer n, produces as output a random permutation of 1..n, i.e. a list of integers [x1,…,xn] such that:

1. xi∈1..n for all i∈1..n
2. xi≠xj for all i≠j.

For instance, a possible output of `genperm 10` could be:

`- : int list = [10; 3; 7; 4; 9; 5; 2; 6; 1; 8]`

Hint. You should *not* use the function `perm` of Exercise 5. Use the expression `Random.int n` to generate a random integer between 0 and n-1.

## 8. Shift cipher

1. Write a function `charpos: char → int` that gives the position of a character. For instance, `charpos 'a' ` evaluates to 0, `charpos 'b' ` evaluates to 1, etc. (We assume the english alphabet, and that positions start from 0).
2. Write a function `shift_encrypt: int → char → char` such that `shift_encrypt k x` is the encryption of a character `x` under the key `k`. The encryption of character x (with position i) is defined as the character with position Ek(i) = (i + k) mod 26. For instance, `shift_encrypt 3 'a' ` evaluates to `d`, because E3(0) = (0 + 3) mod 26 = 3 and `shift_encrypt 3 'z' ` evaluates to `c`, because E3(25) = (25 + 3) mod 26 = 2.
3. Write a function `shift_decrypt: int → char → char` such that `shift_decrypt k y` is the decryption of a character `y` under the key `k`. The decryption of a character y (with position j) under a key k is defined as the character with position Dk(j) = (j - k) mod 26.
4. Write a function `shift_encrypt_file: int → string → string` that, taken as input an integer key `k` and the names of two files (`in`, `out`), writes in the file `out` the encryption of the file `in`. You can assume that the input file only contains lowercase letters a-z.
5. Write a function `shift_decrypt_file: int → string → string` that, taken as input an integer key `k` and the names of two files (`in`, `out`), writes in the file `out` the decryption of the file `in`.

Hint. Use the following function to get a list of characters from a string:

```let rec list_of_string s =
if s="" then []
else let s' = (String.sub s 1 ((String.length s)-1)) in
let l= list_of_string s' in
let c = String.get s 0 in
c::l;;```

## 9. LFSR keystream

Let k = k1 … km and c = c0 … cm-1 be two lists of length m. Let the sequence z1 z2 … be defined as follows, for all i>0:

Write a function `keystream : int → int list → int list → int list` such that `keystream n c k` evaluates to the list z1 z2 … zn

For instance, if `k = [1;0;0;0]` and `c = [1;1;0;0]`, we will have:

```keystream 15 c k;;
- : int list = [1; 0; 0; 0; 1; 0; 0; 1; 1; 0; 1; 0; 1; 1; 1]```

Then, write a function `lfsr_encrypt: int list → int list → int list → int list` such that `lfsr_encrypt c k x` evaluates to the encryption of the list `x` with the LFSR stream cipher, which is defined as follows.

Let x = x1 … xn is a list of 0/1 (of arbitrary length), let c,k be lists of 0/1 (of equal length), and assume that `keystream n c k` evaluates to the list z = z1 … zn.

Then, the encryption of x (under key k,c) is the list y = y1 … yn such that yi = (xi + zi) mod 2.

## 10. Dutch national flag problem

1) Consider a list of elements of type `'a * string` and two functions `isred : 'a * string → bool` and `isblue : 'a * string → bool` Assume that for each element `x` of the list, either `isred x` or `isblue x` (but not both) is true. Write a recursive function `order : ('a * string) list → ('a * string) list` that orders the list, by putting all the red elements before all the blue ones. The ordering among the elements of the same colour is not relevant. For instance:

```let l = [1,"b"; 2,"r"; 3,"r"; 4,"b"];;
# val l : (int * string) list = [(1, "b"); (2, "r"); (3, "r"); (4, "b")]

order l;;
# - : (int * string) list = [(2, "r"); (3, "r"); (4, "b"); (1, "b")]```

2) Solve the previous problem using the `List.fold_right` function and no recursion.

3) Solve the previous problem using the `List.fold_left` function and no recursion.

4) Consider having also the function `iswhite : 'a * string → bool` and assume that for each element `x` of the list, only one between `isred x` or `isblue x` or ` iswhite x` is true. Write a recursive function `order : ('a * string) list → ('a * string) list` that orders the list, by putting all the elements in the red - white - blue ordering. The ordering among the elements of the same colour is not relevant. For instance:

```let l = [1,"b"; 2,"r"; 3,"r"; 4,"b"; 5,"w"];;
# val l : (int * string) list = [(1, "b"); (2, "r"); (3, "r"); (4, "b"); (5, "w")]

order l;;
# - : (int * string) list = [(2, "r"); (3, "r"); (5, "w"); (1, "b"); (4, "b")]```

5) Solve the previous problem using the `List.fold_right` function and no recursion.

6) Solve the previous problem using the `List.fold_left` function and no recursion.

## 11. Number of occurrences in a list

Complete the following definitions:

```# let fsearch = List.fold_right ...
val fsearch : 'a -> ('a * 'b) list -> bool

# let fadd    = List.fold_right ...
val fadd :  'a -> ('a * int) list -> ('a * int) list

# let fcount  = List.fold_right ...
val fcount : 'a list -> ('a * int) list ```

such that:

1. `fsearch x l` evaluates to true iff `x` belongs to the list `l`.

2. `fadd x [(x1,n1);…;(xk,nk)]`, assuming that there exists an index i such that x=xi, produces the list `[(x1,n1);…;(xi,ni+1);…;(xk,nk)]`

3. `fcount [x1;…;xk]` evaluates to the list `[(x1,n1);…;(xk,nk)]`, where `ni` is the number of occurrences of `xi` in `l`, for all i.