Many good programming practices boil down to preparing for change or expressing intent. Novices emphasize the former, experts the latter.

(John D. Cook)

]]>Many good programming practices boil down to preparing for change or expressing intent. Novices emphasize the former, experts the latter.

(John D. Cook)

]]>This note presents `Free`

from a sole structural standpoint. More specifically, we reduce the derivation of `Free`

to the problem of designing a data type for trees without predetermined internal nodes. The reader should be familiar with recursive data types, type constructors, as well as the functor and monad

This note presents `Free`

from a sole structural standpoint. More specifically, we reduce the derivation of `Free`

to the problem of designing a data type for trees without predetermined internal nodes. The reader should be familiar with recursive data types, type constructors, as well as the functor and monad abstraction. The code is written in Haskell.

Let us consider the following encoding of a tree:

```
data Tree a = Leaf a | Branch (Tree a) (Tree a)
```

Note that `Tree`

has an immediate `Monad`

instance:

```
instance Monad Tree where
return x = Leaf x
(Leaf x) >>= g = g x
(Branch l r) >>= g = Branch (l >>= g) (r >>= g)
```

According to the above, `(>>=)`

replaces each leaf node with whatever tree the function `g`

returns. That is, `(>>=`

) implements adjoining between trees. As an example, we can duplicate each leaf node by means of the `duplicateLeaf`

function:

```
duplicateLeaf :: a -> Tree a
duplicateLeaf x = Branch (Leaf x) (Leaf x)
t1 = Branch (Leaf 9) (Leaf 7)
-- t2 = Branch (Branch (Leaf 9) (Leaf 9)) (Branch (Leaf 7) (Leaf 7))
t2 = t1 >>= duplicateLeaf
```

At present, `Branch`

is the only possible structural form for internal nodes. The most immediate way to support alternative forms for internal nodes would be to extend the definition of `Tree`

with additional data constructors. For instance, we may introduce a `Branch'`

constructor to account for the case of an internal node with three child nodes:

```
data Tree a = Leaf a
| Branch (Tree a) (Tree a)
| Branch' (Tree a) (Tree a) (Tree a)
```

However, one may wonder if a more general solution exists. That is, if it is possible to provide a definition of `Tree`

that permits internal nodes of arbitrary structures without the need of explicitly encoding them in the definition of the data type.

As an example, we might be interested in internal nodes with either one, two or three child nodes. Let us enumerate these three alternatives in a dedicated data type, which we parameterize on the type of its child nodes:

```
data Node e = Unary e | Binary e e | Ternary e e e
```

This is to say that a value of type `Node e`

represents an internal node whose child nodes are of type `e`

. Depending on the use case at hand, we may come up with different definitions for the internal nodes, such as:

```
data Node' e = Empty | Unary e
```

Nonetheless, we would have a type constructor `f`

(e.g., `Node`

) parameterized on the type `e`

of its child nodes. It is therefore a matter of altering the definition of `Tree`

so as to account for whatever type constructor `f`

happens to represent our internal nodes. A revised definition may read:

```
data Tree f a = Leaf a | Branch (f e)
```

`Branch`

now holds a single field, namely, the actual internal node of type `f e`

(e.g., `Node e`

). Still, the above is not valid Haskell, in that the type parameter `e`

is only mentioned on the right-hand side of the definition. However, we know that `e`

denotes the type of the child nodes. Since child nodes are themselves trees, that is, they are of type `Tree f a`

, we conclude that the final definition should read:

```
data Tree f a = Leaf a | Branch (f (Tree f a))
```

It is useful to contrast the original definition with what we have just derived:

```
data Tree a = Leaf a | Branch (Tree a) (Tree a) -- original
data Tree f a = Leaf a | Branch (f (Tree f a)) -- parameterized on f
```

As shown, we are still in the presence of a recursive data type; the only difference being that internal nodes have two explicit child nodes (of type `Tree a`

) in the original definition, while arbitrarily many child nodes (of type `Tree f a`

) in the second.

We are now in the condition of instantiating trees with different internal nodes. For instance:

```
t1 :: Tree Node Integer
t1 = Branch (Unary (Leaf 5))
t2 :: Tree Node Integer
t2 = Branch (Binary (Branch (Unary (Leaf 7))) (Leaf 8))
```

