O'Reilly logo

Real World OCaml by Jason Hickey, Anil Madhavapeddy, Yaron Minsky

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Chapter 3. Lists and Patterns

This chapter will focus on two common elements of programming in OCaml: lists and pattern matching. Both of these were discussed in Chapter 1, but we’ll go into more depth here, presenting the two topics together and using one to help illustrate the other.

List Basics

An OCaml list is an immutable, finite sequence of elements of the same type. As we’ve seen, OCaml lists can be generated using a bracket-and-semicolon notation:

OCaml utop

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

And they can also be generated using the equivalent :: notation:

OCaml utop (part 1)

# 1 :: (2 :: (3 :: [])) ;;
- : int list = [1; 2; 3]
# 1 :: 2 :: 3 :: [] ;;
- : int list = [1; 2; 3]

As you can see, the :: operator is right-associative, which means that we can build up lists without parentheses. The empty list [] is used to terminate a list. Note that the empty list is polymorphic, meaning it can be used with elements of any type, as you can see here:

OCaml utop (part 2)

# let empty = [];;
val empty : 'a list = []
# 3 :: empty;;
- : int list = [3]
# "three" :: empty;;
- : string list = ["three"]

The way in which the :: operator attaches elements to the front of a list reflects the fact that OCaml’s lists are in fact singly linked lists. The figure below is a rough graphical representation of how the list 1 :: 2 :: 3 :: [] is laid out as a data structure. The final arrow (from the box containing 3) points to the empty list.

Diagram

Each :: essentially adds a new block to the proceding picture. ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required