Subject: Evolution and Functional programming

From: Chen Shapira <[email-masked]>
Date: Sun, 14 Jan 2001 17:24:12 +0200

> I found a funny picture, of the evolution of humans from apes 
> to computer-
> users :)
> Take a look:

Evolution:
Which reminds me of something I used to ponder.
The human body is very well designed to the happy task of running in a
savanna and throwing things. 
These days however our main task involves sitting somewhere and either
shuffling papers of hitting keys.

Usually it could take a while until evolution did its thing and we all have
bodies adapted to sitting and hitting keys, but these days we have genetic
engneering advancing rapidly, so perhaps we could speed things up. So the
important question is - what do you think is the best shape for a
table-sitting, key hitting creature?

And Functional Programming:
How would you implement a hash table in a pure-functional language? (no side
effects)

---

From: Shlomi Fish <[email-masked]>
Date: Sun, 14 Jan 2001 17:46:52 +0200 (IST)

> How would you implement a hash table in a pure-functional language? (no side

I have been thinking about that too recently. In any case, Haskell
supports incremental updates to arrays, but I'm not sure whether doing
such thing every time you wish to remove or add an item will cause the
garbage collection to kill you or not.

A hash is usually a vector of linked lists (unless you use open
addressing, which I have still to see one implementation of it.) There
isn't a problem with the linked list part, but arrays are not handled very
well in purely functional programming languages.

In any case, if you need a dictionary, then the GHC compiler for Haskell
contains an implementation of a balanced binary tree. Since in a hash
table all cells are present, it may be possible to use an "array" which is
actually a tree of tuples whose end elements are the cells. This will have
an O(log(N)) access time for getting to the cell, in comparison to an
array which has O(1), but it will help the garbage collection.

Regards,

	Shlomi Fish
 
> 
> 
> To unsubscribe from this group, send an email to:
> [email-masked]
> 
> 
> 
> 

----------------------------------------------------------------------
Shlomi Fish        [email-masked] 
Home Page:         http://t2.technion.ac.il/~shlomif/
Home E-mail:       [email-masked]

The prefix "God Said" has the extraordinary logical property of 
converting any statement that follows it into a true one.

---

From: Omer Zak <[email-masked]>
Date: Sun, 14 Jan 2001 18:16:13 +0200 (EET)

Wow, in the beginning of 21st century, hackers discuss various genetic
programming ideas in addition to computer programming.  How cool!!!

To the specifics:
There'll be co-evolution of the electronic devices and the human bodies.
Eventually, we will grow very sensitive patches on our fingertips, which
have high concentrations of nerve ends.
With those patches, we'll interface with the electronic devices and
exchange directly electronic pulses with them.

Tomorrow's children caught twiddling fingers will be punished like
yesterday's children caught touching the prehistorically sensitive parts
of their skins (which are close to their reproductive organs).
                                             --- Omer
WARNING TO SPAMMERS:  at http://www.zak.co.il/spamwarning.html

On Sun, 14 Jan 2001, Chen Shapira wrote:

> bodies adapted to sitting and hitting keys, butthese days we have genetic

---

From: Oleg Goldshmidt <[email-masked]>
Date: 14 Jan 2001 18:27:40 +0200

Chen Shapira <[email-masked]> writes:

> bodies adapted to sitting and hitting keys, 

Hmm... We lost the tail, which would be useful for keeping balance
while running in a savanna, but quite uncomfortable for sitting at
a desk.

> How would you implement a hash table in a pure-functional language? (no side

Interesting question. I wonder if there is a pure-functuonal scheme
implementation. I suppose it would be based on the concept of
"operational identity", i.e. objects are the same if they behave the
same. A hash table has to behave in a certain way w.r.t. insert,
delete, and search operations. I suppose that using chaining, i.e.
putting all the elements that hash to the same slot in a linked list,
we can do something. E.g. insertion will be consing, deletion can be
non-destructive, etc.

This is probably terribly inefficient, at least space-wise, but that's
the usual trade-off.

Disclaimer: I have no idea if what I wrote makes sense ;-)

-- 
Oleg Goldshmidt | Comgates Ltd. | [email-masked] 
"... We work by wit, and not by witchcraft;
 And wit depends on dilatory time." [Shakespeare]