Code Along – Nesting Traversals

A code-along is a story about coding in which you are encouraged to “code up” all the examples in the story. In a code-along you shouldnot cut-and-paste.

In this code-along, we will take a look at how to construct a lace using the applyWithin traversal function (for more about laces, see Special Project in Level 3). The basic idea is to create a point_function that when called with a point (i.e., a coordinate) will either (1) create a lace of a given size at that point, or (2) skip that point (i.e., do nothing). More specifically, our point_function will only create a lace when called with a point having a particular property. We define this property using a function called a predicate, which is a function whose result (i.e., value returned) is a Boolean value. We will build laces only at points for which our predicate returns the value true. All other points will be skipped by our point_function.

We use the applyWithin traversal function to traverse very specific ranges. Within the range of points traversed by a particularapplyWithin function, there will be exactly three points where our lace should be created. The three points correspond to the “stamping pattern” of the lace we are creating. All other points will be skipped. The definition of the point_function type and the signature of theapplyWithin traversal function are shown below.

Code-along Program 1

In the program below, the function lace1 uses the applyWithin function to traverse the points in the xz-axis belonging to a 2¹ x 2¹ box. Specifically, the points in the set { (0,0,0), (0,0,1), (1,0,0), (1,0,1) } will be visited in no particular order. To each of the points in this square, the function applyFn is applied.

In the lace pattern that we are using, a larger lace is constructed from three smaller laces. For example, a lace of size 2² is constructed from three laces of size 2¹. In turn, a lace of size 2¹ is constructed from three laces of size 2⁰, and a lace of size 2⁰ is constructed from a 1-bit blue brick.

The body of the function applyFn is a conditional expression, whose condition (i.e., the expression between the keyword if and the keyword then) is a call to a locally declared predicate calledbuildLace. When buildLace (x,y,z) evaluates to true a lace of size 0 is constructed at the point (x,y,z); otherwise a call is made to a the function skip, which does nothing. Technically speaking, the conditional expression in the function applyFn could be simplified by replacing the call skip(x,y,z) with the unit value (). However, the call to skip is included in the code to highlight how the then-else branches of the conditional expression relate to one another.

This brings us to the predicate property. This function has three formal parameters: (1) the size of a 2ⁿ x 2ⁿ box in which a lace stamping pattern is to occur, (2) a point denoting the lower-left corner of the box, and (3) a point falling within the box which will be supplied by the applyWithin function.

Within the the body of property the variable laceSize computes the size of the smaller lace that will be used to construct the larger lace (the one currently under construction). The variableslacePosition1, lacePosition2, and lacePosition3 define the points in the 2ⁿ x 2ⁿ box where the smaller laces are to be constructed. The variables atPos1, atPos2, and atPos3 hold the Boolean-valued results of equality-based comparisons indicating whether (x2,y2,z2) is a point at which a smaller lace should be constructed.

In this particular example, the applyWithin function in the body of lace1 will traverse (in no assumed order) the point set:

Note that 2¹ – 1 = 1, which is how the value of 1 is arrived at in the above point set. Our lace of size 1 is constructed by creating laces of size 0 at the points { (0,0,0), (0,0,1), and (1,0,1) }.

open Level_5;

fun property boxSize (x1,y1,z1) (x2,y2,z2) = 
  let
    val laceSize = boxSize div 2;
        
    val lacePosition1 = (x1         ,y1,z1         );
    val lacePosition2 = (x1+laceSize,y1,z1         );
    val lacePosition3 = (x1+laceSize,y1,z1+laceSize);
        
    val atPos1 = lacePosition1 = (x2,y2,z2);
    val atPos2 = lacePosition2 = (x2,y2,z2);
    val atPos3 = lacePosition3 = (x2,y2,z2);
        
  in
    atPos1 orelse atPos2 orelse atPos3
  end;

fun lace0 (x,y,z) = put (1,1,1) BLUE (x,y,z);
fun skip (x,y,z) = ();

fun lace1 (x,y,z) = 
    let
        val buildLace = property 2 (x,y,z);
        
        fun applyFn (x,y,z) = 
            if buildLace (x,y,z) then lace0 (x,y,z) 
            else skip (x,y,z);
    in
        applyWithin (x,y,z) (x+2-1,y,z+2-1) applyFn
    end;
    
build(32,1,32);

lace1 (0,0,0);

show "Lace";

Code-along Program 2

The program in this example extends the previous program with a declaration for the function lace2 which is quite similar (by design) to the declaration of the function lace1. In this case, the size of the lace constructed by lace2 is 2².

Worth noting is that the construction of a lace of size 2² is accomplished with the help of a call to the function applyWithin. However, within this traversal smaller traversals are performed when points are encountered where laces of size 2¹ are to be constructed. And finally, laces of size 2³ (and larger) can be constructed through additional function declarations.

open Level_5;

fun property boxSize (x1,y1,z1) (x2,y2,z2) = 
  let
    val laceSize = boxSize div 2;
        
    val lacePosition1 = (x1         ,y1,z1         );
    val lacePosition2 = (x1+laceSize,y1,z1         );
    val lacePosition3 = (x1+laceSize,y1,z1+laceSize);
        
    val atPos1 = lacePosition1 = (x2,y2,z2);
    val atPos2 = lacePosition2 = (x2,y2,z2);
    val atPos3 = lacePosition3 = (x2,y2,z2);   
  in
    atPos1 orelse atPos2 orelse atPos3
  end;

fun lace0 (x,y,z) = put (1,1,1) BLUE (x,y,z);
fun skip (x,y,z) = ();

fun lace1 (x,y,z) = 
    let
        val buildLace = property 2 (x,y,z);
        
        fun applyFn (x,y,z) = 
            if buildLace (x,y,z) then lace0 (x,y,z) 
            else skip (x,y,z);
    in
        applyWithin (x,y,z) (x+2-1,y,z+2-1) applyFn
    end;
    
fun lace2 (x,y,z) = 
    let
        val buildLace = property 4 (x,y,z); 
        
        fun applyFn (x,y,z) = 
            if buildLace (x,y,z) then lace1 (x,y,z) 
            else skip (x,y,z);
    in
        applyWithin (x,y,z) (x+4-1,y,z+4-1) applyFn
    end;
    
build(32,1,32);

lace2 (0,0,0);

show "Lace";