Unflatten

ruby-talk
1

This is probably a general programming question but I am using Ruby as my
lang of choice hence a post to this group.

I am trying to convert a flat list (array) of tokens into a nested list
(hence the name UNflatten) using a simple rule:
Every token which looks like ‘(’ begins a nested list and the corresponding
’)’ token ends it … in a recursive fashion.
e.g:
[“a”, “(”,“b”, “)”] ==> [“a”,[ “b” ]]
[ “(”, “a”, “(”,“b”, “)”, “)”] ==> [[“a”,[“b”]]]

Of course, I also want a function (reflatten) which traverses the nested
list to generate the original back.
My first attempt looks like this (see code below).

Any suggestions to improve will be highly appreciated.
Right now I don’t care as much for the efficiency as for the ecomony of
expression.
Thanks,
– Shanko

···

def reflatten(list,left = ‘(’, right = ‘)’,accu=[],level = 0)

print level,'<=' if $DEBUG
p list, accu if $DEBUG

return accu if not list

if list.length < 1
    print '.1.' if $DEBUG
    accu  += [right] if level > 0
    return accu
else
    e = list[0]
    if e.type == list.type
        print '.2.' if $DEBUG
        accu = reflatten(e,left,right,accu + [left],level+1)
        reflatten(list[1..-1],left,right,accu,level)
    else
        print '.3.' if $DEBUG
        reflatten(list[1..-1],left,right,accu+[e],level)
    end
end

end

def unflatten(list, left = ‘(’,right = ‘)’,accu = [], level = 0)
print level,’=>’ if $DEBUG
p list,accu if $DEBUG

return accu if list.length < 1

e = list[0]

if e == left
    print '.1.'  if $DEBUG
    unflatten(list[1..-1],left,right,accu << [], level+1)
else
    if e == right
        if (level > 1) and (accu[-2].type == accu.type)
            print '.2.' if $DEBUG
            unflatten(list[1..-1],left,right,accu[0..-3] << (accu[-2] <<

accu[-1]),level-1)
else
print ‘.3.’ if $DEBUG
unflatten(list[1…-1],left,right,accu,level-1)
end
else
if level > 0
print ‘.4.’ if $DEBUG
unflatten(list[1…-1],left,right,accu[0…-2] << accu[-1] +
[e],level)
else
print ‘.5.’ if $DEBUG
unflatten(list[1…-1],left,right,accu+[e],level)
end
end
end

end

if $0 == FILE

s = "( ( ( a ( b ) ( ( c ) d ) ( e ) f ) ) )"
# s = "R ( b ( c ( ( a ( Z ) ) ( k ) ) d ) e ) ( a ( b ) ( c ( d ) ) e )

U ( d e ) B ( f ) Y "
puts s

t = s.split
u = unflatten(t)
p u
puts

r = reflatten(u)
p r
puts

puts r.join(" ")

end

2

Shashank Date wrote:

I am trying to convert a flat list (array) of tokens into a nested list
(hence the name UNflatten) using a simple rule:
Every token which looks like ‘(’ begins a nested list and the corresponding
‘)’ token ends it … in a recursive fashion.
e.g:
[“a”, “(”,“b”, “)”] ==> [“a”,[ “b” ]]
[ “(”, “a”, “(”,“b”, “)”, “)”] ==> [[“a”,[“b”]]]

Of course, I also want a function (reflatten) which traverses the nested
list to generate the original back.

Coincidentally, I wrote an inverse for flatten yesterday. (Well,
actually only a right inverse since flatten is not injective.) What you
are doing isn’t precisely an inverse of Array#flatten, though, which I
guess is why you have reflatten. So this may not be useful to you.

Anyway, it’s called Enumerable#nest. You give it a proc that calculates
the depth of each item, and it returns a nesting of arrays in which each
item has the desired depth. I’m using it to parse strings with
Python-like indentation syntax, but it isn’t limited to strings. It’s
probably not going to help you because, in your case, you can’t
calculate the depth from each object by itself–you have to know the
paren count.

Any suggestions appreciated…

···

module Enumerable
def nest(&compare)
ary = to_a
i = 0
# wrap into Array::Iterator?
items_left = proc { i < ary.size }
get_cur = proc { ary[i] }
go_next = proc { i += 1 }
Enumerable.nest items_left, get_cur, go_next, compare
end

def Enumerable.nest items_left, get_cur, go_next, compare
# should handle compare.arity == 2 like a <=> proc
result = ; item = depth = nil
while items_left
item = get_cur
depth = compare[item]
base_depth ||= depth

  if depth < base_depth
    break
  elsif depth > base_depth
    result << nest(items_left, get_cur, go_next, compare)
  else
    result << item; go_next[]
  end
end
return result

end
end

str = <<END
a
aa
ab
aba
abb
abba
abbaa
abbb
ac
ad
ada
adaa
adb
b
ba
bb
c
ca
END

