DEV Community: J David Eisenberg

Do Arrays in Java Violate “Call by Value”?

J David Eisenberg — Wed, 23 Mar 2022 16:28:13 +0000

“Any headline that ends in a question mark can be answered by the word ‘no’.”
-- Betteridge’s Law of Headlines

When you first learned about methods in Java, you might have read something like “arguments are always passed to parameters by value.” This means that a parameter is always a copy of the argument. You can change the value of the parameter all you want, and the original argument will remain unaffected. In this code:

public class ByValue1 {
    public static void printCube(int n) {
        n = n * n * n;
        System.out.println("The cube is " + n);
    }

    public static void main(String[] args) {
        int n = 12;
        System.out.println("Before call, n is " + n);
        printCube(n);
        System.out.println("After call, n is " + n);
    }
}

The output shows that n in main() remains unchanged:

Before call, n is 12
The cube is 1728
After call, n is 12

This is a good thing; imagine calling printCube(3); you certainly wouldn’t want Java to change the literal 3 to 27!

Further along in your adventures with Java, you encountered arrays, and may have seen a program like this:

import java.util.Arrays;

public class ByValue2 {
    public static void cubeArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            arr[i] = arr[i] * arr[i] * arr[i];
        }
    }

    public static void main(String[] args) {
        int [] data = {10, 2, 4};
        System.out.println("Before call, data is " +
           Arrays.toString(data));
        cubeArray(data);
        System.out.println("After call, data is " +
            Arrays.toString(data));
    }
}

When you run this program, you get this output:

Before call, data is [10, 2, 4]
After call, data is [1000, 8, 64]

What’s going on here? The array contents have changed! Is this an exception to “always call by value“? No, it isn’t. The key point here is that arrays are references. Here’s what a memory diagram looks like when we enter the cubeArray method:

When doing the multplication arr[i] * arr[i] * arr[i], Java is changing element i in the memory that arr refers to; it is not changing arr itself. We can prove this by printing out the reference, which will show the memory address of the arrays:

import java.util.Arrays;

public class ByValue3 {
    public static void cubeArray(int[] arr) {
        System.out.println("At start of cubeArray, arr is "
            + arr);
        for (int i = 0; i < arr.length; i++) {
            arr[i] = arr[i] * arr[i] * arr[i];
        }
        System.out.println("At end of cubeArray, arr is "
            + arr);
    }

    public static void main(String[] args) {
        int [] data = {10, 2, 4};
        System.out.println("Before call, data is " +
            Arrays.toString(data) + " reference " + data);
        cubeArray(data);
        System.out.println("After call, data is " +
            Arrays.toString(data) + " reference " + data);
    }
}

