Discounts Using Lists ​

You’ve implemented the logic for the burger discounts that will be applied on International Burger Day, but something feels off. The code inside the Discount module is safe, in the sense that it doesn’t raise exceptions, so when it’s used in the app, it won’t crash. But the current logic in Discount.getFreeBurger is a little fragile, since you have to remember to not change the order of function invocations in such a way that the function will accidentally change the input array. You have a test in DiscountTests which tests for that possibility, but you know that tests are only as reliable as the humans that maintain them. By now, you’ve come to realize that The OCaml Way should be to rewrite the function so that it cannot have side effects.

Introduction to lists ​

A list is a sequential data structure that can often be used in place of an array. In OCaml, lists are implemented as singly-linked lists. The main limitation is that they don’t allow constant-time access to any element except the first one (also known as the head of a list). Most operations on lists go through the Stdlib.List module, which has many functions that are equivalent to the ones you’ve already used in Js.Array.

Refactor Discount.getFreeBurger ​

Let’s refactor Discount.getFreeBurger to accept list(Item.t) instead of array(Item.t):

/** Buy 2 burgers, get 1 free */
let getFreeBurger = (items: list(Item.t)) => {
  let prices =
    items
    |> List.filter(item =>
         switch (item) {
         | Item.Burger(_) => true
         | Sandwich(_)
         | Hotdog => false
         }
       )
    |> List.map(Item.toPrice)
    |> List.sort((x, y) => - compare(x, y));

  switch (prices) {
  | []
  | [_] => None
  | [_, cheaperPrice, ..._] => Some(cheaperPrice)
  };
};

/** Buy 2 burgers, get 1 free */
let getFreeBurger = (items: list(Item.t)) => {
  let prices =
    items
    |> List.filter(item =>
         switch (item) {
         | Item.Burger(_) => true
         | Sandwich(_)
         | Hotdog => false
         }
       )
    |> List.map(Item.toPrice)
    |> List.sort((x, y) => - compare(x, y));

  switch (prices) {
  | []
  | [_] => None
  | [_, cheaperPrice, ..._] => Some(cheaperPrice)
  };
};

There are a lot of things to talk about in this piece of code—let’s go through them one by one.

Documentation comment ​

You might have noticed that the comment at the beginning of the function has a different format than before:

// Buy 2 burgers, get 1 free 
/** Buy 2 burgers, get 1 free */ 

// Buy 2 burgers, get 1 free 
/** Buy 2 burgers, get 1 free */ 

This is a documentation comment, a special comment that is attached to the function it appears above. Go to DiscountTests and hover over an invocation of getFreeBurger—the editor will display a popup showing both the type signature and documentation comment of this function:

Documentation comments can also be attached to modules, types, and variables. Besides showing up in editor popups, they are also consumed by documentation generators like odoc.

List functions ​

We replaced these functions with their counterparts in the List module:

• Js.Array.filter → List.filter. Note that List.filter doesn’t accept the labeled argument ~f, because the functions inside List don’t use labeled arguments.
• Js.Array.map → List.map. List.map also doesn’t accept the labeled argument ~f.
• Js.Array.sortInPlaceWith → List.sort. List.sort returns a brand new list, because, unlike Js.Array.sortInPlaceWith, it doesn’t modify its argument (and it can’t, since lists are immutable).

Pattern match on lists ​

The switch expression in Discount.getFreeBurgers accepts the entire prices list. Unlike with arrays, we can pattern match on lists even if we don’t know the length of the list.

Inside the “failure” branch of the switch expression, we see this:

| []
| [_] => None

| []
| [_] => None

This pattern matches both empty lists and lists with one element, and returns None.

Inside the “success” branch of the switch expression, we have:

| [_, cheaperPrice, ..._] => Some(cheaperPrice)

| [_, cheaperPrice, ..._] => Some(cheaperPrice)

This pattern will match on lists that have at least two elements. The first element is ignored via the wildcard pattern _. The second element is bound to the name cheaperPrice, which is encased in Some and returned. We use list spread syntax (...) to indicate that the list can have more than the two elements we explicitly matched on.

List spread syntax ​

The spread operator (...) can also be used to create a new list by prepending elements to an existing list:

let list = [1, 2, 3];
Js.log([0, ...list]); // [0, 1, 2, 3]
Js.log([-1, 0, ...list]); // [-1, 0, 1, 2, 3]

let list = [1, 2, 3];
Js.log([0, ...list]); // [0, 1, 2, 3]
Js.log([-1, 0, ...list]); // [-1, 0, 1, 2, 3]

