• Coding
  • [Exercise] Flatten nested sequences

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)
Notes
  • 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.
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);
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]
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)
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.
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