DEV Community

loading...

Converting “while” loops to ReScript: use recursion

John Jackson
I’m probably riding my bicycle or coding.
Updated on ・6 min read

This article was originally written with ReasonML and ReasonReact. I updated it in May 2021 to use ReScript.

I recently rewrote my chess tournament app from React to ReasonReact ReScript-React. One area that left me bewildered at first was the imperative while loop. Sometimes, you just need to repeat a block of code indefinitely until a condition is reached. But although imperative loops are the go-to tool for a lot of us, it turns out that are actually great (even better?) functional alternatives.

If you’re familiar with ReScript, you may recognize this page from their docs: Loops. In summary, ReScript support these loops, but they aren’t pretty. To save you a click, here’s their code sample:

Random.self_init()

let break = ref(false)

while !break.contents {
  if Random.int(10) === 3 {
    break := true
  } else {
    print_endline("hello")
  }
}
Enter fullscreen mode Exit fullscreen mode

As you can see, ReScript doesn’t support break statements, and thank goodness! Being able to arbitrarily break out of any loop at any point drastically increases your code’s complexity. We can, however, awkwardly emulate them with a mutable ref value. (Values are immutable, but ref and its := syntax are just sugar for accessing a mutable content field.)

A real-world example.

I needed to solve a problem for my app: In a chess tournament, you need to rank players by first, second, third, etc (duh), but this is surprisingly difficult. A typical tournament ends up with a lot of tied scores, so scores alone aren’t sufficient. USCF and FIDE have crafted several tie-breaking methods to solve the problem. For example, you may use someone’s cumulative (running) score to break ties, or you may use who played as black more times. There are a lot of methods, and some of them are complex. One method isn’t usually sufficient, so a tournament will use several, each with a priority relative to the others. There’s no decreed standard for which ones to use, or in which order, so a tournament director is free to pick what they want.

Whether your tournament has big cash prizes or is just something you’re doing for fun at your local library, you want to be sure that your tiebreak methods are clear to the participants and are accurately calculated.

My solution, while version

Each player’s score information is defined in a record of this type:

type scores = {
  id: string,
  score: float,
  tieBreaks: list<(tieBreak, float)>,
}
Enter fullscreen mode Exit fullscreen mode

The tieBreaks field is an associative list, which can be used like a Map object except simpler for cases like this. It maps each tiebreak-method to the result. (In this code, the results have already been calculated in a previous function.)

The tieBreak type used in that list is defined as this:

type tieBreak =
  | Median
  | Solkoff
  | Cumulative
  | CumulativeOfOpposition
  | MostBlack
Enter fullscreen mode Exit fullscreen mode

(As chess aficionados may notice, I haven’t implemented all the methods.)

If I have a list of player scores, I need to sort them to find out who earned first-place. And to sort them, I need a comparator function. That function has to look through each items in the tieBreaks field, which can be any size, until it finds a comparison or runs out of items. Here’s what I used at first:

let standingsSorter = (tieBreaks: array<tieBreak>, a: scores, b: scores) => {
  let result = ref(0)
  let tieBreakIndex = ref(0)
  let break = ref(false)
  while result.contents === 0 && !break.contents {
    switch tieBreaks->Belt.Array.get(tieBreakIndex.contents) {
    | None => break := true
    | Some(tieBreak) =>
      let getTieBreak = Belt.List.getAssoc(_, tieBreak, \"==")
      /* a and b are switched for ascending order */
      switch compare(b.score, a.score) {
      | 0 =>
        switch (getTieBreak(b.tieBreaks), getTieBreak(a.tieBreaks)) {
        | (Some(tb_b), Some(tb_a)) =>
          /* a and b are switched for ascending order */
          switch compare(tb_b, tb_a) {
          | 0 => tieBreakIndex := tieBreakIndex.contents + 1
          | x => result := x
          }
        | (None, _)
        | (_, None) => ()
        }
      | x => result := x
      }
    }
  }
  result.contents
}
Enter fullscreen mode Exit fullscreen mode

The tieBreaks array, passed as the first argument, tells the comparator function which method to check for and in what order. For example:

standingsSorter([Median, Cumulative, MostBlack]);
Enter fullscreen mode Exit fullscreen mode

Will return a function that compares median scores first, then cumulative scores second, and finally most-black scores if the others are tied.

I would sort them with this code:

listOfScores->Belt.List.sort(standingsSorter(methods))
Enter fullscreen mode Exit fullscreen mode

It works, but could it be better? Is it easy to read? Would it be easy to refactor? I thought I could improve it.