[1, 2, 3]

[1, 2, 3]

[1, ...[2, ...[3, ...[]]]]

[1, ...[2, ...[3, ...[]]]]

When pattern matching, the spread operator allows you to bind the tail of a list to a name:

switch ([1, 2, 3]) {
| [_, ...tail] => Js.log(tail) // [2, 3]
| _ => ()
};

switch ([1, 2, 3]) {
| [_, _, _, ...tail] => Js.log(tail) // []
| _ => ()
};

switch ([1, 2, 3]) {
| [_, ...tail] => Js.log(tail) // [2, 3]
| _ => ()
};

switch ([1, 2, 3]) {
| [_, _, _, ...tail] => Js.log(tail) // []
| _ => ()
};

The tail of the list is the sublist that remains after you extract the first n elements from the front of the list. As you can see, the tail might be the empty list ([]). In practice, you don’t need to bind the tail to a name unless you’re writing a custom list function. Often, you’ll just bind the tail to the wildcard pattern _, effectively ignoring it:

switch (["one", "two", "three"]) {
| [a, b, ..._] => Js.log(a ++ ", " ++ b ++ ", etc") // one, two, etc
| _ => ()
};

switch (["one", "two", "three"]) {
| [a, b, ..._] => Js.log(a ++ ", " ++ b ++ ", etc") // one, two, etc
| _ => ()
};

Runtime representation of lists ​

Run this snippet in Melange Playground:

Js.log3(Array.of_list([]), "->", []);
Js.log3(Array.of_list([42]), "->", [42]);
Js.log3(Array.of_list([4, 5, 6]), "->", [4, 5, 6]);

Js.log3(Array.of_list([]), "->", []);
Js.log3(Array.of_list([42]), "->", [42]);
Js.log3(Array.of_list([4, 5, 6]), "->", [4, 5, 6]);

You’ll see this output:

[] -> 0
[42] -> {"hd":42,"tl":0}
[4,5,6] -> {"hd":4,"tl":{"hd":5,"tl":{"hd":6,"tl":0}}}

[] -> 0
[42] -> {"hd":42,"tl":0}
[4,5,6] -> {"hd":4,"tl":{"hd":5,"tl":{"hd":6,"tl":0}}}

The list [4, 5, 6] becomes this object in the JS runtime (pretty printed for readability):

{
  "hd": 4,
  "tl": {
    "hd": 5,
    "tl": {
      "hd": 6,
      "tl": 0
    }
  }
}

{
  "hd": 4,
  "tl": {
    "hd": 5,
    "tl": {
      "hd": 6,
      "tl": 0
    }
  }
}

An empty list in the JS runtime is represented by 0. A non-empty list is represented by an object with fields hd (for the head) and tl (for the tail).

Fix tests for Discount.getFreeBurger ​

You should be getting this compilation error for DiscountTests:

File "src/order-confirmation/DiscountTests.re", lines 15-19, characters 32-11:
15 | ................................[|
16 |            Hotdog,
17 |            Sandwich(Ham),
18 |            Sandwich(Turducken),
19 |          |]..
Error: This expression has type 'a array
       but an expression was expected of type Item.t list

File "src/order-confirmation/DiscountTests.re", lines 15-19, characters 32-11:
15 | ................................[|
16 |            Hotdog,
17 |            Sandwich(Ham),
18 |            Sandwich(Turducken),
19 |          |]..
Error: This expression has type 'a array
       but an expression was expected of type Item.t list

It’s simple to fix—just change the delimiters from [||] to []:

test("0 burgers, no discount", () =>
  expect
  |> equal(
       Discount.getFreeBurger([Hotdog, Sandwich(Ham), Sandwich(Turducken)]),
       None,
     )
);

test("0 burgers, no discount", () =>
  expect
  |> equal(
       Discount.getFreeBurger([Hotdog, Sandwich(Ham), Sandwich(Turducken)]),
       None,
     )
);

The “Input array isn’t changed” test can simply be deleted, because lists are immutable and therefore Discount.getBurger can’t change its input list.

Refactor Discount.getHalfOff ​

Let’s now refactor Discount.getHalfOff to use lists:

/** Buy 1+ burger with 1+ of every topping, get half off */
let getHalfOff = (items: list(Item.t)) => {
  let meetsCondition =
    items
    |> List.exists(
         fun
         | Item.Burger({lettuce: true, tomatoes: true, onions, cheese, bacon})
             when onions > 0 && cheese > 0 && bacon > 0 =>
           true
         | Burger(_)
         | Sandwich(_)
         | Hotdog => false,
       );

  switch (meetsCondition) {
  | false => None
  | true =>
    let total =
      items
      |> List.fold_left((total, item) => total +. Item.toPrice(item), 0.0);
    Some(total /. 2.0);
  };
};

