Flatten a list

From Rosetta Code
Jump to: navigation, search
Task
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

Contents

[edit] ACL2

(defun flatten (tr)
(cond ((null tr) nil)
((atom tr) (list tr))
(t (append (flatten (first tr))
(flatten (rest tr))))))

[edit] ActionScript

function flatten(input:Array):Array {
var output:Array = new Array();
for (var i:uint = 0; i < input.length; i++) {
//typeof returns "object" when applied to arrays. This line recursively evaluates nested arrays,
// although it may break if the array contains objects that are not arrays.
if (typeof input[i]=="object") {
output=output.concat(flatten(input[i]));
} else {
output.push(input[i]);
}
}
return output;
}
 

[edit] Aikido

 
function flatten (list, result) {
foreach item list {
if (typeof(item) == "vector") {
flatten (item, result)
} else {
result.append (item)
}
}
}
 
var l = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]
var newl = []
flatten (l, newl)
 
// print out the nicely formatted result list
print ('[')
var comma = ""
foreach item newl {
print (comma + item)
comma = ", "
}
println("]")
 
 

Output:

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

[edit] Aime

void
show_list(list l)
{
integer i;
text s;
 
o_text("[");
 
s = "";
 
i = 0;
while (i < l_length(l)) {
o_text(s);
if (l_s_integer(l, i)) {
o_integer(l_q_integer(l, i));
} else {
show_list(l_q_list(l, i));
}
s = ", ";
i += 1;
}
 
o_text("]");
}
 
void
flat(list c, list l)
{
integer i;
 
i = 0;
while (i < l_length(l)) {
if (l_s_integer(l, i)) {
lb_p_integer(c, l_q_integer(l, i));
} else {
flat(c, l_q_list(l, i));
}
i += 1;
}
}
 
list
flatten(list l)
{
list c;
 
flat(c, l);
 
return c;
}
 
list
nl(...)
{
integer i;
list l;
 
i = 0;
while (i < count()) {
l_append(l, $i);
i += 1;
}
 
return l;
}
 
integer
main(void)
{
list l;
 
l_set(l, nl(nl(1), 2, nl(nl(3, 4), 5), nl(nl(nl())), nl(nl(nl(6))), 7, 8,
nl()));
 
show_list(l);
o_byte('\n');
 
show_list(flatten(l));
o_byte('\n');
 
return 0;
}

Output:

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

[edit] ALGOL 68

Works with: ALGOL 68 version Revision 1 - no extensions to language used
Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny
Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8-8d

Flattening is built in to all of Algol68's transput routines. The following example also uses widening, where scalars are converted into arrays.

main:(
[][][]INT list = ((1), 2, ((3,4), 5), ((())), (((6))), 7, 8, ());
print((list, new line))
)

Output:

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

[edit] AppleScript

my_flatten({{1}, 2, {{3, 4}, 5}, {{{}}}, {{{6}}}, 7, 8, {}})
 
on my_flatten(aList)
if class of aList is not list then
return {aList}
else if length of aList is 0 then
return aList
else
return my_flatten(first item of aList) & (my_flatten(rest of aList))
end if
end my_flatten
 

[edit] AutoHotkey

Works with: AutoHotkey_L

AutoHotkey doesn't have built in list data type. This examples simulates a list in a tree type object and flattens that tree.

list := object(1, object(1, 1), 2, 2, 3, object(1, object(1, 3, 2, 4)
, 2, 5), 4, object(1, object(1, object(1, object()))), 5
, object(1, object(1, 6)), 6, 7, 7, 8, 9, object())
msgbox % objPrint(list) ; (( 1 ) 2 (( 3 4 ) 5 )(((())))(( 6 )) 7 8 ())
msgbox % objPrint(objFlatten(list)) ; ( 1 2 3 4 5 6 7 8 )
return
 
!r::reload
!q::exitapp
 
objPrint(ast, reserved=0)
{
if !isobject(ast)
return " " ast " "
 
if !reserved
reserved := object("seen" . &ast, 1) ; to keep track of unique objects within top object
 
enum := ast._newenum()
while enum[key, value]
{
if reserved["seen" . &value]
continue ; don't copy repeat objects (circular references)
; string .= key . ": " . objPrint(value, reserved)
string .= objPrint(value, reserved)
}
return "(" string ")"
}
 
 
objFlatten(ast)
{
if !isobject(ast)
return ast
 
flat := object() ; flat object
 
enum := ast._newenum()
while enum[key, value]
{
if !isobject(value)
flat._Insert(value)
else
{
next := objFlatten(value)
loop % next._MaxIndex()
flat._Insert(next[A_Index])
 
}
}
return flat
}

[edit] Bracmat

A list is automatically flattened during evaluation if the items are separated by either commas, plusses, asterisks or white spaces.

On top of that, lists separated with white space, plusses or asterisks have 'nil'-elements removed when evaluated. (nil-elements are empty strings, 0 and 1 respectively.)

On top of that, lists separated with plusses or asterisks have their elements sorted and, if possible, combined when evaluated.

A list that should not be flattened upon evaluation can be separated with dots.

 
( (myList = ((1), 2, ((3,4), 5), ((())), (((6))), 7, 8, ()))
& put$("Unevaluated:")
& lst$myList
& !myList:?myList { the expression !list evaluates myList }
& put$("Flattened:")
& lst$myList
)
 

[edit] Brat

array.prototype.flatten = {
true? my.empty?
{ [] }
{ true? my.first.array?
{ my.first.flatten + my.rest.flatten }
{ [my.first] + my.rest.flatten }
}
}
 
list = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]
p "List: #{list}"
p "Flattened: #{list.flatten}"

[edit] Burlesque

Usually flattening Blocks is done with the Concat command but it only removes one level of nesting therefore it is required to chain Concat calls until the Block does not contain Blocks anymore.

 
blsq ) {{1} 2 {{3 4} 5} {{{}}} {{{6}}} 7 8 {}}{\[}{)to{"Block"==}ay}w!
{1 2 3 4 5 6 7 8}
 

[edit] C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
typedef struct list_t list_t, *list;
struct list_t{
int is_list, ival; /* ival is either the integer value or list length */
list *lst;
};
 
list new_list()
{
list x = malloc(sizeof(list_t));
x->ival = 0;
x->is_list = 1;
x->lst = 0;
return x;
}
 
void append(list parent, list child)
{
parent->lst = realloc(parent->lst, sizeof(list) * (parent->ival + 1));
parent->lst[parent->ival++] = child;
}
 
list from_string(char *s, char **e, list parent)
{
list ret = 0;
if (!parent) parent = new_list();
 
while (*s != '\0') {
if (*s == ']') {
if (e) *e = s + 1;
return parent;
}
if (*s == '[') {
ret = new_list();
ret->is_list = 1;
ret->ival = 0;
append(parent, ret);
from_string(s + 1, &s, ret);
continue;
}
if (*s >= '0' && *s <= '9') {
ret = new_list();
ret->is_list = 0;
ret->ival = strtol(s, &s, 10);
append(parent, ret);
continue;
}
s++;
}
 
if (e) *e = s;
return parent;
}
 
