A community for technology geeks in Lebanon.

You are not logged in.

- Topics: Active • Unanswered

Pages: **1**

**Joe****Member**

In this exercise you have the freedom to chose the type of sequence you want to work with (arrays, lists, vectors, ...) according to the language you're using.

Let's define a "nested sequence" as a sequence where each element can be either:

a value.

a nested sequence

The goal of this exercise is to write a function that will take a nested sequence as input and returns the corresponding "flat" list. For instance:

a = (5, (3, 2), ((5, (3, 2), 4), (2, 1)), 2)

f(a) -> (5, 3, 2, 5, 3, 2, 4, 2, 1, 2)

You should be able to deal with deep nestings. Consider that there is no depth limit.

If your language implements this function, clearly don't use it

**Bonus points**: Don't use a**for**loop.

**Ra8****Member**

In Javascript, return by reference

```
function flatten(arr,i,newA)
{
if(arr.length==i)
return -1;
if(typeof(arr[i])=="object")
{
if(flatten(arr[i],0,newA)==-1)
return flatten(arr,i+1,newA);
}
else
{
newA.push(arr[i]);
return flatten(arr,i+1,newA);
}
}
t=[1,[1,2],[2,3]];
g=[];
flatten(t,0,g);
```

**mesa177****Member**

Matlab:

PS; Yes, it's easier for me to include this run on Octaviz than to explain my final one-liner. It's a simple manipulation of matrices, namely transpose (the ' symbol), column assorting (the (:) symbols), and horizontal concatenation of arrays (the horzcat function). If the code is still not clear, then I'll go through it more thoroughly.

[Edit] Well the one liner isn't that clear, so the code goes like this:

`flat_x=[]; for (i = 1:size(x'(:)',2)) flat_x = horzcat(flat_x,((x'(:))'{i}'(:))'); end`

Where x is any cell matrix.

So, if x is given as:

`x = {1,[2,4,5];3,[6,13;2,6]}`

then the result would be:

`flat_x = [1,2,4,5,3,6,13,2,6]`

Note 1: Flattening nested sequences is an inherent property of Matlab, and that's why I decided to step it up and flatten nested matrices instead.

Note 2: This Matlab one-liner code has a very nice real-life application if you think of it. Consider an RGB image; when imported into Matlab/Octaviz, the image is saved as a cell matrix of the binary matrices R, G, and B which compose the image (think of the RGB image as a 3D matrix where R is 1D, G is another 1D, and B is the final 1D). If the binary entries on these matrices were to be transmitted via a channel (let's say emulated in Simulink), then the entries on the matrices would have to be flattened before transmission. I like this exercise :)

[/Edit]

*Last edited by mesa177 (October 2 2012)*

**Joe****Member**

Working on Python tuples (it can be very easily adapted to other types of sequences), this code takes advantage of the newly introduced yield from syntax.

```
def flatten_gen(s):
if len(s) > 0:
elt=s[0]
if isinstance(elt, tuple):
yield from flatten_gen(elt)
else:
yield elt
yield from flatten_gen(s[1:])
def flatten(s):
return tuple(flatten_gen(s))
```

>>> a = (5, (1, 2, (2, 3), (( 5, 4), 3)), (2, 3), (1, (), (2, 5)))

>>> print(flatten(a))

(5, 1, 2, 2, 3, 5, 4, 3, 2, 3, 1, 2, 5)

**rolf****Member**

In PHP; Nothing fancy, just a recursive function with a foreach loop.

I like how readable the code is :)

```
<?php
$flat_list = $tree = array();
$tree = array(
"one",
array(
"two",
"three",
array(
"four"
),
"five"
),
"six",
"seven",
array(
"eight"
)
);
function descend($into) {
global $flat_list;
if (is_array($into)) {
foreach($into as $item) {
descend($item);
}
} else {
$flat_list[] = $into;
}
}
descend($tree);
print_r($tree);
echo "\r\n";
print_r($flat_list);
?>
```

See it in action:

http://codepad.org/awXfJqCl

Edit: I had to replace all tabs with spaces in the code for it to display properly. Something is very wrong with the code box.

*Last edited by rolf (October 3 2012)*

**Joe****Member**

Haskell's equivalent (to a certain extent) to Python's **yield from** is called **concatMap**.

```
data NestedList a =
Elem a | List [NestedList a]
flatten :: NestedList Int -> [Int]
flatten (Elem x) = [x]
flatten (List x) = concatMap flatten x
```

Pages: **1**