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
ADEG
ADEH
...

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

X₁=(A, B) x X₂=(C, D) x X₃=(E, F) x X₄=(G, H)

This is a Cartesian product of X₁ x X₂ x ... x X_n, 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[0]
     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']}

S₁ x S₂ x ... S_n =


     ['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(2ⁿ) ), whereas the Cartesian product is a quadratic ( O(n²) ) algorithm.

Here's the code.


Related:
Types and Programming Languages
http://en.wikipedia.org/wiki/Cartesian_product
http://programming-misc.googlecode.com/svn/trunk/python/types_cartesian.py
What to know before debating type systems