void show_list(list l)
{
int i;
if (!l) return;
if (!l->is_list) {
printf("%d", l->ival);
return;
}
 
printf("[");
for (i = 0; i < l->ival; i++) {
show_list(l->lst[i]);
if (i < l->ival - 1) printf(", ");
}
printf("]");
}
 
list flatten(list from, list to)
{
int i;
list t;
 
if (!to) to = new_list();
if (!from->is_list) {
t = new_list();
*t = *from;
append(to, t);
} else
for (i = 0; i < from->ival; i++)
flatten(from->lst[i], to);
return to;
}
 
void delete_list(list l)
{
int i;
if (!l) return;
if (l->is_list && l->ival) {
for (i = 0; i < l->ival; i++)
delete_list(l->lst[i]);
free(l->lst);
}
 
free(l);
}
 
int main()
{
list l = from_string("[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []", 0, 0);
 
printf("Nested: ");
show_list(l);
printf("\n");
 
list flat = flatten(l, 0);
printf("Flattened: ");
show_list(flat);
 
/* delete_list(l); delete_list(flat); */
return 0;
}
output
Nested: [[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]
Flattened: [1, 2, 3, 4, 5, 6, 7, 8]

[edit] C++

#include <list>
#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));
current = list.erase(current);
}
else
++current;
}
}

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.

#include <cctype>
#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";
}

The output of this program is

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

[edit] C#

Works with: C# version 3+

Actual Workhorse code

 
using System;
using System.Collections;
using System.Linq;
 
namespace RosettaCodeTasks
{
static class FlattenList
{
public static ArrayList Flatten(this ArrayList List)
{
ArrayList NewList = new ArrayList ( );
 
NewList.AddRange ( List );
 
while ( NewList.OfType<ArrayList> ( ).Count ( ) > 0 )
{
int index = NewList.IndexOf ( NewList.OfType<ArrayList> ( ).ElementAt ( 0 ) );
ArrayList Temp = (ArrayList)NewList[index];
NewList.RemoveAt ( index );
NewList.InsertRange ( index, Temp );
}
 
return NewList;
}
}
}
 

Method showing population of arraylist and usage of flatten method

 
using System;
using System.Collections;
 
namespace RosettaCodeTasks
{
class Program
{
static void Main ( string[ ] args )
{
 
ArrayList Parent = new ArrayList ( );
Parent.Add ( new ArrayList ( ) );
((ArrayList)Parent[0]).Add ( 1 );
Parent.Add ( 2 );
Parent.Add ( new ArrayList ( ) );
( (ArrayList)Parent[2] ).Add ( new ArrayList ( ) );
( (ArrayList)( (ArrayList)Parent[2] )[0] ).Add ( 3 );
( (ArrayList)( (ArrayList)Parent[2] )[0] ).Add ( 4 );
( (ArrayList)Parent[2] ).Add ( 5 );
Parent.Add ( new ArrayList ( ) );
( (ArrayList)Parent[3] ).Add ( new ArrayList ( ) );
( (ArrayList)( (ArrayList)Parent[3] )[0] ).Add ( new ArrayList ( ) );
Parent.Add ( new ArrayList ( ) );
( (ArrayList)Parent[4] ).Add ( new ArrayList ( ) );
( (ArrayList)( (ArrayList)Parent[4] )[0] ).Add ( new ArrayList ( ) );
 
( (ArrayList)( (ArrayList)( (ArrayList)( (ArrayList)Parent[4] )[0] )[0] ) ).Add ( 6 );
Parent.Add ( 7 );
Parent.Add ( 8 );
Parent.Add ( new ArrayList ( ) );
 
 
foreach ( Object o in Parent.Flatten ( ) )
{
Console.WriteLine ( o.ToString ( ) );
}
}
 
}
}
 
 
Works with: C# version 4+
 
public static class Ex {
public static List<object> Flatten(this List<object> list) {
 
var result = new List<object>();
foreach (var item in list) {
if (item is List<object>) {
result.AddRange(Flatten(item as List<object>));
} else {
result.Add(item);
}
}
return result;
}
public static string Join<T>(this List<T> list, string glue) {
return string.Join(glue, list.Select(i => i.ToString()).ToArray());
}
}
 
class Program {
 
static void Main(string[] args) {
var list = new List<object>{new List<object>{1}, 2, new List<object>{new List<object>{3,4}, 5}, new List<object>{new List<object>{new List<object>{}}}, new List<object>{new List<object>{new List<object>{6}}}, 7, 8, new List<object>{}};
 
Console.WriteLine("[" + list.Flatten().Join(", ") + "]");
Console.ReadLine();
}
}
 

[edit] Clojure

The following returns a lazy sequence of the flattened data structure.

(defn flatten [coll]
(lazy-seq
(when-let [s (seq coll)]
(if (coll? (first s))
(concat (flatten (first s)) (flatten (rest s)))
(cons (first s) (flatten (rest s)))))))

The built-in flatten is implemented as:

(defn flatten [x]
(filter (complement sequential?)
(rest (tree-seq sequential? seq x))))

[edit] CoffeeScript

 
flatten = (arr) ->
arr.reduce ((xs, el) ->
if Array.isArray el
xs.concat flatten el
else
xs.concat [el]), []
 
# test
list = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]
console.log flatten list
 

Ouput:

 
> coffee foo.coffee
[ 1, 2, 3, 4, 5, 6, 7, 8 ]
 

[edit] Common Lisp