As shown, both `t1`

and `t2`

are trees whose internal nodes are determined by `Node`

, and whose leafs retain a value of type `Integer`

.

The changes we implemented in `Tree`

call for changes also in the corresponding `Monad`

instance. For convenience, let us repeat the original definition:

```
instance Monad Tree where
return x = Leaf x
(Leaf x) >>= g = g x
(Branch l r) >>= g = Branch (l >>= g) (r >>= g)
```

The first straightforward adaptation is to include `f`

in the context. In addition, observe that no changes are required to either `return`

or the first match for `(>>=)`

, as they both have to do with leaf nodes.

```
instance Monad (Tree f) where
return x = Leaf x
(Leaf x) >>= g = g x
(Branch y) >>= g = ...
```

The `Branch`

case proves more challenging. In principle, we would like to apply `(>>= g)`

to every child node the internal node at hand happens to contain. In this case however, we are only provided with `y`

, which represents the entirety of the internal node, effectively masking its specific structure. As a consequence, we can no longer explicitly recurse over its child nodes, as we used to do in the original implementation.

We therefore need an operation on `y`

and `(>>= g)`

that would result in the application of `(>>= g)`

to every child node within `y`

. In other words, we would like to *map* every child node within `y`

to whatever `(>>= g)`

returns. Fortunately, there already exists an abstraction for expressing the *mappability* of a given type, named `Functor`

.

Sticking to the example, the `Functor`

instance for `Node e`

may read:

```
instance Functor Node where
fmap f (Unary e) = Unary (f e)
fmap f (Binary e1 e2) = Binary (f e1) (f e2)
fmap f (Ternary e1 e2 e3) = Ternary (f e1) (f e2) (f e3)
```

Moving the mapping operation within the type functor `f`

(e.g., `Node`

) should appear natural, as it is where we confined the explicit knowledge on the shape of the internal nodes. The intricacy of the mapping is hidden from the calling site by means of `fmap`

.

The instance we just introduced is so immediate that GHC can automatically derive it for us, without further interventions.

```
{-# LANGUAGE DeriveFunctor #-}
data Node e = Unary e | Binary e e | Ternary e e e deriving Functor
```

With the `Functor`

instance in place, we can complete the specification of the `Monad`

instance for `Tree`

as:

```
instance Functor f => Monad (Tree f) where
return x = Leaf x
(Leaf x) >>= g = g x
(Branch y) >>= g = Branch (fmap (>>= g) y)
```

Note how we managed to recover the intended behavior: leaf nodes are replaced with whatever tree the function `g`

happens to return; leaf nodes are reached by applying `(>>= g)`

to the child nodes of every internal node. To show this, let us adapt the `duplicateLeaf`

example we introduced at the beginning of our discussion:

```
duplicateLeaf :: a -> Tree Node a
duplicateLeaf x = Branch (Binary (Leaf x) (Leaf x))
t3 = Branch (Binary (Leaf 9) (Leaf 7))
t4 = t3 >>= duplicateLeaf
-- t4 = Branch (Binary (Branch (Binary (Leaf 9) (Leaf 9)))
-- (Branch (Binary (Leaf 7) (Leaf 7))))
```

`Free`

The derivation of `Free`

is just one renaming away. In particular, it amounts to renaming the data type from `Tree`

to `Free`

, and its data constructors from `Branch`

to `Free`

, and from `Leaf`

to `Pure`

. The final data type is therefore defined as follows:

```
data Free f a = Pure a | Free (f (Free f a))
```

The above derivation highlights `Free`

's affinity with well-known data types for representing trees. In particular, `Free`

appears as a generalization that enables expressing trees with undetermined internal nodes. This intuition serves as a valuable starting point for getting acquainted with `Free`

. Further elaborations are however necessary; most importantly, additional discussion on how to lift values of the inner type constructor `f`

(e.g., `Node`

) to values of type `Free f a`

(e.g., `Free Node a`

), with the aim of enabling `do`

notation. Likely, a treatment of such a topic would benefit from the introduction of some semantics, such as qualifying the inner type constructor as a way of encoding some Domain-Specific Language (DSL). For this reason, it is somewhat out of the scope of this note.

]]>Only accept as input terms coming from your own language.

]]>Only accept as input terms coming from your own language.

