John Whitington - More OCaml: Algorithms, Methods, and Diversions

MORE OCAML Algorithms, Methods & Diversions

In More OCaml John Whitington takes a meandering tour of functional programming with OCaml, introducing various language features and describing some classic algorithms. The book ends with a large worked example dealing with the production of PDF files. There are questions for each chapter together with worked answers and hints.

More OCaml will appeal both to existing OCaml programmers who wish to brush up their skills, and to experienced programmers eager to explore functional languages such as OCaml. It is hoped that each reader will find something new, or see an old thing in a new light. For the more casual reader, or those who are used to a different functional language, a summary of basic OCaml is provided at the front of the book.

JOHN WHITINGTON founded a software company which uses OCaml extensively. He teaches functional programming to students of Computer Science at the University of Cambridge. His other books include PDF Explained (OReilly, 2012) and OCaml from the Very Beginning (Coherent, 2013).

MORE OCAML
Algorithms, Methods & Diversions John WhitingtonC O H E R E N T P R E S SC O H E R E N T P R E S S
Cambridge Published in the United Kingdom by Coherent Press, Cambridge Coherent Press 2014
This publication is in copyright. Subject to statutory
exception no reproduction of any part may take place
without the written permission of Coherent Press.
First published August 2014 A catalogue record for this book is available from the British Library
by the same author
PDF Explained (OReilly, 2012)
OCaml from the Very Beginning (Coherent, 2013)

Contents

A
A
A

Preface

When I wrote OCaml from the Very Beginning, the intention was to have a book with no prerequisites a bright individual, new to programming, could follow it. Because of this, and for length concerns, plenty of interesting material had to be omitted. This text, not being constrained in the same way, contains a variety of topics which require some existing experience with a functional language. Those who have read the previous text should have no problem with this one. Equally, it should be comprehensible to a functional programmer familiar with another language such as Standard ML or Haskell. The reader may need to make occasional reference to the OCaml manual.

There are, typically, two different activities when writing programs larger than a few dozen lines: firstly, dealing with the challenges of complexity inherent in the problem, by finding appropriate abstraction mechanisms and, secondly, finding and using the wide range of third-party libraries available for a given language. Most projects involve a combination of the two. In this text we concentrate wholly on the former, using nothing other than the OCaml Standard Library. Keeping up with the myriad third-party OCaml libraries is a task better suited to other media.

The book consists of sixteen short chapters falling broadly into three categories. Some introduce pieces of OCaml syntax with worked examples. Some survey practical topics such as input/output. Some cover little diversions or puzzles. The main matter of the book ends with a lengthy worked example: a program to build PDF files containing computer-generated drawings and text. There are full answers and hints for all questions in the book, and additional material in the online resources.

Acknowledgments

The quotation in Chapter 6 is taken from ISO-32000 International Organization for Standardization. The tables of codes in the same chapter are taken from ITU-T T.30 International Telecommunication Union. The presentation of the balancing operation for Red-Black trees in Chapter 11 and its functional implementation is due to Chris Okasaki, as described in the invaluable Purely Functional Data Structures (Cambridge University Press, ISBN 978-0521663502, 1998). Chapter 12 was inspired by a University of Cambridge Computer Science Tripos exam question set by Lawrence C. Paulson in 1999. Question 3 of that chapter is due to Peter D. Schumer in Mathematical Journeys (John Wiley & Sons, ISBN 0-471-22066-3, 2004).

I am grateful to the many colleagues and friends with whom I have been able to discuss OCaml style and substance, including Mark Shinwell, Leo White, Daniel Bnzli, Anil Madhavapeddy, Stephen Dolan and many others whom I have forgotten. Helpful comments on an earlier draft were provided by Stefan Schmiedl, Manuel Cornes, Jonas Blow, Emmanuel Delaborde, Mario Alvarez Picallo, Giannis Tsaraias, Emmanuel Oga, and Andr Bjrby.

Summary of Basic OCaml

This chapter contains a summary of each OCaml construct used in the book, together with some examples. Pieces of OCaml syntax not contained in this chapter will be introduced as and when they are needed throughout the rest of the book. Existing OCaml programmers may skip this chapter.

Simple Data Types

Integers min_int -3 -2 -1 max_int of type int . Booleans true and false of type bool . Characters of type char like 'X' and '!' .

Mathematical operators + - * / mod which take two integers and give another.

Operators = < <= > >= <> which compare two values and evaluate to either true or false .

The conditional if expression1 then expression2 else expression3 , where expresssion1 has type bool and expression2 and expression3 have the same type as one another.

The boolean operators && (logical AND) and || (logical OR) which allow us to build compound boolean expressions.

Tuples to combine a fixed number of elements (a, b) , (a, b, c) etc. with types , etc. For example, (1, '1') is a tuple of type int char . On the screen, OCaml writes 'a for etc.

Strings, which are sequences of characters written between double quotes and are of type string . For example, "one" has type string .

Names and Functions

Assigning a name to the result of evaluating an expression using the let name = expression construct.

let x = 5 > 2 x is new, and is false

Building compound expressions using let name1 = expression1 in let name2 = expression2 in

let x = 4 in let y = 5 in x + y

Anonymous (un-named) functions fun name -> expression .

Making operators into functions as in ( < ) and ( + ) .

( + ) 1 2

Functions, introduced by let name argument1 argument2 = expression . These have type , etc. for some types , , etc. For example, let f a b = a > b is a function of type bool .

Recursive functions, which are introduced in the same way, but using let rec instead of let . For example, here is a function g which calculates the smallest power of two greater than or equal to a given positive integer, using the recursive function f :

let rec f x y =
if y < x then f x (2 * y) else y
let g z = f z 1

Mutually recursive functions, introduced by writing let rec f x = and g y = and

Pattern Matching

Matching patterns using match expression1 with pattern1 | -> expression2 | pattern2 | -> expression3 | The expressions expression2 , expression3 etc. must have the same type as one another, and this is the type of the whole match with expression. The special pattern _ which matches anything.

Next page