99 Problems in OCaml

The tutorial "99 Problems in OCaml" is an exercise-wise approach to the OCaml programming language. I have adapted the problem set from "99 Problems in Haskell". Similar sets exists for Prolog and Lisp. I believe that the contribution of solutions should be open to anyone. Please feel free to copy this page and the solutions to a wiki, but let me know. If you rather contribute solutions or would like to point out errata, send me an email to ocaml(at)christiankissig.de .

 

Updates

  • The problem62b found improvement and correction with the help of Rekha Rama Pai and Dr Vineeth Palerie. They point out, that my solutions to the binary tree exercises require each node to have precisely two successor. Thereby I deviate from problem sets for Haskell and Prolog, believing that binary means precisely two. Their alternative definition is
    • type bin_tree = Empty | Node of string * bin_tree * bin_tree
  • As you may have noticed, some days ago I have taken this section of my webpage offline. I did so with the intention to overhaul the content. In the meanwhile I have received emails from students of OCaml, asking me to bring the questions and solutions back online. I conceded. Please note the following :
    • These solutions are not optimal. If you have a better solutions to these problems, let me know and I will post sound improvements, acknowledging authorship.
    • The questions have originally been stated for Prolog, and are cumbersome to implement in OCaml. I decided to apply slight modifications, whenever this helps extracting the essence of the problems. Should you feel, the modifications are unjust, do send me your argument.
    • Eventually I will improve the presentation of the problem set. For instance in the section on binary trees, the graphics are missing. Bear with me for now and refer to the orginal problem sets for Haskell whenever you need to.
  • Problem 26 was incorrect, as the solution I proposed would generate permutations of combinations. My thanks to Maurizio D'Addetta for spotting the mistake and pointing it out to me.
  • Nick Fishman pointed out that the list reversal function in Problem 05 is not tail-recursive, so that it runs out of memory on longer lists. His solution is available. Many thanks!
  • Matteo Residori and Deniz Tohumcu spotted a typo in Problem 31. Many thanks!
  • Deniz Tohumcu provided an alternative solution to problem 31. Many thanks!
  • Bart van Deenen provided alternative solutions to problems 5, 6, 8, and 9. Many thanks!
  • I have now moved the files to github.

Problems for Lists

  • 01 : Find the last element of a list.
    [ Solution, OCaml ]
  • 02 : Find the last but one element of a list.
    [ Solution, OCaml ]
  • 03 : Find the K'th element of a list. The first element in the list is number 1.
    [ Solution, OCaml ]
  • 04 : Find the number of elements of a list.
    [ Solution, OCaml ]
  • 05 : Reverse a list.
    [ Solution, OCaml ]
  • 06 : Find out whether a list is a palindrome. A palindrome can be read forward or backward; e.g. (x a m a x).
    [ Solution, OCaml ]
  • 07 : Flatten a nested list structure
    [ Solution, OCaml ]
  • 08 : Eliminate consecutive duplicates of list elements.
    [ Solution, OCaml ]
  • 09 : Pack consecutive duplicates of list elements into sublists. If a list contains repeated elements they should be placed in separate sublists.
    [ Solution, OCaml ]
  • 10 : Run-length encoding of a list. Use the result of problem P09 to implement the so-called run-length encoding data compression method. Consecutive duplicates of elements are encoded as lists (N E) where N is the number of duplicates of the element E.
    [ Solution, OCaml ]
  • 11: Modified run-length encoding. Modify the result of problem 10 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.
    [ Solution, OCaml ]
  • 12: Decode a run-length encoded list. Given a run-length code list generated as specified in problem 11. Construct its uncompressed version.
    [ Solution, OCaml ]
  • 13: Run-length encoding of a list (direct solution). 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, but only count them. As in problem P11, simplify the result list by replacing the singleton lists (1 X) by X.
    [ Solution, OCaml ]
  • 14: Duplicate the elements of a list.
    [ Solution, OCaml ]
  • 15: Replicate the elements of a list a given number of times.
    [ Solution, OCaml ]
  • 16: Drop every N'th element from a list.
    [ Solution, OCaml ]
  • 17: Split a list into two parts; the length of the first part is given.
    [ Solution, OCaml ]
  • 18: Extract a slice from a list.
    [ Solution, OCaml ]
  • 19: Rotate a list N places to the left.
    [ Solution, OCaml ]
  • 20: Remove the K'th element from a list.
    [ Solution, OCaml ]
  • 21: Insert an element at a given position into a list.
    [ Solution, OCaml ]
  • 22: Create a list containing all integers within a given range.
    [ Solution, OCaml ]
  • 23: Extract a given number of randomly selected elements from a list.
    [ Solution, OCaml ]
  • 24: Lotto: Draw N different random numbers from the set 1..M.
    [ Solution, OCaml ]
  • 25: Generate a random permutation of the elements of a list.
    [ Solution, OCaml ]
  • 26: Generate the combinations of K distinct objects chosen from the N elements of a list In how many ways can a committee of 3 be chosen from a group of 12 people? We all know that there are C(12,3) = 220 possibilities (C(N,K) denotes the well-known binomial coefficients). For pure mathematicians, this result may be great. But we want to really generate all the possibilities in a list.
    [ Solution, OCaml ]
  • 27: Group the elements of a set into disjoint subsets.
    [ Solution, OCaml ]
  • 28: Sorting a list of lists according to length of sublists.
    [ Solution, OCaml ]