What I had been learning in my Programming Language course, however, was that I really could manage my own control flow if I wanted. Furthermore, I could start with a simpler, more naive program and basically DERIVE the sophisticated one through a series of correctness-preserving program transformations.

Rest of the

]]>What I had been learning in my Programming Language course, however, was that I really could manage my own control flow if I wanted. Furthermore, I could start with a simpler, more naive program and basically DERIVE the sophisticated one through a series of correctness-preserving program transformations.

Rest of the story here.

]]>"The walking skeleton is to test-drive the initial architecture."

(S. Freeman, N. Pryce)

]]>"The walking skeleton is to test-drive the initial architecture."

(S. Freeman, N. Pryce)

]]>Constructors that fail when called without new are a potential problem, and three solutions we can use are, respectively, auto-instantiation, overloading the constructor, or killing such calls with fire.

Here's the rest of the article.

]]>Constructors that fail when called without new are a potential problem, and three solutions we can use are, respectively, auto-instantiation, overloading the constructor, or killing such calls with fire.

Here's the rest of the article.

]]>`begin`

lookalike in ES6, we can take advantage of the fact that in JavaScript arguments are evaluated from left to right. This leads to:
```
const begin = (...args) => args[args.length - 1];
```

We can therefore replicate SICP's `make-withdraw`

procedure as:

`const makeWithdraw = bal =>`

]]>`begin`

lookalike in ES6, we can take advantage of the fact that in JavaScript arguments are evaluated from left to right. This leads to:
```
const begin = (...args) => args[args.length - 1];
```

We can therefore replicate SICP's `make-withdraw`

procedure as:

```
const makeWithdraw = bal =>
amount => bal >= amount ? begin(bal = bal - amount, bal)
: "Insufficient founds"
```

]]>`let`

expressions, such as
```
(let ((x 3) (y 5)) (+ x y))
```

is to use ES6 default parameters:

```
((x = 3, y = 5) => x + y)()
```

It is possible to go one step further by defining an auxiliary `let_`

function as:

`const let_ = f => f(`

]]>`let`

expressions, such as
```
(let ((x 3) (y 5)) (+ x y))
```

is to use ES6 default parameters:

```
((x = 3, y = 5) => x + y)()
```

It is possible to go one step further by defining an auxiliary `let_`

function as:

```
const let_ = f => f();
```

This allows rewriting the previous function application as:

```
let_((x = 3, y = 5) => x + y);
```

Definitely not the most idiomatic thing to do, though :-)

]]>"Unit tests prove that a solution works in a particular way, rather than asserting that it solves a particular problem."

(J. Humble et al.)

]]>"Unit tests prove that a solution works in a particular way, rather than asserting that it solves a particular problem."

(J. Humble et al.)

]]>"Pascal and C are special-purpose languages for manipulating the registers and memory."

(P. Norvig)

]]>"Pascal and C are special-purpose languages for manipulating the registers and memory."

(P. Norvig)

]]>"We do not develop the domain. The domain is some realm of know-how of the business we are working in. What we design and implement is a model of a domain."

(V. Vernon)

]]>"We do not develop the domain. The domain is some realm of know-how of the business we are working in. What we design and implement is a model of a domain."

(V. Vernon)

]]>"Naming is perhaps the most powerful abstracting notion we have, in any language, for it allows any complex to be reduced for linguistic purposes to a primitive atom."

(G. L. Steele Jr.)

]]>"Naming is perhaps the most powerful abstracting notion we have, in any language, for it allows any complex to be reduced for linguistic purposes to a primitive atom."

(G. L. Steele Jr.)

]]>"Mathematical induction proves that we can climb as high as we like on a ladder, by proving that we can climb onto the bottom rung (the basis) and that from each rung we can climb up to the next one (the induction)."

(Concrete Mathematics 2nd ed.)

]]>"Mathematical induction proves that we can climb as high as we like on a ladder, by proving that we can climb onto the bottom rung (the basis) and that from each rung we can climb up to the next one (the induction)."

(Concrete Mathematics 2nd ed.)

]]>