/** Buy 1+ burger with 1+ of every topping, get half off */
let getHalfOff = (items: list(Item.t)) => {
  let meetsCondition =
    items
    |> List.exists(
         fun
         | Item.Burger({lettuce: true, tomatoes: true, onions, cheese, bacon})
             when onions > 0 && cheese > 0 && bacon > 0 =>
           true
         | Burger(_)
         | Sandwich(_)
         | Hotdog => false,
       );

  switch (meetsCondition) {
  | false => None
  | true =>
    let total =
      items
      |> List.fold_left((total, item) => total +. Item.toPrice(item), 0.0);
    Some(total /. 2.0);
  };
};

Again, we swap out array functions for list functions:

• Js.Array.some → List.exists. Note that this is one of several functions in List that have different names than their counterparts in Js.Array.
• Js.Array.reduce → List.fold_left. Despite its name, fold_left^[1] has the same meaning as reduce.

Remember to fix the Discount.getHalfOff tests inside DiscountTests, and then all your code should be compiling once more.

ListLabels module ​

The call to List.fold_left is not as readable as the previous version using Js.Array.reduce, but its readability can be improved by instead using ListLabels.fold_left:

let total =
  items
  |> List.fold_left((total, item) => total +. Item.toPrice(item), 0.0); 
  |> ListLabels.fold_left(~init=0.0, ~f=(total, item) => 
           total +. Item.toPrice(item) 
         ); 
Some(total /. 2.0);

let total =
  items
  |> List.fold_left((total, item) => total +. Item.toPrice(item), 0.0); 
  |> ListLabels.fold_left(~init=0.0, ~f=(total, item) => 
           total +. Item.toPrice(item) 
         ); 
Some(total /. 2.0);

The ListLabels module has all the functions found in List, but many of them take labeled arguments instead of positional arguments.

Refactor Order component ​

Because we’ve gone all in on lists, we have to migrate the component modules as well. Next up is Order. Start off by changing the type of Order.t from array(Item.t) to list(Item.t), then refactor Order.make accordingly:

[@react.component]
let make = (~items: t) => {
  let total =
    items
    |> ListLabels.fold_left(~init=0., ~f=(acc, order) =>
         acc +. Item.toPrice(order)
       );

  <table className=css##order>
    <tbody>
      {items
       |> List.mapi((index, item) =>
            <OrderItem key={"item-" ++ string_of_int(index)} item />
          )
       |> Stdlib.Array.of_list
       |> React.array}
      <tr className=css##total>
        <td> {React.string("Total")} </td>
        <td> {total |> Format.currency} </td>
      </tr>
    </tbody>
  </table>;
};

[@react.component]
let make = (~items: t) => {
  let total =
    items
    |> ListLabels.fold_left(~init=0., ~f=(acc, order) =>
         acc +. Item.toPrice(order)
       );

  <table className=css##order>
    <tbody>
      {items
       |> List.mapi((index, item) =>
            <OrderItem key={"item-" ++ string_of_int(index)} item />
          )
       |> Stdlib.Array.of_list
       |> React.array}
      <tr className=css##total>
        <td> {React.string("Total")} </td>
        <td> {total |> Format.currency} </td>
      </tr>
    </tbody>
  </table>;
};

Again, we’re mostly just replacing array functions with list functions:

• Js.Array.reduce → ListLabels.fold_left
• Js.Array.mapi → List.mapi. Note that the order of the callback arguments has been reversed. For Js.Array.mapi it’s (item, index), but for List.mapi it’s (index, item).
• We have to add a call to Stdlib.Array.of_list in between the calls to List.mapi and React.array to convert the list to an array. Whenever we want to render a list of React.elements, we must first convert it to an array of React.elements. To understand why, recall that a list is just an object in the JS runtime, and React cannot directly render objects.

Because Stdlib is automatically opened, normally we can just call Array.of_list, but we have to use the full name Stdlib.Array.of_list because our custom Array module takes precedence^[2].

To get all your code compiling again, you must also fix the code in Index—but all you have to do in there is change the array delimiters ([||]) to list delimiters ([]).

List.nth_opt ​

