Flatten a list

Flatten a list
You are encouraged to solve this task according to the task description, using any language you may know.

Write a function to flatten the nesting in an arbitrary list of values. Your program should work on the equivalent of this list:

  [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]

Where the correct result would be the list:

   [1, 2, 3, 4, 5, 6, 7, 8]

C.f. Tree traversal

C++

<lang cpp>#include <list>

1. include <boost/any.hpp>

typedef std::list<boost::any> anylist;

void flatten(std::list<boost::any>& list) {

 typedef anylist::iterator iterator;

 iterator current = list.begin();
 while (current != list.end())
 {
   if (current->type() == typeid(anylist))
   {
     iterator next = current;
     ++next;
     list.splice(next, boost::any_cast<anylist&>(*current));
     next = current;
     ++next;
     list.erase(current);
     current = next;
   }
   else
     ++current;
 }

}</lang>

Use example:

Since C++ currently doesn't have nice syntax for initializing lists, this includes a simple parser to create lists of integers and sublists. Also, there's no standard way to output this type of list, so some output code is added as well. <lang cpp>#include <cctype>

1. include <iostream>

// ******************* // * the list parser * // *******************

void skipwhite(char const** s) {

 while (**s && std::isspace((unsigned char)**s))
 {
   ++*s;
 }

}

anylist create_anylist_i(char const** s) {

 anylist result;
 skipwhite(s);
 if (**s != '[')
   throw "Not a list";
 ++*s;
 while (true)
 {
   skipwhite(s);
   if (!**s)
     throw "Error";
   else if (**s == ']')
   {
     ++*s;
     return result;
   }
   else if (**s == '[')
     result.push_back(create_anylist_i(s));
   else if (std::isdigit((unsigned char)**s))
   {
     int i = 0;
     while (std::isdigit((unsigned char)**s))
     {
       i = 10*i + (**s - '0');
       ++*s;
     }
     result.push_back(i);
   }
   else
     throw "Error";

   skipwhite(s);
   if (**s != ',' && **s != ']')
     throw "Error";
   if (**s == ',')
     ++*s;
 }

}

anylist create_anylist(char const* i) {

 return create_anylist_i(&i);

}

// ************************* // * printing nested lists * // *************************

void print_list(anylist const& list);

void print_item(boost::any const& a) {

 if (a.type() == typeid(int))
   std::cout << boost::any_cast<int>(a);
 else if (a.type() == typeid(anylist))
   print_list(boost::any_cast<anylist const&>(a));
 else
   std::cout << "???";

}

void print_list(anylist const& list) {

 std::cout << '[';
 anylist::const_iterator iter = list.begin();
 while (iter != list.end())
 {
   print_item(*iter);
   ++iter;
   if (iter != list.end())
     std::cout << ", ";
 }
 std::cout << ']';

}

// *************************** // * The actual test program * // ***************************

int main() {

 anylist list =
   create_anylist("[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]");
 print_list(list);
 std::cout << "\n";
 flatten(list);
 print_list(list);
 std::cout << "\n";

}</lang> The output of this program is

[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]
[1, 2, 3, 4, 5, 6, 7, 8]

Clojure

The following returns a lazy sequence of the flattened data structure. <lang lisp>(defn flatten [coll]

 (lazy-seq
   (when-let [s  (seq coll)]
     (if (coll? (first s))
       (concat (flatten (first s)) (flatten (next s)))
       (cons (first s) (flatten (next s)))))))</lang>

Common Lisp

