Recursive array

ruby-talk
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?

···

On 10/22/07, Simon Schuster <significants@gmail.com> wrote:

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?

3

# 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

···

From: Simon Schuster [mailto:significants@gmail.com]
#
# 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

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

···

On 23 Oct 2007, at 13:08, Simon Schuster wrote:

On 10/22/07, Simon Schuster <significants@gmail.com> wrote:

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

Bioinformatics Center
Kyoto University

5

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.

···

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?

--
普通じゃないのが当然なら答える私は何ができる？
普通でも普通じゃなくて感じるまま感じることだけをするよ！
http://stormwyrm.blogspot.com

6

Dido Sevilla 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
false
[[[[[...], [...], [...]], [[[...], [...], [...]], [[...], [...], [...]], [...]], [[...], [...], [...]]], [[...], [...], [...]], [[...], [...], [...]]], [[[...], [...], [...]], [[[...], [...], [...]], [[...], [...], [...]], [[...], [[...], [...], [...]], [[...], [...], [...]]]], [[...], [...], [...]]], [[[...], [...], [...]], [[...], [...], [...]], [[[[...], [...], [...]], [...], [[...], [...], [...]]], [[...], [...], [...]], [[...], [...], [...]]]], [[...], [...], [...]]]

···

On 10/23/07, Simon Schuster <significants@gmail.com> wrote:

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

7

could you provide some code to exemplify this?

···

On 10/22/07, Dido Sevilla <dido.sevilla@gmail.com> 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,
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.

--
普通じゃないのが当然なら答える私は何ができる？
普通でも普通じゃなくて感じるまま感じることだけをするよ！
http://stormwyrm.blogspot.com

8

[[[[[...], [...], [...]], [[[...], [...], [...]], [[...], [...], [...]],
[...]], [[...], [...], [...]]], [[...], [...], [...]], [[...], [...],
[...]]], [[[...], [...], [...]], [[[...], [...], [...]], [[...], [...],
[...]], [[...], [[...], [...], [...]], [[...], [...], [...]]]], [[...],
[...], [...]]], [[[...], [...], [...]], [[...], [...], [...]], [[[[...],
[...], [...]], [...], [[...], [...], [...]]], [[...], [...], [...]],
[[...], [...], [...]]]], [[...], [...], [...]]]

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

9

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

10

Eric Promislow 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

···

--
Posted via http://www.ruby-forum.com/\.

11

Eric Promislow 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

···

--
Posted via http://www.ruby-forum.com/\.

12

Eric Promislow 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:

···

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