When you print an array with System.out.println, you will get something like [I@764c12b6, which means you have an array ([) of integers (I) at memory location 764c12b6 (@764c12b6). Running the program shows that the references have never changed, but the referred-to array has:

Before call, data is [10, 2, 4] reference [I@764c12b6
At start of cubeArray, arr is [I@764c12b6
At end of cubeArray, arr is [I@764c12b6
After call, data is [1000, 8, 64] reference [I@764c12b6

So, in fact, this program doesn’t settle the question of call by value one way or the other, since nothing here has changed the reference arr itself. Let’s put that to the test by doing something that will change arr—we’ll set arr to refer to a brand new array:

public class ByValue4 {
    public static void cubeArray(int[] arr) {
        System.out.println("At start of cubeArray, arr is "
            + arr);
        for (int i = 0; i < arr.length; i++) {
            arr[i] = arr[i] * arr[i] * arr[i];
        }
        // make arr refer to a different area of memory
        arr = new int[4]; 
        System.out.println("At end of cubeArray, arr is "
            + arr);
    }

    public static void main(String[] args) {
        int [] data = {10, 2, 4};
        System.out.println("Before call, data is " +
            Arrays.toString(data) + " reference " + data);
        cubeArray(data);
        System.out.println("After call, data is " +
            Arrays.toString(data) + " reference " + data);
    }
}

Here’s the memory diagram just before we leave cubeArray():

If call by value really works everywhere, the reference to data in main() should not change. Let’s see the output:

Before call, data is [10, 2, 4] reference [I@764c12b6
At start of cubeArray, arr is [I@764c12b6
At end of cubeArray, arr is [I@4e0e2f2a
After call, data is [1000, 8, 64] reference [I@764c12b6

The third line of the output shows that we changed the arr reference (the parameter) in the cubeArray() method, but the fourth line shows that the original data reference in main() was not affected. The reference is, indeed, passed by value.

Thus, the answer to the article headline: Do Arrays in Java Violate “Call by Value”? The answer is “no.“ Java is always call by value.

The Development Process: Printing a Quadratic in Java

J David Eisenberg — Sun, 27 Feb 2022 03:18:18 +0000

I teach a beginning Computer Science course at a local community college, and we had just written a Java program that asked the user for the coefficients a, b, and c of a quadratic equation and then used the quadratic formula $\pm \sqrt{b^2 - 4ac}} \over {2a}}$ to solve the equation.

At that point, I said, “It would be really nice if we printed out the equation being solved,” and started writing the code. Here’s what happened in the development process.

The First Attempt

I started by adding this code directly in main():

System.out.printf("The equation is %.3fx^2 + %.3fx + %.3f = 0\n",
    a, b, c);

When a is 7.5, b is -3, and c is 2.4, that produced

7.500x^2 + -3.00x + 2.400

The First Improvement

That worked, but having the + and - signs next to each other was a little bit ugly. I wanted to do better, so I split printing the equation into a separate method. I thought, “Oh, this method won’t be too difficult to write.” It turns out that doing an OK job of it is fairly easy. Doing it really well is quite a bit more complicated.

We did some quick planning out loud in class, and came up with the first version of the printFormula() method. Instead of always printing out a plus sign to separate the b and c coefficients, it prints the sign explicitly and then the number without a sign by making sure the value is always positive:

public static void printFormula(double a, double b, double c) {
    System.out.printf("%.3fx^2", a);

    /* Check b to see if it's + or - */
    if (b < 0) {
        System.out.printf(" - %.3fx", -b); // -b to avoid two minus signs in a row
    } else {
        System.out.printf(" + %.3fx", b);
    }

    if (c < 0) {
        System.out.printf(" - %.3f", -c);
    } else {
        System.out.printf(" + %.3f", c);
    }
}

Here are some results for various values of a, b, and c:

a	b	c	prints
7.5	-3	2.4	`7.500x^2 - 3.000x + 2.400`
-4.2	5	3	`-4.200x^2 + 5.000x - 3.000`
1	0	1	`1.000x^2 + 0.000x – 1.000`
-1	1	0	`-1.000x^2 + 1.000x + 0.000`

The first two equations look decent, but the last two aren’t handling coefficients of -1, 1, and 0 very well. That’s to be expected, as the code was the result of a very short amount of planning near the end of the class session.

I wrote the rest of the code you’ll see in this article at home, as I had promised the class I would work on it over the weekend.

Thinking Things Through Thoroughly

It would be better if the program printed the equations without all those unnecessary decimal places:

7.5x^2 – 3x + 2.4
-4.2x^2 + 5x – 3
x^2 – 1
-x^2 + x

To make this happen, we need to do a very careful analysis of what to print for each of the coefficients a, b, and c when the coefficient is -1, 0, 1, other positive numbers, and other negative numbers. The case of zero is the same for all the coefficients—don’t print anything at all. Here's the rest of the analysis, with commas separating the items we have to print:

Coefficient Value	a	b	c
1	"x^2"	" + x"	" + 1"
-1	"-x^2"	" - x"	" - 1"
other positive	a, "x^2"	" + ", b, "x"	" + ", c
other negative	"-", (-a), "x^2"	" - ", (-b), "x"	" - ", (-c)

We can handle the problem of “too many digits after the decimal point” by using System.out.print() instead of System.out.printf() because System.out.print() uses only as many decimal places as needed.

Here’s the code that results from using this new plan. Also, we’re printing the equation, not the formula, so let’s change the method name to be accurate:

public static void printEquation(double a, double b, double c)  {
    /* Handle coefficient for a */
    if (a == -1) {
        System.out.print("-x^2");
    } else if (a == 1) {
        System.out.print("x^2");
    } else if (a < 0) {
        System.out.print("-" + (-a) + "x^2");
    } else if (a > 0) {
        System.out.print(a + "x^2");
    }

    /* Now output coefficient b */
    if (b == -1) {
        System.out.print(" - x");
    } else if (b == 1) {
        System.out.print(" + x");
    } else if (b < 0) {
        System.out.print(" - " + (-b) + "x");
    } else if (b > 0) {
        System.out.print(" + " + b + "x");
    }

    /* And coefficient c */
    if (c == -1) {
        System.out.print(" - 1");
    } else if (c == 1) {
        System.out.print(" + 1");
    } else if (c < 0) {
        System.out.print(" - " + (-c));
    } else if (c > 0) {
        System.out.print(" + " + c );
    }
}

Now the output looks much better for our examples:

a	b	c	prints
7.5	-3	2.4	`7.5x^2 - 3.0x + 2.4`
-4.2	5	3	`4.2x^2 + 5.0x - 3.0`
1	0	1	`x^2 – 1`
-1	1	0	`-x^2 + x`

Do you see that we really had to plan this out in detail? Can you imagine how long it would have taken to come up with this code if we hadn’t laid out all the details first, but instead sat down at the keyboard and tried things out until we got what we wanted? Yes, you might be able to figure this out in your head and keep it all organized, but making the detailed table helped me a lot.

Eliminating Repetition

The code works, but it looks very repetitive. Let’s look for some common factors that we can combine:

There’s not much the cases for a have in common.
For b and c, the minus or plus sign will have a space before and after it no matter what. We could handle the sign as a separate if/else.
If we take the absolute value of the coefficient, then we don’t have to worry about -b vs. b. This is something I would not expect students to recognize—the only reason I recognize it is because I have a lot of experience programming and have seen that the Math.abs() absolute value method often solves this sort of problem.
We could rewrite the first two rows of column c in our analysis table as " - ", 1 and " + ", 1 ; then they are no longer special cases. Again, this is something students might not see right away; it’s something that comes with experience.

I’m also going to change "x^2" to "x²" using the Unicode character \u00b2 so it looks better. If you are on Windows, this may not show up as a superscript 2 if you don’t have your terminal set to use the Unicode character set. I’ve also added an " = 0" at the end of the equation. Now the code looks like this:

public static void printEquation(double a, double b, double c) {
    if (a == -1) {
        System.out.print("-x\u00b2");
    } else if (a == 1) {
        System.out.print("x\u00b2");
    } else if (a < 0) {
        System.out.print("-" + (-a) + "x\u00b2");
    } else if (a > 0) {
        System.out.print(a + "x\u00b2");
    }

    /* Handle sign of b */
    if (b < 0) {
        System.out.print(" - ");
    } else if (b > 0) {
        System.out.print(" + ");
    }

    /* and then its value */
    b = Math.abs(b); // force it to be positive
    if (b == 1) {
        System.out.print("x");
    } else if (b != 0) {
        System.out.print(b + "x");
    }

    if (c < 0) {
        System.out.print(" - " + (-c));
    } else if (c > 0) {
        System.out.print(" + " + c);
    }
    System.out.print(" = 0");
}

Here’s the output from the examples now:

a	b	c	prints
7.5	-3	2.4	`7.5x² - 3.0x + 2.4 = 0`
-4.2	5	3	`4.2x² + 5.0x – 3.0 = 0`
1	0	1	`x² – 1.0 = 0`
-1	1	0	`-x² + x = 0`

Finishing Touches

Let’s evaluate the output of this latest version. The next to last example has 1.0 instead of 1; this happened when we combined the cases for coefficient c. We should fix that. In fact, we should get rid of the “.0” for integral coefficients everywhere.

Unlike the revised code for coefficient c, which is significantly shorter, the code for coefficient b is not only three lines longer than the code it replaced, it’s inconsistent with the code for the other two coefficients, and it’s harder to read.

We didn’t do anything wrong by looking for commonalities and trying to make the code more readable; it just didn’t turn out to be the better thing to do in this case. Oh well, live and learn.

Back to the problem at hand: getting rid of the “.0” for integral coefficients. We can test to see if a double coefficient has an integer value by asking if the number equals the integer part of the number. If so, the fractional part must be zero, and we print the integer part. That won’t have a decimal point in it. If there is a fractional part, we print the number, unchanged.

We need to do this every time we print a coefficient. Here is a place where it is definitely worth our time to write a new method that does this operation, using a cast to convert the double to int if necessary:

public static void printNumber(double number) {
    if (number == (int) number) {
        System.out.print((int) number);
    } else {
        System.out.print(number);
    }
}

We then change the code to use this new method. We also use the shorter, more consistent code we wrote to handle coefficient b. Here’s the method with all those changes:

public static void printEquation(double a, double b, double c) {
    if (a == -1) {
        System.out.print("-x\u00b2");
    } else if (a == 1) {
        System.out.print("x\u00b2");
    } else if (a < 0) {
        System.out.print("-");
        printNumber(-a);
        System.out.print("x\u00b2");
    } else if (a > 0) {
        printNumber(a);
        System.out.print("x\u00b2");
    }

    if (b == -1) {
        System.out.print(" - x");
    } else if (b == 1) {
        System.out.print(" + x");
    } else if (b < 0) {
        System.out.print(" - ");
        printNumber(-b);
        System.out.print("x");
    } else if (b > 0) {
        System.out.print(" + ");
        printNumber(b);
        System.out.print("x");
    }

    if (c < 0) {
        System.out.print(" - ");
        printNumber(-c);
    } else if (c > 0) {
        System.out.print(" + ");
        printNumber(c);
    }

    System.out.print(" = 0");
}

Here are our four example equations:

a	b	c	prints
7.5	-3	2.4	`7.5x² - 3x + 2.4 = 0`
-4.2	5	3	`-4.2x² + 5x - 3 = 0`
1	0	1	`x² - 1 = 0`
-1	1	0	`-x² + x = 0`

Summary

Here are some of the main takeaways from this code:

Start with a first attempt at a solution; the idea is to have something—anything—that works.
You can do a quick analysis of the problem and come up with a better, but still somewhat unsatisfactory, result.
Instead of doing a quick analysis, do a more careful analysis of the problem to produce a much better solution.
Look for ways to eliminate duplicate code. Sometimes, as in the case of coefficient c, what you get is an improvement. Sometimes, as in the case of coefficient b, it isn’t.
Create new methods when you have to do an operation many times. We did this when we wanted to avoid printing decimal places for integer coefficients.
“Wow! For a ‘simple’ problem, that’s a lot of work!” Yes, it is. Getting a program to work well requires a lot of analysis. Then it’s a process of writing code, testing it, seeing that it works, and making improvements—lather, rinse, repeat.

Drawing on a Canvas in ReScript (Part 3)

J David Eisenberg — Fri, 28 Aug 2020 03:27:58 +0000

In the preceding two articles, we set up bs-webapi and extracted the data from the fields in the HTML page. In this article, we’ll complete the task and use the information to draw a polar or Lissajous figure graph.

Moving Things Around

The DomGraphs.res file is getting a bit large. Rather than put everything into one file, create a new Plot.res file in the src directory.

Start it with some module aliases:

module DOM = Webapi.Dom
module Doc = Webapi.Dom.Document
module Elem = Webapi.Dom.Element
module Node = Webapi.Dom.Node
module Evt = Webapi.Dom.Event
module EvtTarget = Webapi.Dom.EventTarget
module Canvas = Webapi.Canvas
module CanvasElement = Webapi.Canvas.CanvasElement
module C2d = Webapi.Canvas.Canvas2d
module Result = Belt.Result

Move the draw function and the initialization from DomGraphs.res into Plot.res. This will require adding the DomGraphs module name in order to reference its functions.

let draw = (_evt) => {
  let formula1 = DomGraphs.getFormula("1")
  let formula2 = DomGraphs.getFormula("2")
  let plotAs = DomGraphs.getRadioValue([("polar", DomGraphs.Polar),
    ("lissajous", DomGraphs.Lissajous)], DomGraphs.Polar)
  switch (formula1, formula2) {
    | (Belt.Result.Ok(f1), Belt.Result.Ok(f2)) => {
        plot(f1, f2, plotAs)
      }
    | (Belt.Result.Error(e1), _) => DOM.Window.alert(e1, DOM.window)
    | (_, Belt.Result.Error(e2)) => DOM.Window.alert(e2, DOM.window)
  }
}

let optButton = Doc.getElementById("draw", DOM.document)
switch (optButton) {
  | Some(button) => {
      EvtTarget.addClickEventListener(draw, Elem.asEventTarget(button))
    }
  | None => DOM.Window.alert("Cannot find button", DOM.window)
}

And then change the <script> element in index.html:

 <script type="text/javascript" src="Plot.bs.js"></script>

As a convenience for keeping function annotations readable, define these types:

type polar = (float, float) // (radius, angle in degrees)
type cartesian = (float, float) // (0.0, 0.0) is at center
type canvasCoord = (float, float) // (0.0, 0.0) is at top left

Since the user interface is in degrees, I decided to keep polar coordinates in degrees and convert to radians only when necessary. Here are utility routines for that purpose:

let radians = (degrees: float): float => {
  degrees *. Js.Math._PI /. 180.0
}

let toCartesian = ((r, theta): polar): cartesian => {
  (r *. cos(radians(theta)), r *. sin(radians(theta)))
}

If you compile the code now, it says that the plot() function hasn’t been written yet. Let’s do that. Start by getting the <canvas>, its drawing context, and its dimensions. Then erase the canvas.

let plot = (f1: DomGraphs.formula, f2: DomGraphs.formula,
 plotAs: DomGraphs.graphType): unit => {

  switch (Doc.getElementById("canvas", DOM.document)) {
    | Some(element) => {
        let context = Canvas.CanvasElement.getContext2d(element);
        let width = float_of_int(Canvas.CanvasElement.width(element));
        let height = float_of_int(Canvas.CanvasElement.height(element));
        let centerX = width /. 2.0;
        let centerY = height /. 2.0;

        C2d.setFillStyle(context, String, "white");
        C2d.fillRect(~x=0.0, ~y=0.0, ~w=width, ~h=height, context);

    | None => ()
  }
}

Next, calculate the amplitude of the wave form; this is the maximum of 1.0 and the sum of the factors in the formulas. This enables us to write a function to convert a coordinate point where (0, 0) is at the center of a graph to the canvas coordinates where (0, 0) is at the upper left of the coordinate system.

let amplitude = Js.Math.max_float(1.0, abs_float(f1.factor) +. abs_float(f2.factor))

let toCanvas = ((x, y): cartesian): canvasCoord => {
  ((centerX /. amplitude) *. x +. centerX,
  (-.centerY /. amplitude) *.y +. centerY)
}

The process of drawing the graph will require evaluating a formula at a given number of degrees:

let evaluate = (f: DomGraphs.formula, angle: float): float => {
  f.factor *. f.fcn(f.theta *. (radians(angle)) +. radians(f.offset))
}

The code for plotting a graph starts at an angle of 0° and evaluates the formulas, combining their results into a point for a polar or Lissajous figure (depending on the user’s choice). The code then repeatedly adds 3° and re-evaluates to find the next point on the curve. The question then becomes: how many times should we iterate in order to ensure a closed figure? For example, if one formula is 3·sin(θ) and the other is 5·cos(θ), then going through 15 times 360° should put the curves “back in sync” with one another. In general, a naïve approach says that the number of degrees we need is 360 times the least common multiple of the theta-factors.

What if you have factors like 3.75 and 7.2? The solution we’ll use is to multiply them factors by 100, find the least common multiple, and divide that result by 100. Here’s the relevant code, with the keyword rec to indicate that the gcd() function is recursive.

let rec gcd = (m: int, n:int): int => {
  if (m == n) {
    m
  } else if (m > n) {
    gcd(m - n, n)
  } else {
    gcd(m, n - m)
  }
}

let lcm = (m: int, n: int): int => {
  (m * n) / gcd(m, n)
}

let lcm_float = (m:float, n:float): float => {
  float_of_int(lcm(int_of_float(m *. 100.0),
    int_of_float(n *. 100.0))) /. 100.0
}

The code for drawing the lines for a polar or Lissajous figure is identical except for the function that determines the (x, y) point to plot, which becomes the parameter to drawLines().

let drawLines = (getXY: (float)=>cartesian): unit => {
  let increment = 3.0
  let limit = 360.0 *. lcm_float(formula1.theta, formula2.theta)

  let rec helper = (d: float) => {
    if (d >= limit) {
      ()
    } else {
      let (x, y) = toCanvas(getXY(d))
      C2d.lineTo(~x = x, ~y = y, context)
      helper(d +. increment)
    }
  }

  let (x, y) = toCanvas(getXY(0.0))
  C2d.setStrokeStyle(context, String, "#000")
  C2d.beginPath(context)
  C2d.moveTo(context, ~x=x, ~y=y)
  helper(increment)
  C2d.closePath(context)
  C2d.stroke(context)

  // draw the plot lines
}

The helper() function is tail-recursive; the recursive call is the last operation when recursion occurs. ReScript will optimize this into a while loop in JavaScript, so there is no danger of a stack overflow from too many recursive calls.

We then need to provide the functions for getting the polar coordinates for polar and Lissajous plots:

let getPolar = (theta): cartesian => {
  let r1 = evaluate(formula1, theta)
  let r2 = evaluate(formula2, theta)
  toCartesian((r1 +. r2, theta))
}

let getLissajous = (theta): cartesian => {
  let r1 = evaluate(formula1, theta)
  let r2 = evaluate(formula2, theta)
  (r1, r2)
}

The call to drawLines() comes at the very end of the plot() function:

drawLines((plotAs == Polar) ? getPolar : getLissajous)

Summary

In this series of articles, you have seen how to set up a ReScript project to use the bs-webapi library, use bs-webapi to extract information from input fields, and how to use that information to draw on a <canvas> element.

The source code for this project is at https://github.com/jdeisenberg/domgraphs; there are three branches: master (part 1), getFieldData (part 2), and plotGraphs (part 3).

You can see the code in action at http://langintro.com/rescript/domgraphs/

Getting Information from the DOM in ReScript (Part 2)

J David Eisenberg — Wed, 26 Aug 2020 21:08:57 +0000

In the preceding article, you learned enough to get started with bs-webapi. Now it’s time to use that library to extract data from the HTML input fields. There’s a lot of things going on here, so take a deep breath, and let’s dive in.

Defining Types

Let’s define a type for a formula that the user will enter. We’ll use a record for this:

type formula = {
  factor: float,
  fcn: trigFcn,
  theta: float,
  offset: float
}

How shall we define this trigFcn type? We could make it a variant type:

type trigFcn = 
  | Sin
  | Cos

But instead, make trigFcn an actual function, so you can directly assign sin or cos to the field.

type trigFcn = (float) => float

type formula = {
  factor: float,
  fcn: trigFcn,
  theta: float,
  offset: float
}

Finally, you need a variant data type for the kind of graph the user wants:

type graphType =
  | Polar
  | Lissajous

Finding the Draw Button

To get access to an element, you must call the getElementById() function, which takes as its arguments the element ID and a DOM document. This function returns an option type—it’s possible that the button doesn’t exist. Important: ReScript’s type checking doesn’t prevent you from having an error. It does require you to handle both the error and non-error cases. Here’s the code for the moment:

let optButton = Webapi.Dom.Document.getElementById("draw", Webapi.Dom.document)
switch (optButton) {
  | Some(button) => ()
  | None => Webapi.Dom.Window.alert("Cannot find button", Webapi.Dom.window)
}

The () is ReScript’s unit value, which is morally equivalent to void in other programming languages. You may have noticed that there’s a lot of repetition of Webapi.Dom. You can eliminate that repetition by putting some module aliases at the beginning of the file:

module DOM = Webapi.Dom  // use all upper case to distinguish from built-in Dom
module Doc = Webapi.Dom.Document
module Elem = Webapi.Dom.Element
module HtmlElem = Webapi.Dom.HtmlElement
module InputElem = Webapi.Dom.HtmlInputElement
module EvtTarget = Webapi.Dom.EventTarget

The code then becomes:

let optButton = Doc.getElementById("drawx", DOM.document)
switch (optButton) {
  | Some(button) => ()
  | None => DOM.Window.alert("Cannot find button", DOM.window)
}

Let’s set a click handler for the button (when it exists) to call a function called draw(). The addClickEventListener function requires an EventTarget, not a generalized Element, so you have to force ReScript to treat it as the correct type:

  | Some(button) => {
      EvtTarget.addClickEventListener(draw, Elem.asEventTarget(button))
    }

You’ll need the draw() function, which takes an event as its parameter. For now, put in a placeholder function. This function must precede its first use.

let draw = (evt) => {
  Js.log(evt);
  Js.log("Button clicked")
}

Open up the web console in your browser, and you’ll see something like this when you click the button:

click { target: button#draw, buttons: 0, clientX: 505, clientY: 230, layerX: 505, layerY: 230 }
Button clicked

Getting a Text Field’s Value

When the user clicks the Draw button, the program needs to go through the form fields and extract the data. Let’s start with the numeric values. Here’s the plan:

If the ID of the field exists, then
- If the text field is empty, use a default value
- Convert to a float. If successful, return that value
- Otherwise, return a “not numeric” error
otherwise, return an “ID not found” error

You cannot use an option here—it either has a Some(value) or None. Instead, you must use Belt.Result, which can return an Ok(value) or Error(otherValue).

You’ll also need to take the generic element from getElementById() and convince ReScript to treat it as an HtmlInputElement:

type numResult = Belt.result.t<float, string>
external unsafeAsHtmlInputElement: Elem.t => InputElem.t = "%identity"

In the preceding code, the first line establishes a type for our result: Ok values are float; Error values are string. The second line is a magic voodoo spell that forces the conversion. You can pass any element to this function, and ReScript will blindly return it as an HtmlInputElement. If you pass something that really isn’t an <input> element, well, that’s on you! That’s why it has unsafe in its name.

Once these are established, you can write a function that takes an element ID and a default value and returns a numResult. Although ReScript would do the correct type inference, I’m now annotating the functions and explicitly giving the parameter and return types to make them clear to me, not to the computer.

let getNumericValue = (id: string, default: float): numResult => {
  let converter = (s: string, default: float): numResult => {
    if (s == "") {
      Belt.Result.Ok(default)
    } else {
      switch (float_of_string(s)) {
        | result => Belt.Result.Ok(result)
        | exception Failure(_) =>
            Belt.Result.Error(s ++ " is not numeric.")
      }
    }
  }
  getInputValue(id, default, converter)
}

Extra bonus: this code shows you one way to handle exceptions in ReScript. You can test this by adding the following code in the draw() function:

  let testNumeric = getNumericValue("factor1", 1.0)
  Js.log(testNumeric)

If you enter a valid number (like 5.3) and a non-numeric (like “blah”) in the first input field and then click the Draw button, you’ll see something like this in the web console:

Object { TAG: 0, _0: 5.3 }
Object { TAG: 1, _0: "blah is not numeric." }

Eliminating Duplication

The next step is to get an entire formula: the factor, function, theta multiplier, and offset. Getting the function shares a lot of code with getting numeric input:

If the ID of the field exists, then
- If the text field is empty, use a default value
- Convert to a trigFcn. If successful, return that value
- Otherwise, return an “unknown function“ error
otherwise, return an “ID not found“ error

Add another convenience type for the result:

type numResult = Belt.Result.t<float, string>
type fcnResult = Belt.Result.t<trigFcn, string>

Do you see a pattern here? This is a perfect place to use a parametric data type, which is similar to generics in other programming language. The following code creates a generalized inputResult type and a getInputValue() function that takes an element id, a default value, and a function that converts a string (the value in the input field) to the appropriate Result type:

let getInputValue = (id: string, default: 'a, f: (string, 'a)=> inputResult<'a>):
  inputResult<'a> => {
  switch (Doc.getElementById(id, DOM.document)) {
    | Some(element) => {
        let s = InputElem.value(unsafeAsHtmlInputElement(element))
        f(s, default)
      }
    | None => Belt.Result.Error("No element" ++ id)
  }
}

This lets you rewrite getNumericValue() as:

let getNumericValue = (id: string, default: float): numResult => {
  let converter = (s: string, default: float): numResult => {
    if (s == "") {
      Belt.Result.Ok(default)
    } else {
      switch (float_of_string(s)) {
        | result => Belt.Result.Ok(result)
        | exception Failure(_) =>
            Belt.Result.Error(s ++ " is not numeric.")
      }
    }
  }
  getInputValue(id, default, converter)
}

The function for getting the trigonometric function then becomes the following. There’s no need for a default value here, as both possibilities are accounted for in the drop-down menu. That’s why there is an underscore in _default, to tell ReScript that you know you won’t be using that variable.

let getFunctionValue = (id: string): fcnResult => {
  let converter = (s: string, _default: trigFcn): fcnResult => {
    if (s == "sin") {
      Belt.Result.Ok(sin)
    } else if (s == "cos") {
      Belt.Result.Ok(cos)
    } else {
      Belt.Result.Error("Unknown trig function " ++ s)
    }
  }
  getInputValue(id, sin, converter);
}

Building a formula

You can now read all the fields to put together a formula variable. Since any of the elements of the formula can fail, you need a Result type for the formula:

type formulaResult = Belt.Result.t<formula, string>

One approach to putting together a formula would be a deeply nested series of switch statements to separate out the Ok and Error conditions for each part of a formula. Normally, instead of a nested switch, you would use Belt.Result.map() and Belt.Result.flatMap() to “pass along” the Ok conditions and stop when you hit an Ok.

Unfortunately, in this case each of the items in the formula is itself a Result, and neither map() nor flatMap() does what you want. However, there’s no law that stops you from writing your own custom function:

let multiMap = (
  rX: Belt.Result.t<'a, 'b>, // this will be our formula
  rY: Belt.Result.t<'c, 'b>, // this is the result of getting an input field
  f: ('c, 'a) => 'a):        // function to insert input value ('c) into formula ('a)
    Belt.Result.t<'a, 'b> => {

  switch (rX, rY) {
    | (Belt.Result.Ok(x), Belt.Result.Ok(y)) =>
        Belt.Result.Ok(f(y, x))
    | (Belt.Result.Ok(_x), Belt.Result.Error(err)) =>
        (Belt.Result.Error(err): Belt.Result.t<'a, 'b>)
    | (err, _) => err
  }
}

Thus, given a formulaResult and an inputResult, the preceding code does this:

If both the formula and input value are Ok, use a function to put the value into the formula.
If the formula is Ok so far, but you have an input error, pass on the input error. The type annotation here is required to extract the error value from an inputResult and repackage it in a formulaResult
If the formula so far has an error, pass it along

Here’s the code for putting together a formula from the fields that end with a given suffix (either "1" or "2"). It uses -> to pass the result of one multiMap() call as the first parameter of the next one.

let getFormula = (suffix: string): Belt.Result.t<formula, string> => {

  // start with a "neutral" formula that is Ok
  let possibleFormula = Belt.Result.Ok(
     {factor: 1.0, fcn: sin, theta: 1.0, offset: 0.0}
  )

  multiMap(possibleFormula, getNumericValue("factor" ++ suffix, 1.0),
    (factor, form) => {...form, factor: factor}) ->
  multiMap(getFunctionValue("fcn" ++ suffix),
    (fcn, formula) => {...formula, fcn: fcn}) ->
  multiMap(getNumericValue("theta" ++ suffix, 1.0),
    (theta, formula) => {...formula, theta: theta}) ->
  multiMap(getNumericValue("offset" ++ suffix, 0.0),
    (offset, formula) => {...formula, offset: offset})
}

Each of the anonymous functions uses the ... spread operator to create a new formula with the given value.

You can test this code by changing draw() as follows. The code doesn’t need any information from the event, so _evt starts with an underscore. Try entering non-numbers in several fields and see what happens.

let draw = (_evt) => {
  let testFormula = getFormula("1")
  Js.log(testFormula)
}

Once you’re satisfied with this, add code to get the selected radio button. The following code takes two parameters. The first is an array of two-tuples giving the radio button values and the corresponding variant data type value. The second parameter is a default value. This code is very laissez-faire; if there is any error, it defaults to a polar graph.

let getRadioValue = (radioButtons: array<(string, 'a)>, default: 'a) => {
  let rec helper = (index: int) => {
    if (index == Belt.Array.length(radioButtons)) {
      default
    } else {
      switch (Doc.getElementById(fst(radioButtons[index]), DOM.document)) {
        | Some(element) => {
            let input = unsafeAsHtmlInputElement(element)
            if (InputElem.checked(input)) {
              snd(radioButtons[index])
            } else {
              helper(index + 1)
            }
          }
        | None => helper(index + 1)
      }
    }
  }
  helper(0)
}

Now you can write the final version of draw() to collect all the form data.

let draw = (_evt) => {
  let formula1 = getFormula("1")
  let formula2 = getFormula("2")
  let plotAs = getRadioValue([("polar", Polar), ("lissajous", Lissajous)], Polar)
  switch (formula1, formula2) {
    | (Belt.Result.Ok(f1), Belt.Result.Ok(f2)) => {
        Js.log2("formula 1:", f1)
        Js.log2("formula 2:", f2)
        Js.log2("plot as: ", plotAs)
      }
    | (Belt.Result.Error(e1), _) => DOM.Window.alert(e1, DOM.window)
    | (_, Belt.Result.Error(e2)) => DOM.Window.alert(e2, DOM.window)
  }
}

There’s a lot of material here. You’ll probably want to look at the code carefully to see what’s going on. (And if you find a way to make it better, let me know.)

In the next and final part of this series, you’ll take the formula information and create the graph.

Manipulating the DOM with ReScript (Part 1)

J David Eisenberg — Tue, 25 Aug 2020 19:15:50 +0000

Sometimes you will want to write a single-page web application, but you’d like to manipulate the DOM directly rather than use a framework like React.

The project we’re going to build will ask for parameters to two equations based on trigonometric functions and then draw a polar or Lissajous figure from those equations.

Setting up

Start by creating a ReScript project, renaming it, and going to its directory:

git clone https://github.com/rescript-lang/new-project
mv new-project domgraphs
cd domgraphs

The src directory contains two files: Demo.res, the ReScript source file, and Demo.bs.js the generated JavaScript. (The bs stands for BuckleScript. BuckleScript has been rebranded as ReScript.) Remove the .bs.js file, and rename the source file:

rm src/Demo.bs.js
mv src/Demo.res src/DomGraphs.res

Next, put the HTML into file src/index.html.

<!DOCTYPE html>
<html>
  <head>
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
    <title>DOM Graphs</title>
    <style type="text/css">
      #canvas {
        width: 450px;
        float: left;
        border: 1px solid black;
        margin: 5px;
      }
    </style>
  </head>
  <body>
    <h1>DOM Graphs</h1>
    <canvas id="canvas" width="400" height="400">
      Your browser does not support the &lt;canvas&gt; element :(
    </canvas>
    <div>
      <p><input type="text" size="3" id="factor1"/>
      <select id="fcn1">
        <option value="sin">sin</option>
        <option value="cos">cos</option>
      </select>
      (
        <input type="text" size="3" id="theta1"/>
        &theta; +
        <input type="text" size="3" id="offset1"/>&deg;
      )</p>

      <p><input type="text" size="3" id="factor2"/>
      <select id="fcn2">
        <option value="sin">sin</option>
        <option value="cos">cos</option>
      </select>
      (
        <input type="text" size="3" id="theta2"/>
        &theta; +
        <input type="text" size="3" id="offset2"/>&deg;
      )</p>

      <p>
        Type of graph:
        <input type="radio" value="polar" name="graphType" id="polar"/>
          <label for="polar">Polar</label>
        <input type="radio" value="polar" name="graphType" id="lissajous"/>
          <label for="lissajous">Lissajous</label>
      </p>

      <p><button id="draw" value="draw">Draw</button></p>
    </div>
    <script type="text/javascript" src="DomGraphs.bs.js"></script>
  </body>
</html>

The <script> element at the end gives the name of the JavaScript file containing the application code, which ReScript will generate from the DomGraphs.res file.

ReScript includes a Dom library for basic manipulation of the DOM, but for more power and convenience, you’ll want to use the bs-webapi library. Put the dependency for bs-webapi into the project’s bs-config.json file:

  "bs-dependencies": [
    "bs-webapi"
  ],

Install bs-platform and bs-webapi:

npm install # installs the ReScript platform
npm install --save bs-webapi

Finally, we need to have a bundler that will take the HTML file and JavaScript generated by the compiler and put it in one nice web application. In this article, I’m using parcel, because it works right out of the box and doesn’t require a lot of configuration. Install it globally so that you don’t need to duplicate it for every project.

npm install --global parcel-bundler

Accessing the DOM

Let’s take a look at some of the modules in bs-webapi that you’ll use frequently, and those that we’ll use in this program.

Webapi
├── Canvas
│   ├── Webapi.Canvas.Canvas2d
├── Dom
│   ├── Webapi.Dom.Attr
│   ├── Webapi.Dom.ChildNode
│   ├── Webapi.Dom.Document
│   ├── Webapi.Dom.Element
│   ├── Webapi.Dom.Event
│   ├── Webapi.Dom.EventTarget
│   ├── Webapi.Dom.HtmlElement
│   ├── Webapi.Dom.HtmlInputElement
│   ├── Webapi.Dom.MouseEvent
│   ├── Webapi.Dom.Node
│   ├── Webapi.Dom.Text
│   └── Webapi.Dom.Window

Let’s do a quick test of the JavaScript Window.alert() function. Replace the code in your DomGraphs.res file with this code:

let testAlert = Webapi.Dom.Window.alert("It works!", Webapi.Dom.window)

The bs-webapi library is set up so that, most of the time, the element you’re working with (in this case, the window we’re using for the alert) is the last argument in the call.

Compile and bundle:

npm run build # or: bsb -make-world
parcel build src/index.html --public-url ./

The parcel command specifies the entry point for the application (src/index.html) and the URL to use when serving the JavaScript—in this case, the same directory as the HTML (--public-url ./). This will locally install the cssnano package. You can specify the --no-minify flag to prevent this local install.

When these steps are complete, you’ll see a file named DomGraphs.bs.js, which is the JavaScript generated by ReScript, and a directory named dist that contains the bundled web app.

$ ls dist
DomGraphs.bs.5acda38d.js  DomGraphs.bs.5acda38d.js.map  index.html

Every time you run parcel, it generates a new number to append to the bundled files based on the content of the files being processed. To avoid getting multiple different .js and .js.map files accumulating in your dist directory, you may want to remove the directory before rebuilding. Here is a bash script to do exactly that:

#!/bin/bash

npm run build # or bsb -make-world
status=$?
if test $status -eq 0
then
  rm -rf dist
  parcel build src/index.html src/*csv --public-url ./
fi

If all has gone well, when you open the dist/index.html file in your browser, you’ll see an alert telling you that It works!

Now that everything is set up, it’s time to start writing the project code.

Type Annotation in ReasonML

J David Eisenberg — Sun, 22 Dec 2019 02:20:17 +0000

One of the most powerful features of ReasonML is its type inference system. In code like this:

let age = 42;
let price = 10.66;
let word = "reason";
let isValid = true;
let hours = [10, 2, 4];
let focalLength = (objDist, imgDist) => {
  (objDist *. imgDist) /. (objDist +. imgDist);
};

ReasonML figures out the type of each of these bindings. If you’re using an editor like Visual Studio Code with the reason-vscode extension, you can see what ReasonML has inferred:

The type inference system does such a good job of figuring out what types you’re using that you can write an entire program without having to specify any types. But type inference is still there, looking over your shoulder and letting you know if you do something wrong, as in line two:

  We've found a bug for you!
  /home/david/annotation/src/Demo.re 2:19-21

  1 │ let age = 42;
  2 │ let total = age + "3";
  3 │ let price = 10.66;
  4 │ let word = "reason";

  This has type:
    string
  But somewhere wanted:
    int

Sometimes, though, there are situations where the type inference system can’t figure out what you need. Sometimes there’s an ambiguous situation (two different record types with the same fields or similar ones in different modules) where type inference makes a choice—but not the one you want. And sometimes you just plain want to do your own type annotation. Here’s how to do it.

Annotating Value Bindings

For bindings to a value, you follow the variable name with a colon and the value’s type. Here are our original value bindings with explicit annotation:

let age: int = 42;
let price: float = 10.66;
let word: string = "reason";
let isValid: bool = true;
let hours: list(int) = [10, 2, 4];

While you can annotate value bindings, almost nobody does this. In most cases, the expression on the right-hand side makes the type sufficiently clear that adding the annotation won’t give you an exponential gain in clarity.

However, many people do annotate function bindings.

Annotating Function Bindings (Method 1)

Function binding annotation follows the same pattern, with the type information between the function name and the equal sign:

Start with a colon
In parentheses, specify the parameter types
Add =>
Specify the return type

Here’s the annotation for the focal length function:

let focalLength: (float, float) => float  =
  (objDist, imgDist) => {
    (objDist *. imgDist) /. (objDist +. imgDist);
  };

Annotating Function Bindings (Method 2)

The preceding method with the type information separate from the parameter list and function body is familiar to people coming from a language like Haskell or Elm.

If you’re coming from a language like Java or TypeScript or Flow, you’re used to seeing type information attached each individual parameter. ReasonML supports that kind of notation as well:

let focalLength = (objDist: float, imgDist: float): float => {
    (objDist *. imgDist) /. (objDist +. imgDist);
  };

Annotating Functions with Labeled Parameters

Consider this un-annotated function to calculate the total price, given a quantity, unit price, and tax as a percent. This function uses labeled parameters, specified with the ~. When you call the function, you need to give the parameter name, but you can give the parameters in any order you like:

let totalPrice = (~qty, ~unitPrice, ~tax) => {
   (float_of_int(qty) *. unitPrice) *. (1.0 +. (tax /. 100.0));
};

let price1 = totalPrice(~qty=5, ~unitPrice=34.95, ~tax=7.5);
let price2 = totalPrice(~unitPrice=15.00, ~tax=5.0, ~qty=12);

When you annotate this function with the type information separated from the function definition (method 1), you need to name the parameters in the same order as in their declaration in the function:

let totalPrice: (~qty: int, ~unitPrice: float, ~tax: float) => float =
  (~qty, ~unitPrice, ~tax) => {
    (float_of_int(qty) *. unitPrice) *. (1.0 +. (tax /. 100.0));
  };

When using parameters-with-their-types (method 2), add the type information exactly as you did with unlabeled parameters.

let totalPrice =  (~qty: int, ~unitPrice: float, ~tax:float): float => {
   (float_of_int(qty) *. unitPrice) *. (1.0 +. (tax /. 100.0));
};

Which Method to Use?

The main advantage of the separate specification (method 1) is that this is the format you use when creating a .rei (ReasonML interface) file. You use .rei files to specify an API for modules that you would like other people to use.

The main advantages of the parameter-with-type specification (method 2) are familiarity and the fact that you don’t have to specify a type for every parameter. If a parameter’s type is too complicated for you to figure out, you can leave it out and let the type inference system take over for you.

From what I’ve seen in code written by others, most people let the inference system do all the work. When they do annotate, they use method 2.

Should You Annotate?

If you’re coming from a programming language where you have to specify types, I recommend that you annotate your ReasonML code as well.

If you’re coming from an untyped language, I recommend that you annotate your code as you’re learning ReasonML. This will get you used to thinking through exactly what kinds of input and output your functions need. Don’t worry about making mistakes—the type inference system will keep you honest!

Please let me know your thoughts in the discussion.

Higher-Order Functions in ReasonML

J David Eisenberg — Wed, 18 Dec 2019 17:35:43 +0000

In a previous post, I developed a recursive function that found the index of the first negative value in a list of quarterly balances:

let debitIndex = (data) => {
  let rec helper = (index) => {
    if (index == Js.Array.length(data)) {
      -1; 
    } else if (data[index] < 0.0) {
      index;
    } else {
      helper(index + 1); 
    }   
  };  

  helper(0);
};

let balances = [|563.22, 457.81, -309.73, 216.45|];
let result = debitIndex(balances);

What if I wanted to find the first value that was 1000.00 or more? Then I’d need to write another function like this:

let goodQuarterIndex = (data) => {
  let rec helper = (index) => {
    if (index == Js.Array.length(data)) {
      -1; 
    } else if (data[index] >= 1000.0) {
      index;
    } else {
      helper(index + 1); 
    }   
  };  

  helper(0);
};

It’s the same as the first function, except for the if test for the data value.

What about finding the first value that’s equal to zero? I’d need to write yet another function that looks exactly the same as the preceding two, except for the if test. There must be a way to write a generic findFirstIndex function that can handle any of these cases without having to duplicate most of the code.

We can do this by writing a higher-order function—a function that takes another function as its argument.

Let’s put the tests for “we found it!” (the only code that’s different) into their own functions that take an item as input and return a true or false value.

let isDebit = (item) => {item < 0.0};
let isGoodQuarter = (item) => {item >= 1000.00};
let isZero = (item) => {item == 0.0};

These functions that return boolean are sometimes called predicate functions .

Then change the recursive function as follows:

let findFirstIndex = (testingFunction, data) => {
  let rec helper = (index) => {
    if (index == Js.Array.length(data)) {
      -1; 
    } else if (testingFunction(data[index])) {
      index;
    } else {
      helper(index + 1);
    }
  };

  helper(0);
};

Now you can find the first negative balance, the first quarter with a good balance, and the first zero-balance quarter with these calls:

let firstDebit = findFirstIndex(isDebit, balances);
let firstGoodQuarter = findFirstIndex(isGoodQuarter, balances);
let firstZero = findFirstIndex(isZero, balances);

When the first call is made, this is what it looks like:

As a result, the call testingFunction(data[index]) will pass balances[index] to the isDebit() function.

The second time we call findFirstIndex, testingFunction(data[index]) will pass balances[index] to the isGoodQuarter() function.

The third time we call findFirstIndex, testingFunction(data[index]) will pass balances[index] to the isZero() function.

This ability to plug in a function as an argument to another function gives you great flexibility and helps you avoid a lot of duplicated code.

Example: Rate of Change

Not all the functions you give to a higher-order function (HOF) need to be predicate functions. Consider this graph of the function f(x) = x^2

In this diagram, you can see that the y value increases more slowly when x is between 0 and 2 than when x is between 4 and 6.

We want to write a function that calculates the rate of change for some function f. If you have two points x1 and x2, the formula for rate of change between those points is (f(x2) – f(x1)) / (x2 – x1).

Here’s the rate of change function:

let rateOfChange = (f, x1, x2) => {
    (f(x2) -. f(x1)) /. (x2 -. x1)
};

We are presuming here that function f returns a floating point value. ReasonML is very strict about not mixing integer and floating values; it’s so strict that it has separate arithmetic operators for each type. To add, subtract, multiply, or divide floating point numbers, you have to follow the operator with a dot.

Now let’s define the x^2 function and find the rates of change:

let xSquared = (x) => {x *. x};

let rate1 = rateOfChange(xSquared, 0.0, 2.0);
let rate2 = rateOfChange(xSquared, 4.0, 6.0);
Js.log2("Rate of change from 0-2 is", rate1); // 2.0
Js.log2("Rate of change from 4-6 is", rate2); // 10.0

It’s possible to find the rate of change for any sort of mathematical function:

let tripleSine = (x) => {sin(3.0 *. x)};
let polynomial = (x) => {
   5.0 *. x ** 3.0 +. 8.0 *. x ** 2.0 +. 4.0 *.x +. 27.0
};

let rate3 = rateOfChange(tripleSine, 0.0, Js.Math._PI /. 4.0);
let rate4 = rateOfChange(polynomial, -3.0, 2.0);
Js.log2("sine from 0-45 degrees:", rate3); // 0.9003...
Js.log2("polynomial from -3 to 2:", rate4); // 31

Anonymous Functions

There’s a way to specify short functions to pass to a HOF right on the spot without having to create a new, named function (as we have done so far). Here’s how we’d do it for the debit problem:

let firstDebit = findFirstIndex( (item) => {item < 0.0}, balances);

The anonymous predicate function is (item) => {item < 0.0}. It’s exactly the same as the right-hand side of the binding starting let isDebit =...

Similarly, we can use an anonymous function for finding rate of change of the function x^3 in the range 0 to 4:

let cubeChange = rateOfChange((x) => {x ** 3.0}, 0.0, 4.0);

Many programmers like to use anonymous functions, and you will see a lot of them as you read other people’s ReasonML code. Should you use them too? My strong suggestion is that you don’t.

Named functions make things easier to read. isDebit is more immediately meaningful than having to parse (item) => {item < 0.0}
As you find bugs or need features, your one-line anonymous function might grow to a multi-line anonymous function. That makes the code more difficult to read, and you tend to lose the big picture. At that point, you will probably pull out the code into a separate function. So why not do it now?
Anonymous functions aren’t reusable. If you need the same function in a different place, you will have to copy it.

That’s my viewpoint; your mileage may vary.

Summary

Higher-order functions (HOFs) are functions that take other functions as arguments. HOFs can also return a function as their value, though we haven’t covered that aspect in this post. HOFs let you reuse code that would otherwise require writing near-duplicated code.

While you might not have need to write HOFs yourself, you will often find yourself using them. For example, when you want to manipulate lists and arrays you’ll use the map(), keep(), and reduce() HOFs. But those three functions are the subject of a future post.

Taming Recursion with Tail Recursion

J David Eisenberg — Tue, 17 Dec 2019 17:33:14 +0000

One of the key concepts used in functional programming (FP) is recursion—the ability of a function to call itself. You may have heard these things:

Recursion is difficult to understand.
Recursion is slow.
Recursion is dangerous because it can lead to a condition called stack overflow.
Many FP languages don’t use loops; they only use recursion.

This may have put you off the idea of using those FP languages or using recursion at all. Fear not; it is possible to tame recursion using a technique called tail recursion. In this article, I’ll be using ReasonML for code examples.

A Typical Example

This is a typical example you will see when people introduce recursion, and, to be honest, it can be a little bit scary.

The first example will be to write a function that finds the sum of squares of an array (a useful thing to calculate in statistical formulas). Here’s how you create an array of integers in ReasonML.

let numbers = [|3, 7, 4|];

Here’s how we solve the problem using recursion. We first consider the simplest possible case, also called the base case. The sum of squares of an empty array is zero. For any other array, we take the square of the first number and add the sum of squares of the rest of the numbers (there’s our recursion). Here’s how we express it in ReasonML.

let rec sumOfSquares = (data) => {
    if (Js.Array.length(data) == 0) {
        0;
    } else {
        data[0] * data[0] + sumOfSquares(Js.Array.sliceFrom(1, data));
    };
};

let result = sumOfSquares(numbers);

Js.log2("The sum of squares is", result);

In ReasonML, we use rec to indicate that we will be calling this function recursively. We’re using two functions from the Js.Array module: length() to find the length of the array. The sliceFrom() function returns the portion of the given array from the index you specify (in our case, index 1) to the end. The call to sliceFrom(1, data) returns an empty list if you give it an array with only one element, and that is exactly what we want.

In ReasonML, if is an expression, not a statement, so we don’t need to assign the result of the if or else branch to a result variable. ReasonML functions take the last expression that the function evaluates as the return value, so no explicit return is necessary.

What’s going on behind the scenes? Let’s see what the function is doing when given the numbers array [|3, 7, 4|].

Square the first number. 3^2 → 9
Add 9 to the sum of squares of the rest of the array: [|7, 4|]. Use recursion to figure that out (recursion #1).
- Square the first number. 7^2 → 49
- Add 49 to the sum of squares of the rest of the array: [|4|]. Use recursion #2 to figure that out.
  - Square the first number. 4^2 → 16
  - Add 16 to the sum of squares of [||]. Use recursion #3 to figure that out.
    - The sum of squares of the empty list is zero.
  - Complete the addition started in recursion #3: 16 + 0 → 16
- Complete the addition started in recursion #2: 49 + 16 → 65
Complete the addition started in recursion #1: 9 + 65 → 74

Ye cats! That looks incredibly complicated. The way this (and most typical introductions to recursion) are written, we have to put our calculation “on hold” until we have evaluated the remaining numbers. That requires us to store our intermediate results somewhere. That “somewhere“ is called the stack, and it has limited size. If we have a large array, we’ll have more intermediate results than the stack can hold, it will overflow, and our program will crash.

Not only do we have to hold off on our calculations, once we get to the base case, we have to climb back up the ladder of additions we’ve been building.

No wonder people flee from the room, shrieking, whenever they see the word “recursion.”

Please Don’t Run Away

Take a deep breath. Say “om.” Now let’s do a complete restart and introduce recursion with...

A Not-scary Example

Let’s use recursion to solve this problem: given an array of numbers, find the index of the first negative value. Here’s our array of quarterly account balances:

let balances = [|563.22, 457.81, -309.73, 216.45|];

We’ll use a function called debitIndex() that takes two parameters: the array to search, and a starting index. Here’s our pseudocode for that function.

To find the first negative value in an array starting at an index number:

Is our current index equal to the array length? If so, we’ve hit the end of the array, and we return -1 to indicate that we haven’t found a negative value.
Is the value at the current index negative? That means we’ve found the debit, and we’ll return the index number.
Otherwise, we’ll find the first negative value in the array starting at the next index number.

Steps 1 and 2 tell us when we can stop looking. These are called the base cases. Step 3 is where the recursion happens—it restates the problem in terms of itself.

Here’s the ReasonML code:

let rec debitIndex = (data, index) => {
   if (index == Js.Array.length(data)) {
      -1;
   } else if (data[index] < 0.0) {
      index;
   } else {
      debitIndex(data, index + 1);
   }
};

let result = debitIndex(balances, 0);
Js.log2("Result is ", result);

ReasonML is very strict about not mixing floating point and integer values. Because the balances array contains floating point numbers, we have to compare to floating point 0.0 rather than the integer value 0.

Now let’s see what happens when we make our call to debitIndex(balances, 0)

The index (0) isn’t equal to the length of the array.
data[0] is 563.22, which is not less than zero.
Do a recursive call with the data array and index 1
- The index (1) isn’t equal to the length of the array.
- data[1] is 457.81, which is not less than zero.
- Do a recursive call with the data array and index 2.
  - The index (2) isn’t equal to the length of the array.
  - data[2] is -309.73, which is less than zero. Return the index (2).

That wasn’t as bad as the first example. We didn’t have to put any calculations on hold. When we hit a base case, we were finished. We didn’t have to climb back up a ladder of nested calls.

What made the difference? Let’s compare the two recursive calls:

data[0] * data[0] + sumOfSquares(Js.Array.sliceFrom(1, data));
// vs.
debitIndex(data, index + 1);

In the first example, the recursion is the next-to-last thing we do (the last operation in the expression is the addition). We have to put the calculation on hold and save our partially-completed addition on the stack.

In the second example, the recursion is the last (and only) thing we do.

When the recursion is the last operation, that is called tail recursion.

In tail recursion, when you hit the base case, you have finished.

Taming the Scary Example

If we can make our recursive call from the first example tail recursive, we’ll have a non-scary recursion. Let’s examine the second example a bit more closely.

The reason we were to do the second example as tail recursion was because the parameters contained all the information needed to continue the process. There was no need to put any calculations on hold.

If we can do the same thing in the first example—make the partially-completed addition one of our parameters in the recursive call—we’ll be able to make it our only operation and end up with a non-scary tail recursive function.

Here’s the code that makes that happen:

let rec sumOfSquares = (accumulator, data) => {
  if (Js.Array.length(data) == 0) {
     accumulator 
  } else { 
     sumOfSquares(accumulator + data[0] * data[0],
        Js.Array.sliceFrom(1, data));
  }
};

let answer = sumOfSquares(0, data);

This time, our function has two parameters: the data array and an accumulator to hold our partially-completed calculation.

The base case changes: when we hit an empty array, we return whatever the calculation has accumulated.

If the array isn’t empty, the recursive call is the last—and only—thing we do. We pass along the partial calculation (the accumulator plus the square of the first item) and the remaining items in the array.

Let’s see what happens now when given the numbers array [|3, 7, 4|].

The accumulator is zero, and the array is [|3, 7, 4|].
Do a recursive call with 0 + 3^2 as the accumulator and the remaining items.
- The accumulator is 9, and the array is [|7, 4|].
- Do a recursive call with 9 + 7^2 as the accumulator and the remaining items.
  - The accumulator is 58, and the array is [|4|].
  - Do a recursive call with 58 + 4^2 as the accumulator and the remaining items.
    - The accumulator is 74, and the array is [||].
    - The array is empty. Return the accumulator (74).

Voilà—a non-scary recursion.

You can almost always use this accumulator trick to turn a “hold-off-and-climb-back-up” recursion into a “base-case-and-finished“ tail recursion.

Tail Recursion’s Big Win

There’s another enormous advantage of using tail recursion. Look at that last analysis of the sum of squares. Was there any real need to indent the list? If you line all the steps up at the left and cut out the recursion:

The accumulator is zero, and the array is [|3, 7, 4|]
The accumulator is 9 (3^2 + 0), and the array is [|7, 4|]
The accumulator is 58 (7^2 + 9), and the array is [|4|]
The accumulator is 74 (4^2 + 58), and the array is [||]

That looks a whole lot like a plain old while loop. ReasonML (and some other functional programming languages) take advantage of this. When the compiler detects tail recursion, it doesn’t use the stack at all. Instead, it compiles the recursion into a while loop. The stack is bypassed entirely, and there’s no possibility of stack overflow.

Bonus Section: Helper Functions

If you are approaching information overload, feel free to skip this section. You can come back and read it later.

The good news about tail recursion is that it is conceptually simpler and it can be optimized. The bad news is that the people using the function have to pass an extra parameter for the accumulator. They have to say sumOfSquares(numbers, 0) instead of sumOfSquares(numbers) and debitIndex(balances, 0) instead of debitIndex(balances). But we have a trick to solve that: helper functions.

ReasonML lets you nest functions within functions. We can rewrite the debitIndex() function to use only one parameter as follows:

let debitIndex = (data) => {
  let rec helper = (index) => {
    if (index == Js.Array.length(data)) {
      -1; 
    } else if (data[index] < 0.0) {
      index;
    } else {
      helper(index + 1); 
    }   
  };  

  helper(0);
};

let result = debitIndex(balances);

In this version, debitIndex() takes only one parameter: the array of values. It calls the nested helper() function to recursively move the index forward through the array until it finds a negative value. We don’t have to pass data to the helper() function; it is available in the scope of the outer function and it’s not changing from one call to the next.

Similarly, here’s the helper function version for the sum of squares:

let sumOfSquares = (data) => {
  let rec helper = (accumulator, data) => {
    if (Js.Array.length(data) == 0) {
       accumulator 
    } else { 
       helper(accumulator + data[0] * data[0],
          Js.Array.sliceFrom(1, data));
    };  
  };  

  helper(0, data);
};

let result = sumOfSquares(numbers);

In this case we do have to pass the data array to the helper() function because it is changing every time we call the helper function.

Summary

When solving a problem recursively, figure out the base case first.
Whenever possible make the function tail recursive— make the recursive call the last operation. You can do this by carrying along any intermediate results you need in the call parameters.
Use a language that optimizes tail recursion into a while loop. Your code will run faster and safer.