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
ActionScript
<lang 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; } </lang>
Aikido
<lang 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("]")
</lang> Output:
[1, 2, 3, 4, 5, 6, 7, 8]
ALGOL 68
Flattening is built in to all of Algol68's transput routines. The following example also uses widening, where scalars are converted into arrays.
<lang algol68>main:(
[][][]INT list = ((1), 2, ((3,4), 5), ((())), (((6))), 7, 8, ()); print((list, new line))
)</lang> Output:
+1 +2 +3 +4 +5 +6 +7 +8
AppleScript
<lang 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 </lang>
AutoHotkey
AutoHotkey doesn't have built in list data type. This examples simulates a list in a tree type object and flattens that tree. <lang AutoHotkey>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
}</lang>
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.
<lang bracmat> ( (myList = ((1), 2, ((3,4), 5), ((())), (((6))), 7, 8, ())) & put$("Unevaluated:") & lst$myList & !myList:?myList { the expression !list evaluates myList } & put$("Flattened:") & lst$myList ) </lang>
Brat
<lang brat>array.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}"</lang>
C
<lang 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;
}</lang>output
Nested: [[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] Flattened: [1, 2, 3, 4, 5, 6, 7, 8]
C++
<lang cpp>#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;
}
}</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>
- 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]
C#
Actual Workhorse code <lang csharp> 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; } } } </lang>
Method showing population of arraylist and usage of flatten method <lang csharp> 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 ( ) );
}
}
} }
</lang>
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 (rest s)))
(cons (first s) (flatten (rest s)))))))</lang>
The built-in flatten is implemented as:
<lang lisp>(defn flatten [x]
(filter (complement sequential?)
(rest (tree-seq sequential? seq x))))</lang>
CoffeeScript
<lang coffeescript>flatten = (arr) -> arr.reduce ((xs, el) -> if Array.isArray el xs.concat flatten el else xs.concat [el]), []</lang>
Usage: <lang coffeescript>coffee> list = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] [ [ 1 ], 2, [ [ 3, 4 ], 5 ], [ [ [] ] ], [ [ [Object] ] ], 7, 8, [] ] coffee> flatten list [ 1, 2, 3, 4, 5, 6, 7, 8 ]</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.
D
There are many ways to implement this in D. This version minimizes heap activity using a tagged union. A similar object-oriented version too is possible.
:
<lang d>import std.stdio: writeln; import std.conv: to;
struct TreeList(T) {
union {
TreeList!T[] arr;
T data;
}
bool isArray = true; // contains an arr on default
static TreeList!T opCall(Types...)(Types items) {
TreeList!T result;
foreach (i, el; items)
static if (is(Types[i] == T)) {
TreeList!T item;
item.isArray = false;
item.data = el;
result.arr ~= item;
} else
result.arr ~= el;
return result; }
// this is better as a general free function
TreeList!T flatten() {
TreeList!T result;
if (this.isArray)
foreach (el; this.arr)
result.arr ~= el.flatten().arr;
else
result.arr ~= this;
return result; }
string toString() {
if (isArray)
return to!string(arr, "[", ", ", "]");
else
return to!string(data);
}
}
void main() {
alias TreeList!(int) L; // 12 bytes if T is int auto l = L(L(1), 2, L(L(3,4), 5), L(L(L())), L(L(L(6))), 7, 8, L()); writeln(l); writeln(l.flatten());
}</lang>
using
:
<lang d>import tango.io.Stdout; import tango.io.device.Array; import tango.io.stream.Format;
struct TreeList(T) {
alias TreeList!(T) MyT;
union {
MyT[] arr;
T data;
}
bool isArray = true; // contains an arr on default
static MyT opCall(Types...)(Types items) {
MyT result;
foreach (i, el; items)
static if (is(Types[i] == T)) {
MyT item;
item.isArray = false;
item.data = el;
result.arr ~= item;
} else
result.arr ~= el;
return result; }
// this is better as a general free function
MyT flatten() {
MyT result;
if (this.isArray)
foreach (el; this.arr)
result.arr ~= el.flatten().arr;
else
result.arr ~= *this;
return result; }
char[] toString() {
auto bf = new Array(1024);
auto f = new FormatOutput!(char) (bf);
if (isArray)
f(arr);
else
f(data);
return cast(char[])bf.slice;
}
}
void main() {
alias TreeList!(int) L; // 12 bytes if T is int auto l = L(L(1), 2, L(L(3,4), 5), L(L(L())), L(L(L(6))), 7, 8, L()); Stdout (l).newline; Stdout (l.flatten()).newline;
}</lang> Output (for both):
[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] [1, 2, 3, 4, 5, 6, 7, 8]
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, []])
- value: [1, 2, 3, 4, 5, 6, 7, 8]</lang>
Ela
This implementation can flattern any given list:
<lang Ela>let xs = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]
let 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</lang>
Output:
[1,2,3,4,5,6,7,8]
An alternative solution:
<lang Ela>let flat [] = []
flat (x::xs) | x is ?list = flat x ++ flat xs
| else = x :: flat xs</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>
Euphoria
<lang Euphoria>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)</lang> Output
{
{1},
2,
{
{3,4},
5
},
{
{{}}
},
{
{
{6}
}
},
7,
8,
{}
}
{1,2,3,4,5,6,7,8}
Factor
USE: sequences.deep
( scratchpad ) { { 1 } 2 { { 3 4 } 5 } { { { } } } { { { 6 } } } 7 8 { } } flatten .
{ 1 2 3 4 5 6 7 8 }
Fantom
<lang 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))
}
} </lang>
Frink
<lang frink> a = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] println[flatten[a]] </lang>
GAP
<lang gap>Flat([[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]);</lang>
Go
<lang 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
}</lang> 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. <lang go>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
}</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>
Yet another choice, custom data structure, efficient lazy flattening:
<lang haskell>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]</lang>
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. <lang Icon>link strings # for compress,deletec,pretrim
procedure sflatten(s) # uninteresting string solution return pretrim(trim(compress(deletec(s,'[ ]'),',') ,','),',') end</lang>
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. <lang Icon>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</lang>
Finally a demo routine to drive these and a helper to show how it works. <lang Icon>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</lang>
Ioke
<lang 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]</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>
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:
<lang j>flatten2 =: [: ; <@,S:0</lang>
Example: <lang j> ]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</lang>
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).
Java
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 <lang java5>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); } } } }</lang>
Method showing population of the test List and usage of flatten method. <lang java5>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); } }</lang>
Output:
[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] flatten: [1, 2, 3, 4, 5, 6, 7, 8]
JavaScript
<lang javascript>var flatten = function(arr){
var flatten = arguments.callee; // reference to self, in case top-level var name is changed
return arr.reduce(function(acc, val){
return acc.concat(val.constructor === Array ? flatten(val) : val);
},[]);
};</lang>
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: <lang k>,//((1); 2; ((3;4); 5); ((())); (((6))); 7; 8; ())</lang>
Logtalk
<lang 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]).</lang>
Lua
<lang 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), ","))</lang>
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>
Mathematica
<lang Mathematica>Flatten[{{1}, 2, {{3, 4}, 5}, {{{}}}, {{{6}}}, 7, 8, {}}]</lang>
Mirah
<lang 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)</lang>
NewLISP
<lang NewLISP>> (flat '((1) 2 ((3 4) 5) ((())) (((6))) 7 8 ())) (1 2 3 4 5 6 7 8) </lang>
Objective-C
and
<lang objc>#import <Foundation/Foundation.h>
@interface NSArray (FlattenExt) -(NSArray *)flatten; @end
@implementation NSArray (FlattenExt) -(NSArray *)flatten {
NSMutableArray *r = [NSMutableArray array];
NSEnumerator *en = [self objectEnumerator];
id o;
while ( (o = [en nextObject]) ) {
if ( [o isKindOfClass: [NSArray class]] )
[r addObjectsFromArray: [o flatten]];
else
[r addObject: o];
}
return [NSArray arrayWithArray: r];
} @end
int main() {
NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init]; NSArray *p = [NSArray
arrayWithObjects: [NSArray arrayWithObjects: [NSNumber numberWithInt: 1], nil], [NSNumber numberWithInt: 2], [NSArray arrayWithObjects: [NSArray arrayWithObjects: [NSNumber numberWithInt: 3], [NSNumber numberWithInt: 4], nil], [NSNumber numberWithInt: 5], nil], [NSArray arrayWithObjects: [NSArray arrayWithObjects: [NSArray arrayWithObjects: nil], nil], nil], [NSArray arrayWithObjects: [NSArray arrayWithObjects: [NSArray arrayWithObjects: [NSNumber numberWithInt: 6], nil], nil], nil], [NSNumber numberWithInt: 7], [NSNumber numberWithInt: 8], [NSArray arrayWithObjects: nil], nil];
NSArray *f = [p flatten];
NSEnumerator *e = [f objectEnumerator];
id o;
while( (o = [e nextObject]) )
{
NSLog(@"%@", o);
}
[pool drain]; return 0;
}</lang>
An alternative solution
<lang objc2>#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() {
NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
NSArray *unflattened = [NSArray arrayWithObjects:[NSArray arrayWithObject:[NSNumber numberWithInteger:1]],
[NSNumber numberWithInteger:2],
[NSArray arrayWithObjects:[NSArray arrayWithObjects:[NSNumber numberWithInteger:3], [NSNumber numberWithInteger:4], nil],
[NSNumber numberWithInteger:5], nil],
[NSArray arrayWithObject:[NSArray arrayWithObject:[NSArray array]]],
[NSArray arrayWithObject:[NSArray arrayWithObject:[NSArray arrayWithObject:[NSNumber numberWithInteger:6]]]],
[NSNumber numberWithInteger:7],
[NSNumber numberWithInteger:8],
[NSArray array], nil];
for (id object in unflattened.flattened)
NSLog(@"%@", object);
[pool drain];
return 0;
}</lang>
OCaml
<lang 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]</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
- 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]</lang>
Oz
Oz has a standard library function "Flatten": <lang oz>{Show {Flatten [[1] 2 [[3 4] 5] nil [[[6]]] 7 8 nil]}}</lang> A simple, non-optimized implementation could look like this: <lang oz>fun {Flatten2 Xs}
case Xs of nil then nil
[] X|Xr then
{Append {Flatten2 X} {Flatten2 Xr}}
else [Xs]
end
end </lang>
PARI/GP
<lang parigp>flatten(v)={
my(u=[]); for(i=1,#v, u=concat(u,if(type(v[i])=="t_VEC",flatten(v[i]),v[i])) ); u
};</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
<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>
Alternatively:
<lang php><?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)); ?></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>
PicoLisp
<lang 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</lang>
or a more succint way using fish:
<lang PicoLisp>(de flatten (X)
(fish atom X) )</lang>
PL/I
<lang PL/I> list = translate (list, ' ', '[]' ); list = '[' || list || ']';
/* the above will erroneously return:
[ 1 , 2, 3,4 , 5 , , 6 , 7, 8, ]
- /
</lang>
PostScript
<lang postscript> /flatten {
/.f {{type /arraytype eq} {{.f} map aload pop} ift}.
[exch .f]
}. </lang> <lang> [[1] 2 [[3 4] 5] [[[]]] [[[6]]] 7 8 []] flatten </lang>
Prolog
<lang 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]). </lang>
PureBasic
<lang 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</lang> Set up the MD-List & test the Flattening procedure. <lang PureBasic>;- 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</lang>
Flatten: [1, 2, 4, 5, 6, 7, 8]
Python
Recursive
Function flatten is recursive and preserves its argument:
<lang python>>>> 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]</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>
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.
<lang python>>>> 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]</lang>
R
<lang R>x <- list(list(1), 2, list(list(3, 4), 5), list(list(list())), list(list(list(6))), 7, 8, list())
unlist(x)</lang>
REBOL
<lang 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
] </lang>
Sample:
>> flatten [[1] 2 [[3 4] 5] [[[]]] [[[6]]] 7 8 []] == [1 2 3 4 5 6 7 8]
REXX
<lang REXX> /*flatten a list*/ y='[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]'
/*-------------- version 1--------------------*/
z='['changestr(' ',space(translate(y,,'[,]')),", ")']' say 'version 1' say y say z say
/*-------------- version 2--------------------*/
z=translate(y,,'[,]') /*change brackets & commas to blanks*/ z=space(z) /*remove extraneous blanks*/ z=changestr(' ',z,", ") /*change blanks to "comma blank"*/ z='['z"]" /*add brackets*/ say 'version 2' say y say z </lang> Output:
version 1 [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] [1, 2, 3, 4, 5, 6, 7, 8] version 2 [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] [1, 2, 3, 4, 5, 6, 7, 8]
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>
S-lang
<lang 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;
}</lang>
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
}
Scala
<lang 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)
}</lang>
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)
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
<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>
Suneido
<lang suneido>ob = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] ob.Flatten()</lang>
Output:
#(1, 2, 3, 4, 5, 6, 7, 8)
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 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.)
Another implementation that's slightly more terse:
<lang tcl>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</lang>
TI-89 BASIC
There is no nesting of lists or other data structures in TI-89 BASIC, short of using variable names as pointers.
Trith
<lang trith>[[1] 2 [[3 4] 5] [[[]]] [[[6]]] 7 8 []] flatten</lang>
VBScript
Working on embedded arrays as that's about the closest we get to lists.
Implementation
<lang vb> 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 </lang>
Invocation
<lang vb> 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())), "!") </lang>
Output
<lang vb> 1!2!3!4!5!6!7!8 </lang>
- Programming Tasks
- Solutions by Programming Task
- ActionScript
- Aikido
- ALGOL 68
- AppleScript
- AutoHotkey
- Bracmat
- Brat
- C
- C++
- C sharp
- Clojure
- CoffeeScript
- Common Lisp
- D
- Tango
- E
- Ela
- Erlang
- Euphoria
- Factor
- Fantom
- Frink
- GAP
- Go
- Groovy
- Haskell
- Icon
- Unicon
- Icon Programming Library
- Ioke
- J
- Java
- JavaScript
- K
- Logtalk
- Lua
- Logo
- Mathematica
- Mirah
- NewLISP
- Objective-C
- OCaml
- Oz
- PARI/GP
- Perl
- Perl 6
- PHP
- PicoLisp
- PL/I
- PostScript
- Initlib
- Prolog
- PureBasic
- Python
- R
- REBOL
- REXX
- Ruby
- S-lang
- Scala
- Scheme
- Slate
- Smalltalk
- Suneido
- Tcl
- TI-89 BASIC
- Trith
- VBScript
- Ada/Omit
- Standard ML/Omit