My solution, recursive version!

It’s possible to achieve the exact same result without any imperative loop at all. To understand how, think of each block of code as a function that returns a value. So instead of having our while block put its return value inside a mutable ref variable, we need to make it return that value like a normal function, without side-effects. But, you may notice, a while loop will continue indefinitely until a condition is reached, and functions typically are executed a set number of times. The key here is to use recursion.

ReScript functions aren’t recursive by default. First, we have to mark them as rec, which enables us to execute the function inside itself. Compared to a while loop, the logic is inverted: while loops will repeat until a break or a condition will tell them to stop; recursive functions will return their value unless a condition tells them to execute the function again.

Here’s version 2 of my code. Note the tieBreaksCompare function defined inside the main function

let standingsSorter = (tieBreaks: list<tieBreak>, a: scores, b: scores) => {
  let rec tieBreaksCompare = tieBreaks =>
    switch tieBreaks {
    | list{} => 0
    | list{tieBreak, ...rest} =>
      let getTieBreak = Belt.List.getAssoc(_, tieBreak, \"==")
      switch (getTieBreak(a.tieBreaks), getTieBreak(b.tieBreaks)) {
      | (None, _)
      | (_, None) =>
        tieBreaksCompare(rest)
      | (Some(tb_a), Some(tb_b)) =>
        /* a and b are switched for ascending order */
        switch compare(tb_b, tb_a) {
        | 0 => tieBreaksCompare(rest)
        | x => x
        }
      }
    }
  /* a and b are switched for ascending order */
  switch compare(b.score, a.score) {
  | 0 => tieBreaksCompare(tieBreaks)
  | x => x
  }
}
Enter fullscreen mode Exit fullscreen mode

As you can tell, a lot of the logic hasn’t changed. We’re still comparing the same things, and the end result is the same. But there are no more refs! The logic, at least line-by-line, has been simplified because there are fewer moving parts to deal with.

You’ll also notice that the input tiebreak array has been changed to a list, which is better for pattern-matching. Instead of having to keep track of which index we’re currently using, looking up the index’s value, and incrementing the index for the next loop, we simply destructure the list at each step.

This is what people mean when they talk about the “expressiveness” of ReScript. You don’t need to chain conditionals together like while(result^ === 0 && ! break^) or do lots of array index look-ups, because that logic is built into the language. The surface area for bugs is drastically reduced!

If you’re skeptical of how well the recursive-function style replaces imperative-loop style, here’s the JavaScript output after we compile our Rescript function:

function standingsSorter(tieBreaks, a, b) {
  var x = Caml.caml_float_compare(b.score, a.score);
  if (x !== 0) {
    return x;
  } else {
    var _tieBreaks = tieBreaks;
    while(true) {
      var tieBreaks$1 = _tieBreaks;
      if (!tieBreaks$1) {
        return 0;
      }
      var rest = tieBreaks$1.tl;
      var tieBreak = tieBreaks$1.hd;
      var getTieBreak = (function(tieBreak){
      return function getTieBreak(__x) {
        return Belt_List.getAssoc(__x, tieBreak, (function (prim0, prim1) {
                      return prim0 === prim1;
                    }));
      }
      }(tieBreak));
      var match = getTieBreak(a.tieBreaks);
      var match$1 = getTieBreak(b.tieBreaks);
      if (match !== undefined) {
        if (match$1 !== undefined) {
          var x$1 = Caml.caml_float_compare(match$1, match);
          if (x$1 !== 0) {
            return x$1;
          }
          _tieBreaks = rest;
          continue ;
        }
        _tieBreaks = rest;
        continue ;
      }
      _tieBreaks = rest;
      continue ;
    };
  }
}
Enter fullscreen mode Exit fullscreen mode

Notice what’s on line 7? A while loop! As far as the computer is concerned, recursive functions are exactly the same as while. In fact, our tieBreaksCompare function isn’t present at all in the output. It’s been transformed into the body of the loop.

Final thoughts

I may be biased towards functional, declarative programming, but I’m not trying to say we should never use imperative loops. Just like the ReScript docs say, some algorithms work better in one style and some work better in another.

That said, I know there are a lot of people who have only ever used imperative code before, and they may not even be aware of how to write declarative loops efficiently. (This was me just a few months ago!) Fully understanding every alternative can enable you to write much better code.

If you’re interested in viewing the rest of my app’s code to see exactly how I implemented this logic, you can view it on GitHub here. Here’s a link to the function referenced in this article.

Discussion (0)