[Exercise] Flatten nested sequences

Joe

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.

Ra8

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

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]

Joe

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

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.

Joe

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