<lang lisp>(defun flatten (tree)

 (let ((result '()))
   (labels ((scan (item)
              (if (listp item)
                (map nil #'scan item)
                (push item result))))
     (scan tree))
   (nreverse result)))</lang>

While this is a common homework problem in Common Lisp, it should be noted that it is typically a mistake to use it in a realistic program; it is almost always easier to rewrite the program such that it does not generate the deeply-nested lists in the first place. In particular, note that flattening means that none of the values stored in the nested-list-structure can be a list (a cons or nil) itself. For example, producing and flattening a tree of boolean values would not do the right thing, since false = nil, a list.

E

<lang e>def flatten(nested) {

   def flat := [].diverge()
   def recur(x) {
       switch (x) {
           match list :List { for elem in list { recur(elem) } }
           match other      { flat.push(other) }
       }
   }
   recur(nested)
   return flat.snapshot()

}</lang>

<lang e>? flatten([[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []])

1. value: [1, 2, 3, 4, 5, 6, 7, 8]</lang>

Erlang

There's a standard function (lists:flatten/2) that does it more efficiently, but this is the cleanest implementation you could have; <lang Erlang>flatten([]) -> []; flatten([H|T]) -> flatten(H) ++ flatten(T); flatten(H) -> [H].</lang>

Groovy

List.flatten() is a Groovy built-in that returns a flattened copy of the source list:

<lang groovy>assert [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []].flatten() == [1, 2, 3, 4, 5, 6, 7, 8]</lang>

Haskell

In Haskell we have to interpret this structure as an algebraic data type.

<lang Haskell>import Data.Tree

-- [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] -- implemented as multiway tree:

-- Data.Tree represents trees where nodes have values too, unlike the trees in our problem. -- so we use a list as that value, where a node will have an empty list value, -- and a leaf will have a one-element list value and no subtrees list :: Tree [Int] list = Node [] [

               Node [] [Node [1] []],
               Node [2] [],
               Node [] [
                        Node [] [ Node [3] [],Node [4] []],
                        Node [5] []
                       ],
               Node [] [Node [] [Node [] []]],
               Node [] [Node [] [Node [6] []]],
               Node [7] [],
               Node [8] [],
               Node [] []
               ]

flattenList = concat.flatten</lang> Flattening the list:

*Main> flattenList list
[1,2,3,4,5,6,7,8]

Alternately: <lang haskell>data Tree a = Leaf a | Node [Tree a]

flatten :: Tree a -> [a] flatten (Leaf x) = [x] flatten (Node xs) = concatMap flatten xs

main = print $ flatten $ Node [Node [Leaf 1],

                              Leaf 2,
                              Node [Node [Leaf 3, Leaf 4], Leaf 5],
                              Node [Node [Node []]],
                              Node [Node [Node [Leaf 6]]],
                              Leaf 7,
                              Leaf 8,
                              Node []]

-- output: [1,2,3,4,5,6,7,8]</lang>

J

Solution: <lang j>flatten =: [: ; <S:0</lang>

Example: <lang j> NB. create and display nested noun li

  ]li =.  (<1) ; 2; ((<3;4); 5) ; ((<a:)) ; ((<(<6))) ; 7; 8; <a:

+---+-+-----------+----+-----+-+-+--+ |+-+|2|+-------+-+|+--+|+---+|7|8|++| ||1|| ||+-----+|5|||++|||+-+|| | |||| |+-+| |||+-+-+|| |||||||||6||| | |++| | | ||||3|4||| |||++|||+-+|| | | | | | |||+-+-+|| ||+--+|+---+| | | | | | ||+-----+| || | | | | | | | |+-------+-+| | | | | | +---+-+-----------+----+-----+-+-+--+

  flatten li

1 2 3 4 5 6 7 8</lang>

Java

Works with: Java version 1.5+

<lang java5>import java.util.LinkedList; import java.util.List; import java.util.Arrays;

public class Flatten {

 public static List<Object> flatten(List<?> list){
   List<Object> retVal = new LinkedList<Object>();
   for(Object item:list){
     if(item instanceof List){
       retVal.addAll(flatten((List)item));
     }else{
       retVal.add(item);
     }
   }
   return retVal;
 }

 public static void main(String[] args){
   List<Object> test = Arrays.<Object>asList(
                         Arrays.<Object>asList(1),
                         2,
                         Arrays.<Object>asList(
                           Arrays.<Object>asList(3,4),
                           5
                         ),
                         Arrays.<Object>asList(
                           Arrays.<Object>asList(
                             Arrays.<Object>asList()
                           )
                         ),
                         Arrays.<Object>asList(
                           Arrays.<Object>asList(
                             Arrays.<Object>asList(6)
                           )
                         ),
                         7,
                         8,
                         Arrays.<Object>asList()
                       );

   System.out.println(test);
   System.out.println(flatten(test));
 }

}</lang> Output:

[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]
[1, 2, 3, 4, 5, 6, 7, 8]

JavaScript

Library: Prototype

Works with: a browser

<lang javascript><script type="text/javascript" src="/path/to/prototype.js"></script> <script type="text/javascript">

  var a = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []];

document.write("

before

"); a.each(function(e){document.write("

" + e + " " + typeof(e) + "

")});

  var f = a.flatten();

document.write("

after

"); f.each(function(e){document.write("

" + e + " " + typeof(e) + "

")});

</script></lang> output:

before

1 object
2 number
3,4,5 object
object
6 object
7 number
8 number
object

after

1 number
2 number
3 number
4 number
5 number
6 number
7 number
8 number

Logo

<lang logo>to flatten :l

 if not list? :l [output :l]
 if empty? :l [output []]
 output sentence flatten first :l flatten butfirst :l

end

using a template iterator (map combining results into a sentence)

to flatten :l

 output map.se [ifelse or not list? ? empty? ? [?] [flatten ?]] :l

end

make "a [[1] 2 [[3 4] 5] [[[]]] [[[6]]] 7 8 []] show flatten :a</lang>

OCaml

<lang ocaml># let flatten = List.concat ;; val flatten : 'a list list -> 'a list = <fun>

1. let li = [[1]; 2; [[3;4]; 5]; [[[]]]; [[[6]]]; 7; 8; []] ;;

               ^^^

Error: This expression has type int but is here used with type int list

1. (* use another data which can be accepted by the type system *)

 flatten [[1]; [2; 3; 4]; []; [5; 6]; [7]; [8]] ;;

- : int list = [1; 2; 3; 4; 5; 6; 7; 8]</lang>

Since OCaml is statically typed, it is not possible to have a value that could be both a list and a non-list. Instead, we can use an algebraic datatype:

<lang ocaml># type 'a tree = Leaf of 'a | Node of 'a tree list ;; type 'a tree = Leaf of 'a | Node of 'a tree list

1. let rec flatten = function

    Leaf x -> [x]
  | Node xs -> List.concat (List.map flatten xs) ;;

val flatten : 'a tree -> 'a list = <fun>

1. flatten (Node [Node [Leaf 1]; Leaf 2; Node [Node [Leaf 3; Leaf 4]; Leaf 5]; Node [Node [Node []]]; Node [Node [Node [Leaf 6]]]; Leaf 7; Leaf 8; Node []]) ;;

- : int list = [1; 2; 3; 4; 5; 6; 7; 8]</lang>

Perl

<lang perl>sub flatten {

   map { ref eq 'ARRAY' ? flatten(@$_) : $_ } @_

}

my @lst = ([1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []); print flatten(@lst), "\n";</lang>

Perl 6

Works with: Rakudo version #22 "Thousand Oaks"

<lang perl6>multi flatten (@a) { map { flatten $^x }, @a } multi flatten ($x) { $x }</lang>

PHP

<lang php>/* Note: This code is only for PHP 4.

  It won't work on PHP 5 due to the change in behavior of array_merge(). */

while (array_filter($lst, is_array))

   $lst = call_user_func_array(array_merge, $lst);</lang>

Explanation: while $lst has any elements which are themselves arrays (i.e. $lst is not flat), we merge the elements all together (in PHP 4, array_merge() treated non-array arguments as if they were 1-element arrays; PHP 5 array_merge() no longer allows non-array arguments.), thus flattening the top level of any embedded arrays. Repeat this process until the array is flat.

Recursive

<lang php><?php function flatten($ary) {

   $result = array();
   foreach ($ary as $x) {
       if (is_array($x))
           // append flatten($x) onto $result
           array_splice($result, count($result), 0, flatten($x));
       else
           $result[] = $x;
   }
   return $result;

}

$lst = array(array(1), 2, array(array(3, 4), 5), array(array(array())), array(array(array(6))), 7, 8, array()); var_dump(flatten($lst)); ?></lang>

Non-recursive

Function flat is iterative and flattens the array in-place. <lang php><?php function flat(&$ary) { // argument must be by reference or array will just be copied

   for ($i = 0; $i < count($ary); $i++) {
       while (is_array($ary[$i])) {
           array_splice($ary, $i, 1, $ary[$i]);
       }
   }

}

$lst = array(array(1), 2, array(array(3, 4), 5), array(array(array())), array(array(array(6))), 7, 8, array()); flat($lst); var_dump($lst); ?></lang>

Python

Recursive

Function flatten is recursive and preserves its argument: <lang python>>>> def flatten(lst): return sum( ([x] if type(x) is not list else flatten(x) for x in lst), [] )

>>> lst = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] >>> flatten(lst) [1, 2, 3, 4, 5, 6, 7, 8]</lang>

Non-recursive

Function flat is iterative and flattens the list in-place. It follows the Python idiom of returning None when acting in-place: <lang python>>>> def flat(lst):

   i=0
   while i<len(lst):
       while True:
           try:
               lst[i:i+1] = lst[i]
           except (TypeError, IndexError):
               break
       i += 1
       

>>> lst = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] >>> flat(lst) >>> lst [1, 2, 3, 4, 5, 6, 7, 8]</lang>

R

<lang R>l <- list(list(1), 2, list(list(3, 4), 5), list(list(list())), list(list(list(6))), 7, 8, list()) unlist(l)</lang>

Ruby

flatten is a built-in method of Arrays <lang ruby>flat = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []].flatten p flat # => [1, 2, 3, 4, 5, 6, 7, 8]</lang>

Scheme

<lang scheme>> (define (flatten x)

   (cond ((null? x) '())
         ((not (pair? x)) (list x))
         (else (append (flatten (car x))
                       (flatten (cdr x))))))

> (flatten '((1) 2 ((3 4) 5) ((())) (((6))) 7 8 ())) (1 2 3 4 5 6 7 8)</lang>

Slate

<lang slate>s@(Sequence traits) flatten [

 [| :out | s flattenOn: out] writingAs: s

].

s@(Sequence traits) flattenOn: w@(WriteStream traits) [

 s do: [| :value |
   (value is: s)
     ifTrue: [value flattenOn: w]
     ifFalse: [w nextPut: value]].

].</lang>

Smalltalk

Works with: GNU Smalltalk

<lang smalltalk>OrderedCollection extend [

 flatten [ |f|
   f := OrderedCollection new.
   self do: [ :i |
     i isNumber
       ifTrue: [ f add: i ]
       ifFalse: [ |t|
         t := (OrderedCollection withAll: i) flatten.
         f addAll: t
       ]
   ].
   ^ f
 ]

].

|list| list := OrderedCollection

         withAll: { {1} . 2 . { {3 . 4} . 5 } .
                    {{{}}} . {{{6}}} . 7 . 8 . {} }.

(list flatten) printNl.</lang>

Tcl

<lang tcl>proc flatten list {

   for {set old {}} {$old ne $list} {} {
       set old $list
       set list [join $list]
   }
   return $list

}

puts [flatten {{1} 2 {{3 4} 5} {{{}}} {{{6}}} 7 8 {}}]

1. ===> 1 2 3 4 5 6 7 8</lang>

Note that because lists are not syntactically distinct from strings, it is probably a mistake to use this procedure with real (especially non-numeric) data. Also note that there are no parentheses around the outside of the list when printed; this is just a feature of how Tcl regards lists, and the value is a proper list (it can be indexed into with lindex, iterated over with foreach, etc.)

TI-89 BASIC

There is no nesting of lists or other data structures in TI-89 BASIC, short of using variable names as pointers.