If we peruse the List module a bit, we’ll find a function that can simplify the logic in Discount.getFreeBurger: List.nth. It takes an index n that returns the n-th element of a list. However, from previous experience, we don’t want to use unsafe functions like this. Fortunately, there’s a similar List.nth_opt function that does the same thing but is safer because it returns option instead of raising an exception. Let’s refactor Discount.getFreeBurger to use it:

let getFreeBurger = (items: list(Item.t)) => {
  items
  |> List.filter(item =>
       switch (item) {
       | Item.Burger(_) => true
       | Sandwich(_)
       | Hotdog => false
       }
     )
  |> List.map(Item.toPrice)
  |> List.sort((x, y) => - compare(x, y))
  |> List.nth_opt(1);
};

let getFreeBurger = (items: list(Item.t)) => {
  items
  |> List.filter(item =>
       switch (item) {
       | Item.Burger(_) => true
       | Sandwich(_)
       | Hotdog => false
       }
     )
  |> List.map(Item.toPrice)
  |> List.sort((x, y) => - compare(x, y))
  |> List.nth_opt(1);
};

By using List.nth_opt, we can simplify the function to a single expression. However, we get a compilation error:

File "docs/order-confirmation/Discount.re", line 61, characters 18-19:
61 |   |> List.nth_opt(1);
                       ^
Error: This expression has type int but an expression was expected of type
         'a list

File "docs/order-confirmation/Discount.re", line 61, characters 18-19:
61 |   |> List.nth_opt(1);
                       ^
Error: This expression has type int but an expression was expected of type
         'a list

Placeholder operator ​

This is because the type signature of List.nth_opt is

list('a) => int => option('a)

list('a) => int => option('a)

That is, it accepts the list as the first argument, not the last. Recall that the pipe last operator (|>) pipes values into the last argument of a function. However, there’s a way to override the placement of the argument:

|> List.nth_opt(_, 1)

|> List.nth_opt(_, 1)

Do not confuse the _ here for wildcard, here it’s a placeholder for where the argument should go. When we put _ in the first argument position, it overrides the default behavior of the pipe last operator. Run npm run test to confirm that Discount.getFreeBurger works the same as before.

List.nth_opt is unsafe ​

The problem with using List.nth_opt is that it can still raise an Invalid_argument exception if the value of n is negative. You can confirm this by hovering over nth_opt and reading the popup or read its documentation. While this is unlikely to cause a problem inside Discount.getFreeBurger, it’s best to avoid unsafe functions except in special circumstances, for example if a function needs to be as fast as possible. Of course, it’s possible to implement a completely safe version of nth_opt, which is an exercise at the end of this chapter.

Mazel tov! You’ve implemented the burger discounts in a way that is more maintainable, and you’ve also learned a lot about lists along the way. In the next chapter, we’ll finally use the discount logic to reduce the final price of an order.

Overview ​

• Lists are immutable
• You can pattern match on a whole list, even if you don’t know its length
• Uses of list spread syntax (...):
  • Create new lists by prepending elements to existing lists
  • Pattern match on the tail of a list
• The delimiters for list literals are []
• The List module contains most of the functions you’ll need for dealing with lists
• The ListLabels module contains the same functions as in List, but they have labeled arguments instead of positional arguments
• The names of equivalent functions in List and Js.Array might not match
• The runtime representation of lists:
  • Empty list → 0
  • Nonempty list → a JavaScript object with the fields hd (for head) and tl (for tail)
• Documentation comments:
  • Show up in editor hover popups and generated documentation pages
  • Can be attached to functions, modules, types, and variables
• The placeholder operator (_) can be used to override the position of the piped argument when using the pipe last operator

Exercises ​

1. There are a couple ways to improve Discount.getFreeBurger:

• Instead of StdLib.compare, use a type-specific compare function to make the code less brittle. Examples of type-specific compare functions are Bool.compare and String.compare.
• Use List.filter_map in place of List.filter and List.map.

/** Buy 2 burgers, get 1 free */
let getFreeBurger = (items: list(Item.t)) => {
  let prices =
    items
    |> List.filter_map(item =>
         switch (item) {
         | Item.Burger(burger) => Some(Item.Burger.toPrice(burger))
         | Sandwich(_)
         | Hotdog => None
         }
       )
    |> List.sort((x, y) => - Float.compare(x, y));

  switch (prices) {
  | []
  | [_] => None
  | [_, cheaperPrice, ..._] => Some(cheaperPrice)
  };
};

