ex-lists

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]

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]

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');;

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]

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]]

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.

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 [x_{1},…,x_{n}] such that:

- x
_{i}∈1..n for all i∈1..n - x
_{i}≠x_{j}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.

- 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). - 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 E_{k}(i) = (i + k) mod 26. For instance,`shift_encrypt 3 'a'`

evaluates to`d`

, because E_{3}(0) = (0 + 3) mod 26 = 3 and`shift_encrypt 3 'z'`

evaluates to`c`

, because E_{3}(25) = (25 + 3) mod 26 = 2. - 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 D_{k}(j) = (j - k) mod 26. - 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. - 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;;

Let k = k_{1} … k_{m}
and c = c_{0} … c_{m-1}
be two lists of length m.
Let the sequence z_{1} z_{2} … 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 z_{1} z_{2} … z_{n}

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 = x_{1} … x_{n} 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 = z_{1} … z_{n}.

Then, the encryption of x (under key k,c) is the list y = y_{1} … y_{n}
such that y_{i} = (x_{i} + z_{i}) mod 2.

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.

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 [(x`

, assuming that there exists an index i such that
x=x_{1},n_{1});…;(x_{k},n_{k})]_{i}, produces the list `[(x`

_{1},n_{1});…;(x_{i},n_{i+1});…;(x_{k},n_{k})]

3. `fcount [x`

evaluates to the list _{1};…;x_{k}]`[(x`

,
where _{1},n_{1});…;(x_{k},n_{k})]`n`

is the number of occurrences of _{i}`x`

in _{i}`l`

, for all i.

ex-lists.txt · Last modified: 2015/10/08 15:20 (external edit)