# OCmal - 99 Problems (1-13)

OCaml website lists 99 basic problems. Here I give the solutions and explain them.

### List

#### 1. Write a function last : 'a list -> 'a option that returns the last element of a list. (easy)

In face, a loop in OCaml could be represented by a recursive function. We use **match** to consider different cases of list: empty, one element, more than one elements.

1 | let rec last lst = |

#### 2. Find the last but one (last and penultimate) elements of a list. (easy)

This problem ask you return last two elements of a list if it has. It is similar to the first problem.

1 | let last_two lst = |

#### 3. Find the k’th element of a list. (easy)

To solve this problem, it seem that we need a counter inside to compute the number of loops. When we traverse the list, assume the list is hd :: tl, if k is equal to 1, then return hd, otherwise traverse tl with k - 1.

1 | let rec list_nth lst k = |

OCaml List module provides List.nth function.

1 | let nth l n = |

#### 4. return the length of a list. (easy)

1 | let length lst = |

#### 5. Reverse a list. (easy)

1 | let rev lst = |

#### 6. Find out whether a list is a palindrome. (easy)

1 | let is_palindrome lst = |

#### 8. Eliminate consecutive duplicates of list elements. (medium)

1 | let rec compress lst = |

#### 9. Pack consecutive duplicates of list elements into sublists. (medium)

This problem is a little difficult. Usually, we will use local variables to store the temporary list and final list in C++. However, in OCaml, the idea is to define **aux** function with parameters. The parameters are regarded as local variables. In the code shown below, **cur** stores the current list store the same elements and **acc** store the whole list.

1 | pack ["a";"a";"a";"a";"b";"c";"c";"a";"a";"d";"d";"e";"e";"e";"e"];; |

If you like C++ style, you can implement like this

1 | let pack_v2 list = |

#### 10. Run-length encoding of a list. (easy)

This problem is similar to the 9th problem.

1 | encode ["a";"a";"a";"a";"b";"c";"c";"a";"a";"d";"e";"e";"e";"e"];; |

#### 11. Modified run-length encoding. (easy)

Modify the result of the previous problem in such a way that if an element has no duplicates it is simply copied into the result list. Only elements with duplicates are transferred as (N E) lists.

Since OCaml lists are homogeneous, one needs to define a type to hold both single elements and sub-lists.

1 | encode ["a";"a";"a";"a";"b";"c";"c";"a";"a";"d";"e";"e";"e";"e"];; |

#### 12. Decode a run-length encoded list. (medium)

Given a run-length code list generated as specified in the previous problem, construct its uncompressed version.

tips: use variable **acc** (represented by a parameter) to store the result. If match **One x**; then add x into acc. If match **Many (n x)**, then add x n times. One solution is to write a **for** loop. Or we write a recursive function.

1 | let rec many acc n x = |

This loop adds **x** into **acc** n times and return **acc**.

1 | decode [Many (4,"a"); One "b"; Many (2,"c"); Many (2,"a"); One "d"; Many (4,"e")];; |

#### 13. Run-length encoding of a list (direct solution). (medium)

Implement the so-called run-length encoding data compression method directly. I.e. don’t explicitly create the sublists containing the duplicates, as in problem “**9. Pack consecutive duplicates of list elements into sublists**”, but only count them. As in problem “10. Modified run-length encoding”, simplify the result list by replacing the singleton lists (1 X) by X.

1 | encode ["a";"a";"a";"a";"b";"c";"c";"a";"a";"d";"e";"e";"e";"e"];; |

1 | let encode list = |