8 Recipe for Variant Data (Sum Types)
Sometimes, data can take on one of different variants. An example are points that may be represented either in Euclidean coordinates (x, y) or in polar coordinates (theta, magnitude). In the latter case, magnitude specifies the distance from the origin of the coordinate system and theta specifies the direction with respect to the positive x-axis. So, (0°, 3) is equivalent to (3, 0) in Euclidean coordinates, (90°, 2) is equivalent to (0, 2), and (45°, sqrt(2)) is equivalent to (1, 1).
A data type that can represent one of different choices is called a variant, a (tagged) union, or a sum type. In PostFix, such types are represented as multiple arrays, one for each variant.
point-euclid-polar.pf serves as the example for variant data.
8.1 Steps
8.1.1 Problem statement
Write down the problem statement as a comment. The problem statement should answer these questions: What information needs to be represented? What should the function (to be implemented) do with the data? What cases need to be considered?
#<
Points on the 2D plane may be given either in Euclidean coordinates or in polar coordinates. Design a function that computes the distance of such a point to the origin of the coordinate system.
>#
8.1.2 Data definition
Write how the domain information should be represented in the program, or, vice versa, write how to interpret the data (e.g., a pair of numbers) as real-world information (e.g., a point in 2D space). Write a data definition as an array with symbols as attribute names. Write a constructor for creating and initializing values of this kind.
# enumeration of point variants:
# :euclid, :polar
euclid: (x :Num, y :Num -> :Arr) { # constructor function
[euclid: x: x y: y]
} fun
euclid?: (e :Obj -> :Bool) { # detector function
[ { e arr? }
{ e length 5 = }
{ e 0 get :euclid = } ] and
} fun
euclid-x: (e :Arr -> :Num) { # accessor function
e .:x
} fun
euclid-y: (e :Arr -> :Num) { # accessor function
e .:y
} fun
polar: (theta :Num, magnitude :Num -> :Arr) { # constructor function
[polar: theta: theta magnitude: magnitude]
} fun
polar?: (p :Obj -> :Bool) { # detector function
[ { p arr? }
{ p length 5 = }
{ p 0 get :polar = } ] and
} fun
polar-theta: (p :Arr -> :Num) { # accessor function
p .:theta
} fun
polar-magnitude: (p :Arr -> :Num) { # accessor function
p .:magnitude
} fun
8.1.3 Function name
distance-to-origin:
8.1.4 Parameter list
distance-to-origin: (p :Arr -> :Num)
8.1.5 Function stub
distance-to-origin: (p :Arr -> :Num) {
0
} fun
8.1.6 Purpose statement
Write down a purpose statement (given as a comment).
# Computes the distance from the given point
# to the origin of the coordinate system.
8.1.7 Examples and expected results
Write down examples with expected results in the test method. Define any constants that the function needs. Check that the code is parsed correctly. (Some tests will fail for the stub.)
distance-to-origin-test: {
1e-10 EPSILON!
# test cases for polar variant
0 0 polar distance-to-origin, 0, EPSILON test~=
0 1 polar distance-to-origin, 1, EPSILON test~=
2.3 2 polar distance-to-origin, 2, EPSILON test~=
# test cases for Euclidean variant
0 -2 euclid distance-to-origin, 2, EPSILON test~=
2 0 euclid distance-to-origin, 2, EPSILON test~=
1 1 euclid distance-to-origin, 2 sqrt, EPSILON test~=
test-stats
} fun
distance-to-origin-test
It is important to generate test cases for each variant.
8.1.8 Function body
Implement the function body. Put required helper functions on a "wish list." These will be implemented later.
How to identify the need for a helper function: A function should perform one well-defined task. A change in task or data type should be outsourced in a helper function. Moreover, a reusable subtask should be outsourced in a helper function (Don’t Repeat Yourself, DRY principle). It is often helpful to write a stub for the helper functions. This way you can already run the program.
The implementation of the example function does not need helper functions.
# Computes the distance from the given point
# to the origin of the coordinate system.
distance-to-origin: (p :Arr -> :Num) {
{ p euclid? } {
p euclid-x p euclid-x *
p euclid-y p euclid-y * + sqrt
}
{ p polar? } {
p polar-magnitude
}
} cond-fun
The function takes different strategies to compute the distance of the point to the root, depending on whether the point is given in Euclidean or in polar coordinates. The detector functions are used to distinguish these cases.
8.1.9 Testing
Check that the function body satisfies the tests. Correct the function body (and the tests). Look for opportunities to simplify the structure of the code. This typically requires multiple iterations.
point-euclid-polar.pf, line 78: Check passed.
point-euclid-polar.pf, line 79: Check passed.
point-euclid-polar.pf, line 80: Check passed.
point-euclid-polar.pf, line 83: Check passed.
point-euclid-polar.pf, line 84: Check passed.
point-euclid-polar.pf, line 85: Check passed.
All 6 tests passed!
8.1.10 Review and revise
Review and revise the function name, the parameter names, and the purpose statement. Improve them if necessary. A design is not complete until it has a purpose statement and tests. The purpose statement should describe what the function computes (not how it does the computation) and should mention the given inputs and produced result. The test examples should cover corner cases and a typical case.
Given the implementation, we can write a reusable template for functions that handle points:
fn-for-points: (p :Arr -> ...) {
{ p euclid? } {
p euclid-x ...
p euclid-y ...
}
{ p polar? } {
p polar-magnitude ...
p polar-theta ...
}
} cond-fun
8.2 Data Definitions for Variant Data
You do not have to write constructor, detector, and accessor functions yourself. The datadef operator automatically creates them as well as type symbols for each variant and the overall type itself. Thus, with datadef it is possible to define new types. The type names can be used in parameter lists to precisely denote the type, whereas above we just used the type :Arr.
Point: {
Euclid: (x :Num, y :Num)
Polar: (theta :Num, magnitude :Num)
} datadef
# Computes the distance from the given point
# to the origin of the coordinate system.
distance-to-origin: (p :Point -> :Num) {
{ p euclid? } {
p euclid-x p euclid-x *
p euclid-y p euclid-y * + sqrt
}
{ p polar? } {
p polar-magnitude
}
} cond-fun
Point: {
Euclid: (x :Num, y :Num)
Polar: (theta :Num, magnitude :Num)
} datadef
point?: ( p :Obj -> :Bool ) {
[ { p euclid? } { p polar? } ] or
} fun
euclid: ( x :Num y :Num -> :Euclid ) {
[ :datadef :Euclid x y ]
} fun
euclid?: ( p :Obj -> :Bool ) {
[ { p arr? }
{ p length 2 >= }
{ p 0 get :datadef = }
{ p 1 get :Euclid = } ] and
} fun
euclid-x: ( p :Euclid -> :Num ) {
p 2 get
} fun
euclid-y: ( p :Euclid -> :Num ) {
p 3 get
} fun
polar: ( theta :Num magnitude :Num -> :Polar ) {
[ :datadef :Polar theta magnitude ]
} fun
polar?: ( p :Obj -> :Bool ) {
[ { p arr? }
{ p length 2 >= }
{ p 0 get :datadef = }
{ p 1 get :Polar = } ] and
} fun
polar-theta: ( p :Polar -> :Num ) {
p 2 get
} fun
polar-magnitude: ( p :Polar -> :Num ) {
p 3 get
} fun
8.3 Exercises
Write a data definition for a type that can represent one of miles or kilometers. Use this data definition to represent distances. Design a function convert-distance that converts a distance to the other unit.
Write a data definition for a type Shape that can represent one of a rectangle, a circle, or an equilateral triangle. Write a function that computes the area of a shape.