/** Buy 2 burgers, get 1 free */
let getFreeBurger = (items: list(Item.t)) => {
  let prices =
    items
    |> List.filter_map(item =>
         switch (item) {
         | Item.Burger(burger) => Some(Item.Burger.toPrice(burger))
         | Sandwich(_)
         | Hotdog => None
         }
       )
    |> List.sort((x, y) => - Float.compare(x, y));

  switch (prices) {
  | []
  | [_] => None
  | [_, cheaperPrice, ..._] => Some(cheaperPrice)
  };
};

2. Add a ListSafe.nth function which safely returns the nth element of a list encased in Some. If the nth element doesn’t exist, return None. Make sure the function can be used with the pipe last operator without the use of the placeholder operator. Refactor Discount.getFreeBurger to use your new function.

/** Return the nth element encased in Some; if it doesn't exist, return None */
let nth = (n, list) => n < 0 ? None : List.nth_opt(list, n);

/** Return the nth element encased in Some; if it doesn't exist, return None */
let nth = (n, list) => n < 0 ? None : List.nth_opt(list, n);

let getFreeBurger = (items: list(Item.t)) => {
  items
  |> List.filter(item =>
       switch (item) {
       | Item.Burger(_) => true
       | Sandwich(_)
       | Hotdog => false
       }
     )
  |> List.map(Item.toPrice)
  |> List.sort((x, y) => - Float.compare(x, y))
  |> ListSafe.nth(1);
};

let getFreeBurger = (items: list(Item.t)) => {
  items
  |> List.filter(item =>
       switch (item) {
       | Item.Burger(_) => true
       | Sandwich(_)
       | Hotdog => false
       }
     )
  |> List.map(Item.toPrice)
  |> List.sort((x, y) => - Float.compare(x, y))
  |> ListSafe.nth(1);
};

3. Update the logic of Discount.getFreeBurger so that for every pair of burgers purchased, one of them is free. Order the burgers by price (descending), and then choose every other burger (starting from the second burger) to be free. Add this new test to DiscountTests and make sure it passes:

test("7 burgers, return Some(46.75)", () =>
  expect
  |> equal(
       Discount.getFreeBurgers([
         Burger(burger), // 15
         Hotdog,
         Burger({...burger, cheese: 5}), // 15.50
         Sandwich(Unicorn),
         Burger({...burger, bacon: 4}), // 17.00
         Burger({...burger, tomatoes: true, cheese: 1}), // 15.15
         Sandwich(Ham),
         Burger({...burger, bacon: 2}), // 16.00
         Burger({...burger, onions: 6}), // 16.20
         Sandwich(Portabello),
         Burger({...burger, tomatoes: true}) // 15.05
       ]),
       Some(46.75),
     )
);

test("7 burgers, return Some(46.75)", () =>
  expect
  |> equal(
       Discount.getFreeBurgers([
         Burger(burger), // 15
         Hotdog,
         Burger({...burger, cheese: 5}), // 15.50
         Sandwich(Unicorn),
         Burger({...burger, bacon: 4}), // 17.00
         Burger({...burger, tomatoes: true, cheese: 1}), // 15.15
         Sandwich(Ham),
         Burger({...burger, bacon: 2}), // 16.00
         Burger({...burger, onions: 6}), // 16.20
         Sandwich(Portabello),
         Burger({...burger, tomatoes: true}) // 15.05
       ]),
       Some(46.75),
     )
);

/** Buy n burgers, get n/2 burgers free */
let getFreeBurgers = (items: list(Item.t)) => {
  let prices =
    items
    |> List.filter_map(item =>
         switch (item) {
         | Item.Burger(burger) => Some(Item.Burger.toPrice(burger))
         | Sandwich(_)
         | Hotdog => None
         }
       );

  switch (prices) {
  | []
  | [_] => None
  | prices =>
    let result =
      prices
      |> List.sort((x, y) => - Float.compare(x, y))
      |> List.filteri((index, _) => index mod 2 == 1)
      |> List.fold_left((+.), 0.0);
    Some(result);
  };
};

/** Buy n burgers, get n/2 burgers free */
let getFreeBurgers = (items: list(Item.t)) => {
  let prices =
    items
    |> List.filter_map(item =>
         switch (item) {
         | Item.Burger(burger) => Some(Item.Burger.toPrice(burger))
         | Sandwich(_)
         | Hotdog => None
         }
       );

  switch (prices) {
  | []
  | [_] => None
  | prices =>
    let result =
      prices
      |> List.sort((x, y) => - Float.compare(x, y))
      |> List.filteri((index, _) => index mod 2 == 1)
      |> List.fold_left((+.), 0.0);
    Some(result);
  };
};

View source code and demo for this chapter.