Subject: RE: [hackers-il] Evolution and Functional programming

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

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

oh, I don't "need" this solution at all. I was just thinking about these
ideas.

Here's how I'd do the array part:

Suppose I decide on array size of 17 (the standard prime :-)
And I want the hash function to map some value to, lets say 5.
I wouldn't want my hash function to return 5, because that'll do me no good,
I'd probably want to get something like 
(cdr(cdr(cdr(cdr(car array)))))

So I can eval it and get the list I need.

What do you say?

---

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

> So I can eval it and get the list I need.

It may work. If bitwise operations are not present you can emulate them
with x mod 2 and x div 2. Anyway, here is some pseudocode:

get_list(hash_branch, number, digit, max_digit)
    if (digit == max_digit)
        return hash_branch
    else
        if (number mod 2 == 0)
            return get_list(
                car(hash_branch), 
                (number div 2), 
		digit+1,
                max_digit
                )
        else
            return get_list(
                cdr(hash_branch),
                (number div 2),
                digit+1,
                max_digit
                )

No evals are necessary!

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.