Problems in Arithmetic

  • 31: Determine whether a given integer number is prime.
    [ Solution, OCaml ]
  • 32: Determine the greatest common divisor of two positive integer numbers.
    [ Solution, OCaml ]
  • 33: Determine whether two positive integer numbers are coprime. Two numbers are coprime if their greatest common divisor equals 1.
    [ Solution, OCaml ]
  • 34: Calculate Euler's totient function phi(m). Euler's so-called totient function phi(m) is defined as the number of positive integers r (1 <= r < m) that are coprime to m. Example: m = 10: r = 1,3,7,9; thus phi(m) = 4. Note the special case: phi(1) = 1.
    [ Solution, OCaml ]
  • 35: Determine the prime factors of a given positive integer. Construct a flat list containing the prime factors in ascending order.
    [ Solution, OCaml ]
  • 36: Determine the prime factors of a given positive integer.
    [ Solution, OCaml ]
  • 37: Calculate Euler's totient function phi(m) (improved). See problem 34 for the definition of Euler's totient function. If the list of the prime factors of a number m is known in the form of problem 36 then the function phi(m) can be efficiently calculated as follows: Let ((p1 m1) (p2 m2) (p3 m3) ...) be the list of prime factors (and their multiplicities) of a given number m. Then phi(m) can be calculated with the following formula:
    phi(m) = (p1 - 1) * p1 ** (m1 - 1) + (p2 - 1) * p2 ** (m2 - 1) + (p3 - 1) * p3 ** (m3 - 1) + ...

    Note that a ** b stands for the b'th power of a. Note: Actually, the official problems show this as a sum, but it should be a product.
    [ Solution, OCaml ]

  • 38: Compare the two methods of calculating Euler's totient function.
    [ Solution, OCaml ]
  • 39: A list of prime numbers.
    [ Solution, OCaml ]
  • 40: Goldbach's conjecture. Goldbach's conjecture says that every positive even number greater than 2 is the sum of two prime numbers. Example: 28 = 5 + 23. It is one of the most famous facts in number theory that has not been proved to be correct in the general case. It has been numerically confirmed up to very large numbers (much larger than w e can go with our Prolog system). Write a predicate to find the two prime numbers that sum up to a given even integer.
    [ Solution, OCaml ]
  • 41: Given a range of integers by its lower and upper limit, print a list of all even numbers and their Goldbach composition.
    [ Solution, OCaml ]

