Recursive array

Ruby
1

207:0> a = [1,2,3,4]
[1, 2, 3, 4]
208:0> a[4] = a
[1, 2, 3, 4, […]]
209:0> a[4]
[1, 2, 3, 4, […]]
210:0> a[4][4]
[1, 2, 3, 4, […]]
211:0> a[4][4][4][4][4][3]
4

have you ever used this technique? can you provide some example code
for us which illustrates any kind of usefulness of this that you can
imagine?

2

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?

3

From: Simon S. [mailto:[email protected]]

207:0> a = [1,2,3,4]

[1, 2, 3, 4]

208:0> a[4] = a

[1, 2, 3, 4, […]]

209:0> a[4]

[1, 2, 3, 4, […]]

210:0> a[4][4]

[1, 2, 3, 4, […]]

211:0> a[4][4][4][4][4][3]

4

have you ever used this technique? can you

provide some example code for us which illustrates

any kind of usefulness of this that you can

imagine?

i am not yet in graphs/game theory but recursion things are good for
research in those fields :slight_smile:

this is just one stupid example,

def sumb(a,i)
return 0 if a[i]==a
a[i]+sumb(a,i+1)
end
=> nil
irb(main):042:0> a
=> [1, 2, 3, 4, […]]
irb(main):043:0> sumb(a,0)
=> 10

i’m just playing w ruby :slight_smile:

kind regards -botp

4

Dido S. wrote:

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
[[[[[…], […], […]], [[[…], […], […]], [[…], […], […]],
[…]], [[…], […], […]]], [[…], […], […]], [[…], […],
[…]]], [[[…], […], […]], [[[…], […], […]], [[…], […],
[…]], [[…], [[…], […], […]], [[…], […], […]]]], [[…],
[…], […]]], [[[…], […], […]], [[…], […], […]], [[[[…],
[…], […]], […], [[…], […], […]]], [[…], […], […]],
[[…], […], […]]]], [[…], […], […]]]

5

On 10/23/07, Simon S. [email protected] 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,
pushdown automaton, linear bounded automaton, or even a Turing
machine) , with each state being represented by an array, the inputs
being indexes into the array, and the values of the array the new
states the machine enters when a particular input is received. This is
the simplest example I could think up off the top of my head, but read
any decent book on algorithms and data structures and you’ll find
hundreds more.

6

[[[[[…], […], […]], [[[…], […], […]], [[…], […], […]],
[…]], [[…], […], […]]], [[…], […], […]], [[…], […],
[…]]], [[[…], […], […]], [[[…], […], […]], [[…], […],
[…]], [[…], [[…], […], […]], [[…], […], […]]]], [[…],
[…], […]]], [[[…], […], […]], [[…], […], […]], [[[[…],
[…], […]], […], [[…], […], […]]], [[…], […], […]],
[[…], […], […]]]], [[…], […], […]]]

so… is this practical because it’s fucking awesome? or not practical
because I’m not making money from it? either way, thanks :smiley:

7

On 23 Oct 2007, at 13:08, Simon S. 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?

It calls Array#[] 5 times if that’s what you mean? But all on the
same Array. It’s turtles all the way down would be another way of
putting it (or one turtle repeated over and over again).

[alexg@powerbook]/Users/alexg/Desktop(31): cat test.rb
a = [1,2,3,4]
a[4] = a

set_trace_func proc {|event,file,line,id,binding,classname|
printf “%8s %s:%-2d %10s %8s\n”,event,file,line,id,classname
if event == “c-call”
}

a[4][4][4][4][0]
[alexg@powerbook]/Users/alexg/Desktop(32): ruby test.rb
c-call test.rb:8 [] Array
c-call test.rb:8 [] Array
c-call test.rb:8 [] Array
c-call test.rb:8 [] Array
c-call test.rb:8 [] Array

4

have you ever used this technique? can you provide some example code
for us which illustrates any kind of usefulness of this that you can
imagine?

I have to say I can’t imagine any practical use (obfuscation
perhaps?), but maybe there are some fun games you can play with it.

Alex G.

Bioinformatics Center
Kyoto University

8

could you provide some code to exemplify this?

9

Eric P. wrote:

I’m impressed, but the name “FSM” raised my expectations.
Is there any way you could construct an FSM, or render it,
so its output looks more like the Flying Spaghetti Monster?

Well, if you use the object_ids, you can construct a graph.

Wolfgang Nádasi-Donner

10

I’m impressed, but the name “FSM” raised my expectations.
Is there any way you could construct an FSM, or render it,
so its output looks more like the Flying Spaghetti Monster?

  • Eric
11

Eric P. wrote:

I’m impressed, but the name “FSM” raised my expectations.
Is there any way you could construct an FSM, or render it,
so its output looks more like the Flying Spaghetti Monster?

This can be a very first step into readability…

class Array
attr_accessor :my_state_name
alias old_inspect inspect
def inspect
if self.my_state_name
(’ /’ + self.my_state_name + ‘/:’ +
old_inspect).gsub(/(]\s*,)\s*/, “\1\n”)
else
old_inspect
end
end
end

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

s0.my_state_name = “Start-End State S0”
s1.my_state_name = “State S1”
s2.my_state_name = “State S2”
s_.my_state_name = “Error State S_”

fsm = [s0, s1, s2, s_]

#… rest of program …

Wolfgang Nádasi-Donner

12

Eric P. wrote:

I’m impressed, but the name “FSM” raised my expectations.
Is there any way you could construct an FSM, or render it,
so its output looks more like the Flying Spaghetti Monster?

I’m afraid I have not been touched by the noodly appendage, and I only
write FSC, Flying Spaghetti Code. :wink: