From: Joel VanderWerf <vjoel@...>
Date: 2007-10-23T14:33:45+09:00
Subject: Re: recursive array

Dido Sevilla wrote:
> On 10/23/07, Simon Schuster <significants@gmail.com> wrote:
>> also, I'm interested in what is going on "behind the scenes" here. is
>> a[4][4][4][4][0] actually reaching in 4 levels deep?
> 
> Well, what seems to have happened here is you created what amounts to
> a cyclic graph using the array.  Every time you get the 4th index of
> a, you get back a itself.  It's not exactly reaching in four levels
> deep but more accurately referencing itself four times. It's as if you
> created an array of pointers in C, and had some element in the array
> be a pointer back to the array itself.
> 
> There are many uses for data structures of this type, as formal
> computer science is rife with graphs and the algorithms to deal with
> them. For instance, you could use such a structure as the internal
> representation of a state machine of some kind (finite automaton,

Just for fun...

# alphabet = {0, 1, 2}
# language = (012)*

s0 = []
s1 = []
s2 = []
s_ = []

fsm = [s0, s1, s2, s_]

s0[0] = s1
s0[1] = s_
s0[2] = s_

s1[0] = s_
s1[1] = s2
s1[2] = s_

s2[0] = s_
s2[1] = s_
s2[2] = s0

s_[0] = s_
s_[1] = s_
s_[2] = s_

accept = proc do |string|
   string.split("").inject(s0) {|s, c| s[c.to_i]}.equal? s0
end

p accept["012012"]
p accept[""]
p accept["01201"]
p accept["12012"]
p accept["01201"]

p fsm # I love this part!

__END__

Output:

true
true
false
false
false
[[[[[...], [...], [...]], [[[...], [...], [...]], [[...], [...], [...]], 
[...]], [[...], [...], [...]]], [[...], [...], [...]], [[...], [...], 
[...]]], [[[...], [...], [...]], [[[...], [...], [...]], [[...], [...], 
[...]], [[...], [[...], [...], [...]], [[...], [...], [...]]]], [[...], 
[...], [...]]], [[[...], [...], [...]], [[...], [...], [...]], [[[[...], 
[...], [...]], [...], [[...], [...], [...]]], [[...], [...], [...]], 
[[...], [...], [...]]]], [[...], [...], [...]]]

-- 
       vjoel : Joel VanderWerf : path berkeley edu : 510 665 3407