## Sunday, December 30

### Types and Programming Languages Revisited

My previous brute-force approach to list all the 4-dimension combinations of S = {(latent, manifest), (static, dynamic), (weak, strong), (nominal, structural)} typing -by filtering the desired tuples from the powerset of S - wasn't very efficient.
It was a perfect example of The Danger of Naïveté: an inefficient algorithm that was nevertheless simple to devise and implement.

Moreover, quoting The eight rules of Dean Carney, I should have observed that "the first place to look for a solution is within the problem itself". If the problem involves 4 tuples of 2 elements each to begin with, the efficient solution is not likely to require the powerset of all 8 elements.

Thus, I figured I should give it another go.

First, for simplicity and better readability, let me replace the values of S with the character-tuples on the left hand side:

(A, B) = (latent, manifest)
(C, D) = (static, dynamic)
(E, F) = (weak, strong)
(G, H) = (nominal, structural)

S = {(A, B), (C, D), (E, F), (G, H)}

Next, I'll write down some 4-size combinations. After a short while, a pattern emerges:

ACEG
ACEH
ACFG
ACFH
...

The pattern becomes clear when I look at the elements like this:

X1=(A, B) x X2=(C, D) x X3=(E, F) x X4=(G, H)

This is a Cartesian product of X1 x X2 x ... x Xn, the set containing all possible combinations of one element from each set.

With this knowledge, implementing an efficient algorithm is easy. First, a method to return the Cartesian product of two sets:

`# arguments must be lists, e.g.: cartesian([1, 2], [3, 4])def cartesian(list1, list2):     result = []     for el in list1:         for item in list2:             if isinstance(el, list):                 result.append(el + [item])             else:                 result.append([el] + [item])     return result`

Testing the method with input X=[1, 2] x Y=[3, 4] yields:

`     [[1, 3], [1, 4], [2, 3], [2, 4]]`

Which looks good.
Next, a method to process the Cartesian product of any number of sets. Here's a candidate implementation:

`def types_cartesian(aList):     head = aList     tail = aList[1:]     for item in tail:         head = cartesian(head, item)     return head`

The output of method types_cartesian(aList) given input aList=S is:

S={['static', 'dynamic'], ['weak', 'strong'], ['latent', 'manifest'], ['nominal', 'structural']}

S1 x S2 x ... Sn =

`     ['static', 'weak', 'latent', 'nominal']     ['static', 'weak', 'latent', 'structural']     ['static', 'weak', 'manifest', 'nominal']     ['static', 'weak', 'manifest', 'structural']     ['static', 'strong', 'latent', 'nominal']     ['static', 'strong', 'latent', 'structural']     ['static', 'strong', 'manifest', 'nominal']     ['static', 'strong', 'manifest', 'structural']     ['dynamic', 'weak', 'latent', 'nominal']     ['dynamic', 'weak', 'latent', 'structural']     ['dynamic', 'weak', 'manifest', 'nominal']     ['dynamic', 'weak', 'manifest', 'structural']     ['dynamic', 'strong', 'latent', 'nominal']     ['dynamic', 'strong', 'latent', 'structural']     ['dynamic', 'strong', 'manifest', 'nominal']     ['dynamic', 'strong', 'manifest', 'structural']`

This is the same list as the one obtained earlier with the powerset approach.
The big difference is that with the powerset implementation the number of possible combinations explodes exponentially ( O(2n) ), whereas the Cartesian product is a quadratic ( O(n2) ) algorithm.

Here's the code.

Related:
Types and Programming Languages
http://en.wikipedia.org/wiki/Cartesian_product
What to know before debating type systems 