### 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**_{1}=(A, B) x **X**_{2}=(C, D) x **X**_{3}=(E, F) x **X**_{4}=(G, H)

This is a Cartesian product of **X**_{1} x **X**_{2} 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**_{1} x **S**_{2} 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 (

^{n})**O(n**) algorithm.

^{2})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

## 2 comments:

Parece-me que alguém anda com tempo a mais ;)

Bom ano fofinho :D ... para que nao penses que te ignorei preferi responder-te por aqui ao invés de um sms. É mais pessoal, o pessoal não percebe um corno porque é português, e ainda te posso mandar recados subliminares, como desejar-te felicidades e que sejas feliz nesse golpe do baú de que tu foste alvo, hehehe

Nice and clear review. But I think beginners still need the basics to fully grasp what's going on her

Post a Comment