lines = str.split “\n”
nested = lines.nest { |line| line.scan(/^\s*/)[0].length }
p nested
flat = nested.flatten
p flat
p flat == lines

3

[Shashank Date]:

I am trying to convert a flat list (array) of tokens into a nested list
(hence the name UNflatten) using a simple rule:
Every token which looks like ‘(’ begins a nested list and the corresponding
‘)’ token ends it … in a recursive fashion.
e.g:
[“a”, “(”,“b”, “)”] ==> [“a”,[ “b” ]]
[ “(”, “a”, “(”,“b”, “)”, “)”] ==> [[“a”,[“b”]]]

My suggestions:

def unflatten(list, left=‘(’, right=‘)’)
current =
stack = 

list.each do |x|
    if x == left
        stack << (current << [])
        current = current[-1]
    elsif x == right
        raise "unbalanced" if stack.size == 0
        current = stack.pop
    else
        current << x
    end
end
raise "unbalanced" unless stack.size == 0
return current

end

def reflatten(list, left=‘(’, right=‘)’)
acc =
list.each do |x|
if Array === x
acc << left
acc += reflatten(x, left, right)
acc << right
else
acc << x
end
end
return acc
end

// Niklas

4

Hi,

“Niklas Frykholm” r2d2@acc.umu.se wrote in message
news:slrnafvnam.s4k.r2d2@shaka.acc.umu.se…

[Shashank Date]:

I am trying to convert a flat list (array) of tokens into a nested
list
(hence the name UNflatten) using a simple rule:
Every token which looks like ‘(’ begins a nested list and the
corresponding
‘)’ token ends it … in a recursive fashion.
e.g:
[“a”, “(”,“b”, “)”] ==> [“a”,[ “b” ]]
[ “(”, “a”, “(”,“b”, “)”, “)”] ==> [[“a”,[“b”]]]

My suggestions:

def unflatten(list, left=‘(’, right=‘)’)
current =
stack = 

list.each do |x|
    if x == left
        stack << (current << [])
        current = current[-1]
    elsif x == right
        raise "unbalanced" if stack.size == 0
        current = stack.pop
    else
        current << x
    end
end
raise "unbalanced" unless stack.size == 0
return current

end

Simple but awful solution.

def unflatten(list)
eval list.inspect.gsub(/“(”,/ , ‘[’).gsub(/“)”/ , ‘]’)
end

Park Heesob.

5

Joel VanderWerf wrote:

module Enumerable
def nest(&compare)
…

FWIW, I just realized that a grouping can be done very easily using
#nest:

module Enumerable
def group(&test)
nest { |x| test ? 1 : 0 }
end
end

p [1, 2, “three”, “four”, 5, “six”].group { |x| x.is_a? String }

==> [1, 2, [“three”, “four”], 5, [“six”]]

6

Park Heesob wrote:

Simple but awful solution.

def unflatten(list)
eval list.inspect.gsub(/“(”,/ , ‘[’).gsub(/“)”/ , ‘]’)
end

Park Heesob.

Sometimes it may work, but it’s quite simple to construct more
complicated cases for which it fails.

E.g.:

list = [“"(”,“a”]
unflatten(list)

gives parse error.

Best regards, Christian

7

Excellent suggestions, Joel, I have added them my perosnal “goodies”
library.
And you are right, they do address a different but similar problem.

I am studying your solution and being a newbie it is taking me a while for
it to sink in ;-), but I am getting there.
Thanks again.

“Joel VanderWerf” vjoel@PATH.Berkeley.EDU wrote in message
news:3D013DB0.5811BD55@path.berkeley.edu…

···

Joel VanderWerf wrote:

module Enumerable
def nest(&compare)
…

FWIW, I just realized that a grouping can be done very easily using
#nest:

module Enumerable
def group(&test)
nest { |x| test ? 1 : 0 }
end
end

p [1, 2, “three”, “four”, 5, “six”].group { |x| x.is_a? String }

==> [1, 2, [“three”, “four”], 5, [“six”]]

8

Thanks. BTW, I’ll include #nest and #group in future versions of
“Enumerable Tools” on RAA.

Shashank Date wrote:

···

Excellent suggestions, Joel, I have added them my perosnal “goodies”
library.
And you are right, they do address a different but similar problem.

I am studying your solution and being a newbie it is taking me a while for
it to sink in ;-), but I am getting there.
Thanks again.

“Joel VanderWerf” vjoel@PATH.Berkeley.EDU wrote in message
news:3D013DB0.5811BD55@path.berkeley.edu…

Joel VanderWerf wrote:

module Enumerable
def nest(&compare)
…

FWIW, I just realized that a grouping can be done very easily using
#nest:

module Enumerable
def group(&test)
nest { |x| test ? 1 : 0 }
end
end

p [1, 2, “three”, “four”, 5, “six”].group { |x| x.is_a? String }

==> [1, 2, [“three”, “four”], 5, [“six”]]