Problems in Logics and Codes

  • 46: Define predicates and/2, or/2, nand/2, nor/2, xor/2, impl/2 and equ/2 (for logical equivalence) which succeed or fail according to the result of their respective operations; e.g. and(A,B) will succeed, if and only if both A and B succeed.
    [ Solution, OCaml ]
  • 47: Truth tables for logical expressions (2).

    Continue problem P46 by defining and/2, or/2, etc as being operators. This allows to write the logical expression in the more natural way, as in the example: A and (A or not B). Define operator precedence as usual; i.e. as in Java.
    [ Solution, OCaml ]

  • 48: Truth tables for logical expressions (3).

    Generalize problem P47 in such a way that the logical expression may contain any number of logical variables. Define table/2 in a way that table(List,Expr) prints the truth table for the expression Expr, which contains the logical variables enumerated in List.
    [ Solution, OCaml ]

  • 49: Gray codes.
    [ Solution, OCaml ]
  • 50: Huffman codes.
    [ Solution, OCaml ]

Problems in Binary Trees

  • 54A: Check whether a given term represents a binary tree
    [ Solution, OCaml ]
  • 55: Construct completely balanced binary trees
    [ Solution, OCaml ]
  • 56: Symmetric binary trees
    [ Solution, OCaml ]
  • 57: Binary search trees (dictionaries)
    [ Solution, OCaml ]
  • 58: Generate-and-test paradigm
    [ Solution, OCaml
  • 59: Construct height-balanced binary trees
    [ Solution, OCaml ]
  • 60: Construct height-balanced binary trees with a given number of nodes Consider a height-balanced binary tree of height H. What is the maximum number of nodes it can contain? Clearly, MaxN = 2**H - 1. However, what is the minimum number MinN? This question is more difficult. Try to find a recursive statement and turn it into a function minNodes that returns the minimum number of nodes in a height-balanced binary tree of height H.
    [ Solution, OCaml ]
  • 61: Count the leaves of a binary tree
    [ Solution, OCaml ]
  • 61A: Collect the leaves of a binary tree in a list
    [ Solution, OCaml ]
  • 62: Collect the internal nodes of a binary tree in a list An internal node of a binary tree has either one or two non-empty successors. Write a predicate internals/2 to collect them in a list.
    [ Solution, OCaml ]
  • 62B: Collect the nodes at a given level in a list A node of a binary tree is at level N if the path from the root to the node has length N-1. The root node is at level 1. Write a predicate atlevel/3 to collect all nodes at a given level in a list.
    [ Solution, OCaml ]
  • 63: Construct a complete binary tree
  • [ Solution, OCaml ]
  • 64: Drawing Binary Trees
  • [ Solution, OCaml ]
  • 65: Drawing Binary Trees (2)
  • [ Solution, OCaml ]
  • 66: Drawing Binary Trees (3)
  • 67: A string representation of binary trees
    [ Solution, OCaml ]
  • 68: Preorder and inorder sequences of binary trees. We consider binary trees with nodes that are identified by single lower-case letters, as in the example of problem P67.

    a) Write predicates preorder/2 and inorder/2 that construct the preorder and inorder sequence of a given binary tree, respectively. The results should be atoms, e.g. 'abdecfg' for the preorder sequence of the example in problem P67.

    b) Can you use preorder/2 from problem part a) in the reverse direction; i.e. given a preorder sequence, construct a corresponding tree? If not, make the necessary arrangements.

    c) If both the preorder sequence and the inorder sequence of the nodes of a binary tree are given, then the tree is determined unambiguously. Write a predicate pre_in_tree/3 that does the job.
    [ Solution, OCaml ]

  • 69: Dotstring representation of binary trees. We consider again binary trees with nodes that are identified by single lower-case letters, as in the example of problem P67. Such a tree can be represented by the preorder sequence of its nodes in which dots (.) are inserted where an empty subtree (nil) is encountered during the tree traversal. For example, the tree shown in problem P67 is represented as 'abd..e..c.fg...'. First, try to establish a syntax (BNF or syntax diagrams) and then write a predicate tree_dotstring/2 which does the conversion in both directions. Use difference lists.

Problems for Multiway Trees

  • 70B: Check whether a given term represents a multiway tree.
  • 70C: Count the nodes of a multiway tree.
    [ Solution, OCaml ]
  • 70: Tree construction from a node string.
  • 71: Determine the internal path length of a tree.
    [ Solution, OCaml ]
  • 72: Construct the bottom-up order sequence of the tree nodes.
  • 73: Lisp-like tree representation.
    [ Solution, OCaml ]

Problems for Graphs

  • 81: Path from one node to another one.

Miscellaneous Problems