(defun flatten (structure)
(cond ((null structure) nil)
((atom structure) (list structure))
(t (mapcan #'flatten structure))))

or, from Paul Graham's OnLisp,

 
(defun flatten (ls)
(labels (
(mklist (x) (if (listp x) x (list x)))
)
(mapcan #'(lambda (x) (if (atom x) (mklist x) (flatten x))) ls)))
 

Note that since, in common lisp, the empty list, boolean false and nil are the same thing, a tree of nil values cannot be flattened; they will disappear.

A third version that is recursive, imperative, and reasonably fast.

(defun flatten (obj)
(let (result)
(labels ((grep (obj)
(cond ((null obj))
((atom obj) (push obj result))
(t (grep (rest obj))
(grep (first obj))))))
(grep obj)
result)))

The following version is tail recursive and functional.

(defun flatten (x &optional stack out)
(cond ((consp x) (flatten (rest x) (cons (first x) stack) out))
(x (flatten (first stack) (rest stack) (cons x out)))
(stack (flatten (first stack) (rest stack) out))
(t out)))

The next version is imperative, iterative and does not make use of a stack. It is faster than the versions given above.

(defun flatten (obj)
(do* ((result (list obj))
(node result))
((null node) (delete nil result))
(cond ((consp (car node))
(when (cdar node) (push (cdar node) (cdr node)))
(setf (car node) (caar node)))
(t (setf node (cdr node))))))

The above implementations of flatten give the same output on nested proper lists.

Output:
CL-USER> (flatten '((1) 2 ((3 4) 5) ((())) (((6))) 7 8 ()))
(1 2 3 4 5 6 7 8)

It should be noted that there are several choices that can be made when implementing flatten in common lisp:

-- should it work on dotted pairs?

-- should it work with non-nil atoms, presumably returning the atom or a copy of the atom?

-- when it comes to nil, should it be considered as an empty list and removed, or should it be considered as an atom and preserved?

So there are in fact several slightly different functions that correspond to flatten in common lisp. They may

-- collect all atoms, including nil,

-- collect all atoms in the car of the cons cells,

-- collect all atoms which are not in the cdr of a cell,

-- collect all non-nil atoms.

Which version is suitable for a given problem depends of course on the nature of the problem.

[edit] D

Instead of a Java-like class-based version, this version minimizes heap activity using a tagged union.

import std.stdio, std.algorithm, std.conv, std.range;
 
struct TreeList(T) {
union { // A tagged union
TreeList[] arr; // it's a node
T data; // It's a leaf.
}
bool isArray = true; // = Contains an arr on default.
 
static TreeList opCall(A...)(A items) pure nothrow {
TreeList result;
 
foreach (i, el; items)
static if (is(A[i] == T)) {
TreeList item;
item.isArray = false;
item.data = el;
result.arr ~= item;
} else
result.arr ~= el;
 
return result;
}
 
string toString() const pure {
return isArray ? arr.text : data.text;
}
}
 
T[] flatten(T)(in TreeList!T t) pure nothrow {
if (t.isArray)
return t.arr.map!flatten.join;
else
return [t.data];
}
 
void main() {
alias TreeList!int L;
static assert(L.sizeof == 12);
auto l = L(L(1), 2, L(L(3,4), 5), L(L(L())), L(L(L(6))),7,8,L());
l.writeln;
l.flatten.writeln;
}
Output:
[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]
[1, 2, 3, 4, 5, 6, 7, 8]

[edit] With an Algebraic Data Type

A shorter and more cryptic version.

import std.stdio, std.variant, std.range, std.algorithm;
 
alias T = Algebraic!(int, This[]);
 
int[] flatten(T t) {
return t.peek!int ? [t.get!int] : t.get!(T[])().map!flatten.join;
}
 
void main() {
T([T([ T(1) ]),
T(2),
T([ T([ T(3), T(4) ]), T(5) ]),
T([ T([ T( T[].init ) ]) ]),
T([ T([ T([ T(6) ]) ]) ]),
T(7),
T(8),
T( T[].init )
]).flatten.writeln;
}
Output:
[1, 2, 3, 4, 5, 6, 7, 8]

[edit] Déjà Vu

(flatten):
for i in copy:
i
if = :list type dup:
(flatten)
 
flatten l:
[ (flatten) l ]
 
 
!. flatten [ [ 1 ] 2 [ [ 3 4 ] 5 ] [ [ [] ] ] [ [ [ 6 ] ] ] 7 8 [] ]
Output:
[ 1 2 3 4 5 6 7 8 ]

[edit] 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()
}
? flatten([[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []])
# value: [1, 2, 3, 4, 5, 6, 7, 8]

[edit] Ela

This implementation can flattern any given list:

xs =  [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]
 
flat = flat' []
where flat' n [] = n
flat' n (x::xs)
| x is List = flat' (flat' n xs) x
| else = x :: flat' n xs
 
flat xs

Output:

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

An alternative solution:

flat [] = [] 
flat (x::xs)
| x is List = flat x ++ flat xs
| else = x :: flat xs

[edit] Elixir

 
defmodule RC do
def flatten([]), do: []
def flatten([h|t]), do: flatten(h) ++ flatten(t)
def flatten(h), do: [h]
end
 
list = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]
 
# Our own implementation
IO.inspect RC.flatten(list)
# Library function
IO.inspect List.flatten(list)
 

Output:

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

[edit] Emacs Lisp

 
(defun flatten (mylist)
(cond
((null mylist) nil)
((atom mylist) (list mylist))
(t
(append (flatten (car mylist)) (flatten (cdr mylist))))))
 

[edit] Erlang

There's a standard function (lists:flatten/1) that does it more efficiently, but this is the cleanest implementation you could have;

flatten([]) -> [];
flatten([H|T]) -> flatten(H) ++ flatten(T);
flatten(H) -> [H].

[edit] Euphoria

Works with: Euphoria version 4.0.0
sequence a = {{1}, 2, {{3, 4}, 5}, {{{}}}, {{{6}}}, 7, 8, {}}
 
function flatten( object s )
sequence res = {}
if sequence( s ) then
for i = 1 to length( s ) do
sequence c = flatten( s[ i ] )
if length( c ) > 0 then
res &= c
end if
end for
else
if length( s ) > 0 then
res = { s }
end if
end if
return res
end function
 
? a
? flatten(a)

Output

{
  {1},
  2,
  {
    {3,4},
    5
  },
  {
    {{}}
  },
  {
    {
      {6}
    }
  },
  7,
  8,
  {}
}
{1,2,3,4,5,6,7,8}

[edit] F#

As with Haskell and OCaml we have to define our list as an algebraic data type, to be strongly typed:

type 'a ll =
| I of '
a // leaf Item
| L of 'a ll list // ' <- confine the syntax colouring confusion
 
let rec flatten = function
| [] -> []
| (I x)::y -> x :: (flatten y)
| (L x)::y -> List.append (flatten x) (flatten y)
 
printfn "%A" (flatten [L([I(1)]); I(2); L([L([I(3);I(4)]); I(5)]); L([L([L([])])]); L([L([L([I(6)])])]); I(7); I(8); L([])])
 
// -> [1; 2; 3; 4; 5; 6; 7; 8]

An alternative approach with List.collect and the same data type. Note that flatten operates on all deepLists (ll) and atoms (I) are "flatened" to lists.

 
let rec flatten =
function
| I x -> [x]
| L x -> List.collect flatten x
 
printfn "%A" (flatten (L [L([I(1)]); I(2); L([L([I(3);I(4)]); I(5)]); L([L([L([])])]); L([L([L([I(6)])])]); I(7); I(8); L([])]))
 
// -> [1; 2; 3; 4; 5; 6; 7; 8]
 

[edit] Factor

   USE: sequences.deep
   ( scratchpad ) { { 1 } 2 { { 3 4 } 5 } { { { } } } { { { 6 } } } 7 8 { } } flatten .
   { 1 2 3 4 5 6 7 8 }

[edit] Fantom

 
class Main
{
// uses recursion to flatten a list
static List myflatten (List items)
{
List result := [,]
items.each |item|
{
if (item is List)
result.addAll (myflatten(item))
else
result.add (item)
}
return result
}
 
public static Void main ()
{
List sample := [[1], 2, [[3,4], 5], [[[,]]], [[[6]]], 7, 8, [,]]
// there is a built-in flatten method for lists
echo ("Flattened list 1: " + sample.flatten)
// or use the function 'myflatten'
echo ("Flattened list 2: " + myflatten (sample))
}
}
 

[edit] Fortran

 
! input  : [[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]
! flatten : [1, 2, 3, 4, 5, 6, 7, 8 ]
 
module flat
implicit none
 
type n
integer :: a
type(n), dimension(:), pointer :: p => null()
logical :: empty = .false.
end type
 
contains
 
recursive subroutine del(this)
type(n), intent(inout) :: this
integer :: i
if (associated(this%p)) then
do i = 1, size(this%p)
call del(this%p(i))
end do
end if
end subroutine
 
function join(xs) result (r)
type(n), dimension(:), target :: xs
type(n) :: r
integer :: i
if (size(xs)>0) then
allocate(r%p(size(xs)), source=xs)
do i = 1, size(xs)
r%p(i) = xs(i)
end do
else
r%empty = .true.
end if
end function
 
recursive subroutine flatten1(x,r)
integer, dimension (:), allocatable, intent(inout) :: r
type(n), intent(in) :: x
integer, dimension (:), allocatable :: tmp
integer :: i
if (associated(x%p)) then
do i = 1, size(x%p)
call flatten1(x%p(i), r)
end do
elseif (.not. x%empty) then
allocate(tmp(size(r)+1))
tmp(1:size(r)) = r
tmp(size(r)+1) = x%a
call move_alloc(tmp, r)
end if
end subroutine
 
function flatten(x) result (r)
type(n), intent(in) :: x
integer, dimension(:), allocatable :: r
allocate(r(0))
call flatten1(x,r)
end function
 
recursive subroutine show(x)
type(n) :: x
integer :: i
if (x%empty) then
write (*, "(a)", advance="no") "[]"
elseif (associated(x%p)) then
write (*, "(a)", advance="no") "["
do i = 1, size(x%p)
call show(x%p(i))
if (i<size(x%p)) then
write (*, "(a)", advance="no") ", "
end if
end do
write (*, "(a)", advance="no") "]"
else
write (*, "(g0)", advance="no") x%a
end if
end subroutine
 
function fromString(line) result (r)
character(len=*) :: line
type (n) :: r
type (n), dimension(:), allocatable :: buffer, buffer1
integer, dimension(:), allocatable :: stack, stack1
integer :: sp,i0,i,j, a, cur, start
character :: c
 
if (.not. allocated(buffer)) then
allocate (buffer(5)) ! will be re-allocated if more is needed
end if
if (.not. allocated(stack)) then
allocate (stack(5))
end if
 
sp = 1; cur = 1; i = 1
do
if ( i > len_trim(line) ) exit
c = line(i:i)
if (c=="[") then
if (sp>size(stack)) then
allocate(stack1(2*size(stack)))
stack1(1:size(stack)) = stack
call move_alloc(stack1, stack)
end if
stack(sp) = cur; sp = sp + 1; i = i+1
elseif (c=="]") then
sp = sp - 1; start = stack(sp)
r = join(buffer(start:cur-1))
do j = start, cur-1
call del(buffer(j))
end do
buffer(start) = r; cur = start+1; i = i+1
elseif (index(" ,",c)>0) then
i = i + 1; continue
elseif (index("-123456789",c)>0) then
i0 = i
do
if ((i>len_trim(line)).or. &
index("1234567890",line(i:i))==0) then
read(line(i0:i-1),*) a
if (cur>size(buffer)) then
allocate(buffer1(2*size(buffer)))
buffer1(1:size(buffer)) = buffer
call move_alloc(buffer1, buffer)
end if
buffer(cur) = n(a); cur = cur + 1; exit
else
i = i+1
end if
end do
else
stop "input corrupted"
end if
end do
end function
end module
 
program main
use flat
type (n) :: x
x = fromString("[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]")
write(*, "(a)", advance="no") "input  : "
call show(x)
print *
write (*,"(a)", advance="no") "flatten : ["
write (*, "(*(i0,:,:', '))", advance="no") flatten(x)
print *, "]"
end program
 

[edit] Frink

 
a = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]
println[flatten[a]]
 

[edit] GAP

Flat([[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]);

[edit] Go

package main
 
import "fmt"
 
func list(s ...interface{}) []interface{} {
return s
}
 
func main() {
s := list(list(1),
2,
list(list(3, 4), 5),
list(list(list())),
list(list(list(6))),
7,
8,
list(),
)
fmt.Println(s)
fmt.Println(flatten(s))
}
 
func flatten(s []interface{}) (r []int) {
for _, e := range s {
switch i := e.(type) {
case int:
r = append(r, i)
case []interface{}:
r = append(r, flatten(i)...)
}
}
return
}

Output:

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

In the code above, flatten uses an easy-to-read type switch to extract ints and return an int slice. The version below is generalized to return a flattened slice of interface{} type, which can of course refer to objects of any type, and not just int. Also, just to show a variation in programming style, a type assertion is used rather than a type switch.

func flatten(s []interface{}) (r []interface{}) {
for _, e := range s {
if i, ok := e.([]interface{}); ok {
r = append(r, flatten(i)...)
} else {
r = append(r, e)
}
}
return
}

[edit] Groovy

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

assert [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []].flatten() == [1, 2, 3, 4, 5, 6, 7, 8]

[edit] Haskell

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

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

Flattening the list:

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

Alternately:

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]

Yet another choice, custom data structure, efficient lazy flattening:

(This is unnecessary; since Haskell is lazy, the previous solution will only do just as much work as necessary for each element that is requested from the resulting list.)

data NestedList a = NList [NestedList a] | Entry a
 
flatten :: NestedList a -> [a]
flatten nl = flatten' nl []
where
-- By passing through a list which the results will be preprended to we allow efficient lazy evaluation
flatten'
:: NestedList a -> [a] -> [a]
flatten' (Entry a) cont = a:cont
flatten'
(NList entries) cont = foldr flatten' cont entries
 
example :: NestedList Int
example = NList [ NList [Entry 1], Entry 2, NList [NList [Entry 3, Entry 4], Entry 5], NList [NList [NList []]], NList [ NList [ NList [Entry 6]]], Entry 7, Entry 8, NList []]
 
main :: IO ()
main = print $ flatten example
 
-- output [1,2,3,4,5,6,7,8]

[edit] Icon and Unicon

The following procedure solves the task using a string representation of nested lists and cares not if the list is well formed or not.

link strings           # for compress,deletec,pretrim
 
procedure sflatten(s) # uninteresting string solution
return pretrim(trim(compress(deletec(s,'[ ]'),',') ,','),',')
end

The solution uses several procedures from strings in the IPL

This procedure is more in the spirit of the task handling actual lists rather than representations. It uses a recursive approach using some of the built-in list manipulation functions and operators.

procedure flatten(L)   # in the spirt of the problem  a structure
local l,x
 
l := []
every x := !L do
if type(x) == "list" then l |||:= flatten(x)
else put(l,x)
return l
end

Finally a demo routine to drive these and a helper to show how it works.

procedure main()
write(sflatten(" [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]"))
writelist(flatten( [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]))
end
 
procedure writelist(L)
writes("[")
every writes(" ",image(!L))
write(" ]")
return
end

[edit] Ioke

iik> [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] flatten
[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] flatten
+> [1, 2, 3, 4, 5, 6, 7, 8]

[edit] J

Solution:

flatten =: [: ; <S:0

Example:

   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

Alternative Solution:
The previous solution can be generalized to flatten the nesting and shape for a list of arbitrary values that include arrays of any rank:

flatten2 =: [: ; <@,S:0

Example:

   ]li2 =.  (<1) ; 2; ((<3;4); 5 + i.3 4) ; ((<a:)) ; ((<(<17))) ; 18; 19; <a:
+---+-+---------------------+----+------+--+--+--+
|+-+|2|+-------+-----------+|+--+|+----+|18|19|++|
||1|| ||+-----+| 5 6 7 8|||++|||+--+|| | ||||
|+-+| |||+-+-+|| 9 10 11 12|||||||||17||| | |++|
| | ||||3|4|||13 14 15 16|||++|||+--+|| | | |
| | |||+-+-+|| ||+--+|+----+| | | |
| | ||+-----+| || | | | | |
| | |+-------+-----------+| | | | | |
+---+-+---------------------+----+------+--+--+--+
 
flatten2 li
1 2 3 4 5 6 7 8
flatten2 li2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Notes: The primitive ; removes one level of nesting.

<S:0 takes an arbitrarily nested list and puts everything one level deep.

[: is glue, here.

We do not use ; by itself because it requires that all of the contents be the same type and nested items have a different type from unnested items.

We do not use ]S:0 (which puts everything zero levels deep) because it assembles its results as items of a list, which means that short items will be padded to be equal to the largest items, and that is not what we would want here (we do not want the empty item to be padded with a fill element).

[edit] Java

Works with: Java version 1.5+

The flatten method was overloaded for better separation of concerns. On the first one you can pass any List and get it flat into a LinkedList implementation. On the other one you can pass any List implementation you like for both lists.

Note that both implementations can only put the result into type List<Object>. We cannot type-safely put the result into a generic type List<T> because there is no way to enforce that the original list contains elements of "type T or lists of elements which are T or further lists..."; there is no generic type parameter that will express that restriction. Since we must accept lists of any elements as an argument, we can only safely put them in a List<Object>.

Actual Workhorse code

import java.util.LinkedList;
import java.util.List;
 
 
public final class FlattenUtil {
 
public static List<Object> flatten(List<?> list) {
List<Object> retVal = new LinkedList<Object>();
flatten(list, retVal);
return retVal;
}
 
public static void flatten(List<?> fromTreeList, List<Object> toFlatList) {
for (Object item : fromTreeList) {
if (item instanceof List<?>) {
flatten((List<?>) item, toFlatList);
} else {
toFlatList.add(item);
}
}
}
}

Method showing population of the test List and usage of flatten method.

import static java.util.Arrays.asList;
import java.util.List;
 
public final class FlattenTestMain {
 
public static void main(String[] args) {
List<Object> treeList = a(a(1), 2, a(a(3, 4), 5), a(a(a())), a(a(a(6))), 7, 8, a());
List<Object> flatList = FlattenUtil.flatten(treeList);
System.out.println(treeList);
System.out.println("flatten: " + flatList);
}
 
private static List<Object> a(Object... a) {
return asList(a);
}
}

Output:

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

[edit] JavaScript

[edit] ES5

function flatten(list) {
return list.reduce(function (acc, val) {
return acc.concat(val.constructor === Array ? flatten(val) : val);
}, []);
}

[edit] ES6

let flatten = list => list.reduce(
(a, b) => a.concat(Array.isArray(b) ? flatten(b) : b), []
);

Result is always:

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

[edit] jq

Recent (1.4+) versions of jq include the following flatten filter:
def flatten:
reduce .[] as $i
([];
if $i | type == "array" then . + ($i | flatten)
else . + [$i]
end);
Example:
 
[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] | flatten
[1,2,3,4,5,6,7,8]

[edit] Julia

Julia auto-flattens nested arrays of this form

julia> t = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]
8-element Int32 Array:
1
2
3
4
5
6
7
8

Arrays of type Any can be nested. They are denoted with {}. Here is a slow recursive version.

flat(A) =  [[isa(x,Array)? flat(x): x for x in A]...]

The following high-level version is notably faster.

flat(A) = mapreduce(x->isa(x,Array)? flat(x): x, vcat, A)

An iterative recursive version that is even faster.

function flat(A)
result = {}
grep(a) = for x in a
isa(x,Array) ? grep(x) : push!(result,x)
end
grep(A)
result
end
 
Output:
julia> show(flat( {{1}, 2, {{3,4}, 5}, {{{}}}, {{{6}}}, 7, 8, {}} ))
{1,2,3,4,5,6,7,8}

[edit] K

In K, join is: , and reduce/fold (called "over") is: /. With a monadic argument (as ,/ is), over repeats application until reaching a fixed-point.

So to flatten a list of arbitrary depth, you can join-over-over, or reduce a list with a function that reduces a list with a join function:

,//((1); 2; ((3;4); 5); ((())); (((6))); 7; 8; ())


[edit] Lasso

Lasso Delve is a Lasso utility method explicitly for handling embedded arrays. With one array which contain other arrays, delve allows you to treat one array as a single series of elements, thus enabling easy access to an entire tree of values. www.lassosoft.com/lassoDocs/languageReference/obj/delve Lasso reference on Delve

local(original = json_deserialize('[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]'))
 
#original
'<br />'
(with item in delve(#original)
select #item) -> asstaticarray
array(array(1), 2, array(array(3, 4), 5), array(array(array())), array(array(array(6))), 7, 8, array())
staticarray(1, 2, 3, 4, 5, 6, 7, 8)

[edit] LFE

 
> (: lists flatten '((1) 2 ((3 4) 5) ((())) (((6))) 7 8 ()))
(1 2 3 4 5 6 7 8)
 

[edit] Logtalk

flatten(List, Flatted) :-
flatten(List, [], Flatted).
 
flatten(Var, Tail, [Var| Tail]) :-
var(Var),
!.
flatten([], Flatted, Flatted) :-
!.
flatten([Head| Tail], List, Flatted) :-
!,
flatten(Tail, List, Aux),
flatten(Head, Aux, Flatted).
flatten(Head, Tail, [Head| Tail]).

[edit] Lua

function flatten(list)
if type(list) ~= "table" then return {list} end
local flat_list = {}
for _, elem in ipairs(list) do
for _, val in ipairs(flatten(elem)) do
flat_list[#flat_list + 1] = val
end
end
return flat_list
end
 
test_list = {{1}, 2, {{3,4}, 5}, {{{}}}, {{{6}}}, 7, 8, {}}
 
print(table.concat(flatten(test_list), ","))

[edit]

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


[edit] Maple

This can be accomplished using the Flatten command from the ListTools, or with a custom recursive procedure.

 
L := [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]:
 
with(ListTools):
 
Flatten(L);
 

Output:

                          [1, 2, 3, 4, 5, 6, 7, 8]
 
flatten := proc(x)
`if`(type(x,'list'),seq(procname(i),i = x),x);
end proc:
 
L := [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]:
 
[flatten(L)];
 

Output:

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

[edit] Mathematica

Flatten[{{1}, 2, {{3, 4}, 5}, {{{}}}, {{{6}}}, 7, 8, {}}]

[edit] Maxima

flatten([[[1, 2, 3], 4, [5, [6, 7]], 8], [[9, 10], 11], 12]);
/* [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] */

[edit] Mirah

import java.util.ArrayList
import java.util.List
import java.util.Collection
 
def flatten(list: Collection)
flatten(list, ArrayList.new)
end
def flatten(source: Collection, result: List)
 
source.each do |x|
if x.kind_of?(Collection)
flatten(Collection(x), result)
else
result.add(x)
result # if branches must return same type
end
end
result
end
 
# creating a list-of-list-of-list fails currently, so constructor calls are needed
source = [[1], 2, [[3, 4], 5], [[ArrayList.new]], [[[6]]], 7, 8, ArrayList.new]
 
puts flatten(source)

[edit] NewLISP

> (flat '((1) 2 ((3 4) 5) ((())) (((6))) 7 8 ()))
(1 2 3 4 5 6 7 8)
 

[edit] Nimrod

type
TreeList[T] = ref TTreeList[T]
TTreeList[T] = object
case isLeaf: bool
of true: data: T
of false: list: seq[TreeList[T]]
 
proc L[T](list: varargs[TreeList[T]]): TreeList[T] =
var s: seq[TreeList[T]] = @[]
for x in list: s.add x
TreeList[T](isLeaf: false, list: s)
 
proc N[T](data: T): TreeList[T] =
TreeList[T](isLeaf: true, data: data)
 
proc `$`[T](n: TreeList[T]): string =
if n.isLeaf: result = $n.data
else:
result = "["
for i, x in n.list:
if i > 0: result.add ", "
result.add($x)
result.add "]"
 
proc flatten[T](n: TreeList[T]): seq[T] =
if n.isLeaf: result = @[n.data]
else:
result = @[]
for x in n.list:
result.add flatten x
 
var x = L(L(N 1), N 2, L(L(N 3, N 4), N 5), L(L(L[int]())), L(L(L(N 6))), N 7, N 8, L[int]())
echo x
echo flatten(x)

Output:

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

[edit] Objective-C

Works with: Cocoa
#import <Foundation/Foundation.h>
 
@interface NSArray (FlattenExt)
@property (nonatomic, readonly) NSArray *flattened;
@end
 
@implementation NSArray (FlattenExt)
-(NSArray *) flattened {
NSMutableArray *flattened = [[NSMutableArray alloc] initWithCapacity:self.count];
 
for (id object in self) {
if ([object isKindOfClass:[NSArray class]])
[flattened addObjectsFromArray:((NSArray *)object).flattened];
else
[flattened addObject:object];
}
 
return [flattened autorelease];
}
@end
 
int main() {
@autoreleasepool {
NSArray *p = @[
@[ @1 ],
@2,
@[ @[@3, @4], @5],
@[ @[ @[ ] ] ],
@[ @[ @[ @6 ] ] ],
@7,
@8,
@[ ] ];
 
for (id object in unflattened.flattened)
NSLog(@"%@", object);
 
}
 
return 0;
}

[edit] OCaml

# let flatten = List.concat ;;
val flatten : 'a list list -> 'a list = <fun>
 
# let li = [[1]; 2; [[3;4]; 5]; [[[]]]; [[[6]]]; 7; 8; []] ;;
^^^
Error: This expression has type int but is here used with type int list
 
# (* 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]

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:

# type 'a tree = Leaf of 'a | Node of 'a tree list ;;
type 'a tree = Leaf of 'a | Node of 'a tree list
 
# let rec flatten = function
Leaf x -> [x]
| Node xs -> List.concat (List.map flatten xs) ;;
val flatten : 'a tree -> 'a list = <fun>
 
# 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]

[edit] Oz

Oz has a standard library function "Flatten":

{Show {Flatten [[1] 2 [[3 4] 5] [[nil]] [[[6]]] 7 8 nil]}}

A simple, non-optimized implementation could look like this:

fun {Flatten2 Xs}
case Xs of nil then nil
[] X|Xr then
{Append {Flatten2 X} {Flatten2 Xr}}
else [Xs]
end
end
 

[edit] ooRexx

 
sub1 = .array~of(1)
sub2 = .array~of(3, 4)
sub3 = .array~of(sub2, 5)
sub4 = .array~of(.array~of(.array~new))
sub5 = .array~of(.array~of(.array~of(6)))
sub6 = .array~new
 
-- final list construction
list = .array~of(sub1, 2, sub3, sub4, sub5, 7, 8, sub6)
 
-- flatten
flatlist = flattenList(list)
 
say "["flatlist~toString("line", ", ")"]"
 
::routine flattenList
use arg list
-- we could use a list or queue, but let's just use an array
accumulator = .array~new
 
-- now go to the recursive processing version
call flattenSublist list, accumulator
 
return accumulator
 
::routine flattenSublist
use arg list, accumulator
 
-- ask for the items explicitly, since this will allow
-- us to flatten indexed collections as well
do item over list~allItems
-- if the object is some sort of collection, flatten this out rather
-- than add to the accumulator
if item~isA(.collection) then call flattenSublist item, accumulator
else accumulator~append(item)
end
 

[edit] PARI/GP

flatten(v)={
my(u=[]);
for(i=1,#v,
u=concat(u,if(type(v[i])=="t_VEC",flatten(v[i]),v[i]))
);
u
};

[edit] Perl

sub flatten {
map { ref eq 'ARRAY' ? flatten(@$_) : $_ } @_
}
 
my @lst = ([1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []);
print flatten(@lst), "\n";

[edit] Perl 6

Works with: Rakudo version #22 "Thousand Oaks"
multi flatten (@a) { map { flatten $^x }, @a }
multi flatten ($x) { $x }

[edit] PHP

Works with: PHP version 4.x only, not 5.x
/* 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);

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.

[edit] Recursive

<?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));
?>
Alternatively:
Works with: PHP version 5.3+
<?php
function flatten($ary) {
$result = array();
array_walk_recursive($ary, function($x, $k) use (&$result) { $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));
?>
<?php
function flatten_helper($x, $k, $obj) {
$obj->flattened[] = $x;
}
 
function flatten($ary) {
$obj = (object)array('flattened' => array());
array_walk_recursive($ary, 'flatten_helper', $obj);
return $obj->flattened;
}
 
$lst = array(array(1), 2, array(array(3, 4), 5), array(array(array())), array(array(array(6))), 7, 8, array());
var_dump(flatten($lst));
?>

Using the standard library (warning: objects will also be flattened by this method):

<?php
$lst = array(array(1), 2, array(array(3, 4), 5), array(array(array())), array(array(array(6))), 7, 8, array());
$result = iterator_to_array(new RecursiveIteratorIterator(new RecursiveArrayIterator($lst)), false);
var_dump($result);
?>

[edit] Non-recursive

Function flat is iterative and flattens the array in-place.

<?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);
?>

[edit] PicoLisp

(de flatten (X)
(make # Build a list
(recur (X) # recursively over 'X'
(if (atom X)
(link X) # Put atoms into the result
(mapc recurse X) ) ) ) ) # or recurse on sub-lists

or a more succint way using fish:

(de flatten (X)
(fish atom X) )

[edit] Pike

There's a built-in function called Array.flatten() which does this, but here's a custom function:

array flatten(array a) {
array r = ({ });
 
foreach (a, mixed n) {
if (arrayp(n)) r += flatten(n);
else r += ({ n });
}
 
return r;
}

[edit] PL/I

This example is incorrect.
output (the flattening) is incorrect,
the incorrect output (list) is shown as a comment within the PL/I program,
the output has extra blanks and extra commas.
Please fix the code and remove this message.
 
list = translate (list, ' ', '[]' );
list = '[' || list || ']';
 
 
 
/* the above will erroneously return:
 
[ 1 , 2, 3,4 , 5 , , 6 , 7, 8, ]
 
*/
 
 

[edit] PostScript

Library: initlib
 
/flatten {
/.f {{type /arraytype eq} {{.f} map aload pop} ift}.
[exch .f]
}.
 
 
[[1] 2 [[3 4] 5] [[[]]] [[[6]]] 7 8 []] flatten
 

[edit] Prolog

 
flatten(List, FlatList) :-
flatten(List, [], FlatList).
 
flatten(Var, T, [Var|T]) :-
var(Var), !.
flatten([], T, T) :- !.
flatten([H|T], TailList, List) :- !,
flatten(H, FlatTail, List),
flatten(T, TailList, FlatTail).
 
flatten(NonList, T, [NonList|T]).
 

[edit] PureBasic

Structure RCList
Value.i
List A.RCList()
EndStructure
 
Procedure Flatten(List A.RCList())
ResetList(A())
While NextElement(A())
With A()
If \Value
Continue
Else
ResetList(\A())
While NextElement(\A())
If \A()\Value: A()\Value=\A()\Value: EndIf
Wend
EndIf
While ListSize(\A()): DeleteElement(\A()): Wend
If Not \Value: DeleteElement(A()): EndIf
EndWith
Wend
EndProcedure

Set up the MD-List & test the Flattening procedure.

;- Set up two lists, one multi dimensional and one 1-D.
NewList A.RCList()
 
;- Create a deep list
With A()
AddElement(A()): AddElement(\A()): AddElement(\A()): \A()\Value=1
AddElement(A()): A()\Value=2
AddElement(A()): AddElement(\A()): \A()\Value=3
AddElement(\A()): \A()\Value=4
AddElement(A()): AddElement(\A()): \A()\Value=5
AddElement(A()): AddElement(\A()): AddElement(\A()): AddElement(\A())
AddElement(A()): AddElement(\A()): AddElement(\A()): \A()\Value=6
AddElement(A()): A()\Value=7
AddElement(A()): A()\Value=8
AddElement(A()): AddElement(\A()): AddElement(\A())
EndWith
 
Flatten(A())
 
;- Present the result
If OpenConsole()
Print("Flatten: [")
ForEach A()
Print(Str(A()\Value))
If ListIndex(A())<(ListSize(A())-1)
Print(", ")
Else
PrintN("]")
EndIf
Next
Print(#CRLF$+"Press ENTER to quit"): Input()
EndIf
Flatten: [1, 2, 4, 5, 6, 7, 8]

[edit] Python

[edit] Recursive

Function flatten is recursive and preserves its argument:

>>> def flatten(lst):
return sum( ([x] if not isinstance(x, 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]

[edit] Non-recursive

Function flat is iterative and flattens the list in-place. It follows the Python idiom of returning None when acting in-place:

>>> 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]

[edit] Generative

This method shows a solution using Python generators.

flatten is a generator that yields the non-list values of its input in order. In this case, the generator is converted back to a list before printing.

>>> def flatten(lst):
for x in lst:
if isinstance(x, list):
for x in flatten(x):
yield x
else:
yield x
 
 
>>>lst = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]
>>>print list(flatten(lst))
[1, 2, 3, 4, 5, 6, 7, 8]

[edit] R

x <- list(list(1), 2, list(list(3, 4), 5), list(list(list())), list(list(list(6))), 7, 8, list())
 
unlist(x)


[edit] Racket

Racket has a built-in flatten function:

 
#lang racket
(flatten '(1 (2 (3 4 5) (6 7)) 8 9))
 

outputs:

 
'(1 2 3 4 5 6 7 8 9)
 

or, writing it explicitly with the same result:

 
#lang racket
(define (flatten l)
(cond [(empty? l) null]
[(not (list? l)) (list l)]
[else (append (flatten (first l)) (flatten (rest l)))]))
(flatten '(1 (2 (3 4 5) (6 7)) 8 9))
 

[edit] REBOL

 
flatten: func [
"Flatten the block in place."
block [any-block!]
][
parse block [
any [block: any-block! (change/part block first block 1) :block | skip]
]
head block
]
 
Sample:
>> flatten [[1] 2 [[3 4] 5] [[[]]] [[[6]]] 7 8 []]
== [1 2 3 4 5 6 7 8]

[edit] REXX

[edit] compact version

/*REXX pgm demonstrates how to flatten a list  (it need not be numeric).*/
y = '[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]'
z = '['changestr(" ", space( translate(y, , '[,]')), ", ")']'
say ' input =' y
say 'output =' z
/*stick a fork in it, we're done.*/

Some older REXXes don't have a changestr bif, so one is included here ──► CHANGESTR.REX.

output

 input = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]
output = [1, 2, 3, 4, 5, 6, 7, 8]

[edit] expatiated version

/*REXX pgm demonstrates how to flatten a list  (it need not be numeric).*/
y = '[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]'
 
z = translate( y, ,'[,]' ) /*change brackets&commas──►blanks*/
z = space(z) /*remove extraneous blanks. */
z = changestr( ' ', z, ", " ) /*change blanks to "comma blank".*/
z = '[' || z || "]" /*add brackets via concatenation.*/
/*another version of above: */
z = '['z"]"
say ' input =' y
say 'output =' z
/*stick a fork in it, we're done.*/

output is the same as the 1st version.

[edit] Ruby

flatten is a built-in method of Arrays

flat = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []].flatten
p flat # => [1, 2, 3, 4, 5, 6, 7, 8]

[edit] Run BASIC

n$ = "[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8 []]"
for i = 1 to len(n$)
if instr("[] ,",mid$(n$,i,1)) = 0 then
flatten$ = flatten$ + c$ + mid$(n$,i,1)
c$ = ","
end if
next i
print "[";flatten$;"]"
Output:
[1,2,3,4,5,6,7,8]

[edit] S-lang

define flatten ();
 
define flatten (list) {
variable item,
retval,
val;
if (typeof(list) != List_Type) {
retval = list;
} else {
retval = {};
foreach item (list) {
foreach val (flatten(item)) {
list_append(retval, val);
}
}
}
return retval;
}

Sample:

slsh> variable data = {{1}, 2, {{3,4}, 5}, {{{}}}, {{{6}}}, 7, 8, {}},
           result = flatten(data);                                    
slsh> print(result);              
{
1
2
3
4
5
6
7
8
}

[edit] Scala

def flatList(l: List[_]): List[Any] = l match {
case Nil => Nil
case (head: List[_]) :: tail => flatList(head) ::: flatList(tail)
case head :: tail => head :: flatList(tail)
}

Sample:

scala> List(List(1), 2, List(List(3, 4), 5), List(List(List())), List(List(List(6))), 7, 8, List())
res10: List[Any] = List(List(1), 2, List(List(3, 4), 5), List(List(List())), List(List(List(6))), 7, 8, List())

scala> flatList(res10)
res12: List[Any] = List(1, 2, 3, 4, 5, 6, 7, 8)

[edit] 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)

[edit] 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]].
].

[edit] Smalltalk

Works with: GNU 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.

[edit] Suneido

ob = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]
ob.Flatten()

Output:

#(1, 2, 3, 4, 5, 6, 7, 8)

[edit] Swift

func list(s: Any...) -> [Any] {
return s
}
 
func flatten<T>(s: [Any]) -> [T] {
var r = [T]()
for e in s {
switch e {
case let a as [Any]:
r += flatten(a)
case let x as T:
r.append(x)
default:
assert(false, "value of wrong type")
}
}
return r
}
 
let s = list(list(1),
2,
list(list(3, 4), 5),
list(list(list())),
list(list(list(6))),
7,
8,
list()
)
println(s)
let result : [Int] = flatten(s)
println(result)

Output:

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

[edit] 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 2 3 4 5 6 7 8

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.)

Another implementation that's slightly more terse:

proc flatten {data} {
while { $data != [set data [join $data]] } { }
return $data
}
puts [flatten {{1} 2 {{3 4} 5} {{{}}} {{{6}}} 7 8 {}}]
# ===> 1 2 3 4 5 6 7 8

[edit] TI-89 BASIC

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

[edit] Trith

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

[edit] TXR

An important builtin.

@(bind foo ((1) 2 ((3 4) 5) ((())) (((6))) 7 8 ()))
@(bind bar foo)
@(flatten bar)

Run:

$ txr -a 5 flatten.txr  # show variable bindings in array notation to depth 5
foo[0][0]="1"
foo[1]="2"
foo[2][0][0]="3"
foo[2][0][1]="4"
foo[2][1]="5"
foo[4][0][0][0]="6"
foo[5]="7"
foo[6]="8"
bar[0]="1"
bar[1]="2"
bar[2]="3"
bar[3]="4"
bar[4]="5"
bar[5]="6"
bar[6]="7"
bar[7]="8"

[edit] VBScript

Working on embedded arrays as that's about the closest we get to lists.

[edit] Implementation
 
class flattener
dim separator
 
sub class_initialize
separator = ","
end sub
 
private function makeflat( a )
dim i
dim res
for i = lbound( a ) to ubound( a )
if isarray( a( i ) ) then
res = res & makeflat( a( i ) )
else
res = res & a( i ) & separator
end if
next
makeflat = res
end function
 
public function flatten( a )
dim res
res = makeflat( a )
res = left( res, len( res ) - len(separator))
res = split( res, separator )
flatten = res
end function
 
public property let itemSeparator( c )
separator = c
end property
end class
 
[edit] Invocation
 
dim flat
set flat = new flattener
flat.itemSeparator = "~"
wscript.echo join( flat.flatten( array( array( 1 ),2,array(array(3,4),5),array(array(array())),array(array(array(6))),7,8,array())), "!")
 
[edit] Output
 
1!2!3!4!5!6!7!8
 
[edit] Alternative (classless) Version
Works with: Windows Script Host version *
 
' Flatten the example array...
a = FlattenArray(Array(Array(1), 2, Array(Array(3,4), 5), Array(Array(Array())), Array(Array(Array(6))), 7, 8, Array()))
 
' Print the list, comma-separated...
WScript.Echo Join(a, ",")
 
Function FlattenArray(a)
If IsArray(a) Then DoFlatten a, FlattenArray: FlattenArray = Split(Trim(FlattenArray))
End Function
 
Sub DoFlatten(a, s)
For i = 0 To UBound(a)
If IsArray(a(i)) Then DoFlatten a(i), s Else s = s & a(i) & " "
Next
End Sub
 

[edit] Wart

Here's how Wart implements flatten:

def (flatten seq acc)
if no.seq
acc
~list?.seq
(cons seq acc)
 :else
(flatten car.seq (flatten cdr.seq acc))

Output:

(flatten '((1) 2 ((3 4) 5) ((())) (((6))) 7 8 ()))
=> (1 2 3 4 5 6 7 8)

[edit] zkl

fcn flatten(list){list.pump(List,
fcn(i){if(List.isType(i)) return(Void.Void,i,self.fcn); i})}
flatten(L(L(1), L(2), L(L(3,4), 5), L(L(L())), L(L(L(6))), 7, 8, L()))
//-->L(1,2,3,4,5,6,7,8)

This works by recursively writing the contents of lists to a new list. If a list is recursive or cyclic, it will blow the stack and throw an exception.

Personal tools
Namespaces

Variants
Actions
Community
Explore
Misc
Toolbox