[Haskell-cafe] Re: "Haskell is a scripting language inspired by Python."

Ketil Malde ketil at malde.org
Fri Nov 5 04:23:44 EDT 2010


"Richard O'Keefe" <ok at cs.otago.ac.nz> writes:

> Automatically?  Probably not.

>> Like biologist can determine the distance between two genotypes, and
>> determine a hierarchy between species from that. 

I'm going to say the same as Richard, only differently.  For computer
languages, we can't observe the genotype, only the phenotype.  I.e. we
can look at what the language looks like on the surface, but not what
made it so - there are no "genes" available.

This is where biology was before DNA was discovered, and it led to
interesting taxonomies, starting with Genesis's division into animals by
habitat. 

> Until this year I taught some of that stuff.  The distance between two
> sequences depends hugely on *what* you choose to measure (which particular
> features) and *how* you measure distances (there are similarity matrices
> people use, but you have to choose).

I think you are referring to edit distance here, where you find
the optimum given penalties for substitutions and gaps - typically
an affine penalty for gaps (exepensive gap opening penalty, somewhat
cheaper gap extension), and a char x char cost matrix for substitution.

Especially the gap costs aren't well founded theoretically, so hopefully
the results aren't varying /hugely/.

> Then there are algorithms that give
> optimal results but blow up for anything much past 15 species, 

I.e, edit distance is O(n^k) for k sequences of length n.

> Then we turn to human designs, and suddenly THERE IS NO TREE.

Bacteria can also do horizontal gene transfer, so there is no (single)
tree there either.

-k
-- 
If I haven't seen further, it is by standing in the footprints of giants


More information about the Haskell-Cafe mailing list