Flatten a list: Difference between revisions
(→{{header|Common Lisp}}: Common Lisp, not common lisp) |
|||
| Line 736: | Line 736: | ||
</lang> |
</lang> |
||
Note that since, in |
Note that since, in Common Lisp, the empty list, boolean false and <code>nil</code> are the same thing, a tree of <code>nil</code> values cannot be flattened; they will disappear. |
||
A third version that is recursive, imperative, and reasonably fast. |
A third version that is recursive, imperative, and reasonably fast. |
||
| Line 742: | Line 742: | ||
(let (result) |
(let (result) |
||
(labels ((grep (obj) |
(labels ((grep (obj) |
||
(cond ((null obj)) |
(cond ((null obj) nil) |
||
((atom obj) (push obj result)) |
((atom obj) (push obj result)) |
||
(t (grep (rest obj)) |
(t (grep (rest obj)) |
||
| Line 770: | Line 770: | ||
(1 2 3 4 5 6 7 8)</pre> |
(1 2 3 4 5 6 7 8)</pre> |
||
It should be noted that there are several choices that can be made when implementing flatten in |
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 on dotted pairs? |
||
Revision as of 19:54, 12 April 2015
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
8th
<lang forth> \ take a list (array) and flatten it:
- (flatten) \ a -- a
( \ is it a number? dup >kind cls:n n:= if \ yes. so add to the list r> swap a:push >r else \ it is not, so flatten it (flatten) then drop ) a:each drop ;
- flatten \ a -- a
[] >r (flatten) r> ;
[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] dup . cr flatten . cr bye </lang>
- Output:
[[1],2,[[3,4],5],[[[]]],[[[6]]],7,8,[]]
[1,2,3,4,5,6,7,8]
ACL2
<lang Lisp>(defun flatten (tr)
(cond ((null tr) nil)
((atom tr) (list tr))
(t (append (flatten (first tr))
(flatten (rest tr))))))</lang>
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]
Aime
<lang 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;
}</lang>
- Output:
[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] [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 !myList evaluates myList } & put$("Flattened:") & lst$myList ) </lang>
Brat
<lang 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}"</lang>
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.
<lang burlesque> blsq ) {{1} 2 {{3 4} 5} {{{}}} {{{6}}} 7 8 {}}{\[}{)to{"Block"==}ay}w! {1 2 3 4 5 6 7 8} </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>
- Output:
[[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>
<lang csharp> 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(); } } </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]), []
- test
list = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] console.log flatten list </lang>
Ouput: <lang> > coffee foo.coffee [ 1, 2, 3, 4, 5, 6, 7, 8 ] </lang>
Common Lisp
<lang lisp>(defun flatten (structure)
(cond ((null structure) nil)
((atom structure) (list structure))
(t (mapcan #'flatten structure))))</lang>
or, from Paul Graham's OnLisp, <lang lisp> (defun flatten (ls)
(labels ((mklist (x) (if (listp x) x (list x)))) (mapcan #'(lambda (x) (if (atom x) (mklist x) (flatten x))) ls)))
</lang>
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. <lang lisp>(defun flatten (obj)
(let (result)
(labels ((grep (obj)
(cond ((null obj) nil)
((atom obj) (push obj result))
(t (grep (rest obj))
(grep (first obj))))))
(grep obj)
result)))</lang>
The following version is tail recursive and functional. <lang lisp>(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)))</lang>
The next version is imperative, iterative and does not make use of a stack. It is faster than the versions given above. <lang lisp>(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))))))</lang>
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.
D
Instead of a Java-like class-based version, this version minimizes heap activity using a tagged union. <lang d>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;
}</lang>
- Output:
[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] [1, 2, 3, 4, 5, 6, 7, 8]
With an Algebraic Data Type
A shorter and more cryptic version. <lang d>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;
}</lang>
- Output:
[1, 2, 3, 4, 5, 6, 7, 8]
Déjà Vu
<lang dejavu>(flatten): for i in copy: i if = :list type dup: (flatten)
flatten l: [ (flatten) l ]
!. flatten [ [ 1 ] 2 [ [ 3 4 ] 5 ] [ [ [] ] ] [ [ [ 6 ] ] ] 7 8 [] ]</lang>
- Output:
[ 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>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</lang>
- Output:
[1,2,3,4,5,6,7,8]
An alternative solution:
<lang Ela>flat [] = [] flat (x::xs)
| x is List = flat x ++ flat xs | else = x :: flat xs</lang>
Elixir
<lang 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) </lang>
- Output:
[1, 2, 3, 4, 5, 6, 7, 8] [1, 2, 3, 4, 5, 6, 7, 8]
Emacs Lisp
<lang lisp> (defun flatten (mylist)
(cond ((null mylist) nil) ((atom mylist) (list mylist)) (t (append (flatten (car mylist)) (flatten (cdr mylist))))))
</lang>
Erlang
There's a standard function (lists:flatten/1) 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}
F#
As with Haskell and OCaml we have to define our list as an algebraic data type, to be strongly typed: <lang fsharp>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]</lang>
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.
<lang fsharp> 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] </lang>
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>
Forth
Works with any ANS Forth. Needs the FMS-SI (single inheritance) library code located here: http://soton.mpeforth.com/flag/fms/index.html <lang forth>include FMS-SI.f include FMS-SILib.f
- flatten {: list1 list2 -- :}
list1 size: 0 ?do i list1 at:
dup is-a object-list2
if list2 recurse else list2 add: then loop ;
object-list2 list o{ o{ 1 } 2 o{ o{ 3 4 } 5 } o{ o{ o{ } } } o{ o{ o{ 6 } } } 7 8 o{ } } list flatten list p: \ o{ 1 2 3 4 5 6 7 8 } ok</lang>
Fortran
<lang 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 </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:
(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.)
<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]
- Functional version
<lang java5>import java.util.List; import java.util.stream.Stream; import java.util.stream.Collectors;
public final class FlattenUtil {
public static Stream<Object> flattenToStream(List<?> list) { return list.stream().flatMap(item -> item instanceof List<?> ? flattenToStream((List<?>)item) : Stream.of(item)); }
public static List<Object> flatten(List<?> list) { return flattenToStream(list).collect(Collectors.toList()); } }</lang>
JavaScript
ES5
<lang javascript>function flatten(list) {
return list.reduce(function (acc, val) {
return acc.concat(val.constructor === Array ? flatten(val) : val);
}, []);
}</lang>
ES6
<lang javascript>let flatten = list => list.reduce(
(a, b) => a.concat(Array.isArray(b) ? flatten(b) : b), []
);</lang>
Result is always:
[1, 2, 3, 4, 5, 6, 7, 8]
Joy
<lang Joy> "seqlib" libload.
[[1] 2 [[3 4] 5] [[[]]] [[[6]]] 7 8 []] treeflatten.
(* output: [1 2 3 4 5 6 7 8] *) </lang>
jq
Recent (1.4+) versions of jq include the following flatten filter:<lang jq>def flatten:
reduce .[] as $i
([];
if $i | type == "array" then . + ($i | flatten)
else . + [$i]
end);</lang>Example:<lang jq>
[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] | flatten [1,2,3,4,5,6,7,8]</lang>
Julia
Julia auto-flattens nested arrays of this form <lang julia>julia> t = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] 8-element Int32 Array:
1 2 3 4 5 6 7 8</lang>
Arrays of type Any can be nested. They are denoted with {}. Here is a slow recursive version. <lang julia>flat(A) = [[isa(x,Array)? flat(x): x for x in A]...]</lang> The following high-level version is notably faster. <lang Julia>flat(A) = mapreduce(x->isa(x,Array)? flat(x): x, vcat, A)</lang> An iterative recursive version that is even faster. <lang Julia>function flat(A)
result = {}
grep(a) = for x in a
isa(x,Array) ? grep(x) : push!(result,x)
end
grep(A)
result
end
</lang>
- Output:
julia> show(flat( {{1}, 2, {{3,4}, 5}, {{{}}}, {{{6}}}, 7, 8, {}} ))
{1,2,3,4,5,6,7,8}
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>
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
<lang Lasso>local(original = json_deserialize('[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]'))
- original
'
'
(with item in delve(#original)
select #item) -> asstaticarray</lang>
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)
LFE
<lang lisp> > (: lists flatten '((1) 2 ((3 4) 5) ((())) (((6))) 7 8 ())) (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>
Maple
This can be accomplished using the Flatten command from the ListTools, or with a custom recursive procedure.
<lang Maple> L := [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]:
with(ListTools):
Flatten(L); </lang>
- Output:
[1, 2, 3, 4, 5, 6, 7, 8]
<lang Maple> 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)]; </lang>
- Output:
[1, 2, 3, 4, 5, 6, 7, 8]
Mathematica
<lang Mathematica>Flatten[{{1}, 2, {{3, 4}, 5}, {{{}}}, {{{6}}}, 7, 8, {}}]</lang>
Maxima
<lang 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] */</lang>
Mercury
As with Haskell we need to use an algebraic data type. <lang mercury>:- module flatten_a_list.
- - interface.
- - import_module io.
- - pred main(io::di, io::uo) is det.
- - implementation.
- - import_module list.
- - type tree(T)
---> leaf(T) ; node(list(tree(T))).
- - func flatten(tree(T)) = list(T).
flatten(leaf(X)) = [X]. flatten(node(Xs)) = condense(map(flatten, Xs)).
main(!IO) :-
List = 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([])
]),
io.print_line(flatten(List), !IO).
- - end_module flatten_a_list.
</lang>
- Output:
[1, 2, 3, 4, 5, 6, 7, 8]
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>
Nim
<lang nim>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)</lang>
- Output:
[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] @[1, 2, 3, 4, 5, 6, 7, 8]
Objective-C
<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() {
@autoreleasepool {
NSArray *p = @[
@[ @1 ], @2, @[ @[@3, @4], @5], @[ @[ @[ ] ] ], @[ @[ @[ @6 ] ] ], @7, @8, @[ ] ];
for (id object in unflattened.flattened)
NSLog(@"%@", object);
}
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>
Oforth
<lang Oforth>[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] expand println</lang>
- Output:
[1, 2, 3, 4, 5, 6, 7, 8]
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>
ooRexx
<lang 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
</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>
<lang php><?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)); ?></lang>
Using the standard library (warning: objects will also be flattened by this method):
<lang php><?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); ?></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>
Pike
There's a built-in function called Array.flatten() which does this, but here's a custom function:
<lang pike>array flatten(array a) {
array r = ({ });
foreach (a, mixed n) { if (arrayp(n)) r += flatten(n); else r += ({ n }); }
return r; }</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
<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>
Racket
Racket has a built-in flatten function: <lang Racket>
- lang racket
(flatten '(1 (2 (3 4 5) (6 7)) 8 9)) </lang>
- Output:
'(1 2 3 4 5 6 7 8 9)
or, writing it explicitly with the same result: <lang Racket>
- 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)) </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
compact version
<lang REXX>/*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.*/</lang>
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]
expatiated version
<lang rexx>/*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 any extraneous blanks. */ z = changestr( ' ', z, ", " ) /*change blanks to "comma blank". */ z = '[' || z || "]" /*add brackets via concatenation. */
/*alternate of the above statement*/
/* (add brackets via abutment) */
/* ╔════════════════════════════╗ */
/* ║ z = '['z"]" ║ */
/* ╚════════════════════════════╝ */
say ' input =' y say 'output =' z
/*stick a fork in it, we're done.*/</lang>
output is the same as the 1st version.
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>
The flatten method takes an optional argument, which dedicates the amount of levels to be flattened.
<lang ruby>p flatten_once = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []].flatten(1)
- => [1, 2, [3, 4], 5, [[]], 6, 7, 8]
</lang>
Run BASIC
<lang runbasic>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$;"]"</lang>
- Output:
[1,2,3,4,5,6,7,8]
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>
Sidef
<lang ruby>func flatten(a) {
var flat = [];
a.each { |item|
flat += (item.is_an(Array) ? flatten(item) : [item]);
};
return flat;
}
var arr = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]; say flatten(arr).dump; # used-defined function say arr.flatten.dump; # built-in method for Array obj</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)
Swift
<lang 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)</lang>
- Output:
[[1] 2 [[3 4] 5] [[[]]] [[[6]]] 7 8 []] [1 2 3 4 5 6 7 8]
More functionally:
<lang swift>func list(s: Any...) -> [Any] {
return s
}
func flatten<T>(s: [Any]) -> [T] {
return s.flatMap {
switch $0 {
case let a as [Any]:
return flatten(a)
case let x as T:
return [x]
default:
assert(false, "value of wrong type")
}
}
}
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)</lang>
- Output:
[[1] 2 [[3 4] 5] [[[]]] [[[6]]] 7 8 []] [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>
TXR
An important builtin. <lang txr>@(bind foo ((1) 2 ((3 4) 5) ((())) (((6))) 7 8 ())) @(bind bar foo) @(flatten bar)</lang>
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"
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:
1!2!3!4!5!6!7!8
Alternative (classless) Version
<lang VBScript> ' 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 </lang>
Wart
Here's how Wart implements flatten:
<lang python>def (flatten seq acc)
if no.seq
acc
~list?.seq
(cons seq acc)
:else
(flatten car.seq (flatten cdr.seq acc))</lang>
- Output:
(flatten '((1) 2 ((3 4) 5) ((())) (((6))) 7 8 ())) => (1 2 3 4 5 6 7 8)
zkl
<lang 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)</lang> 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.
- Programming Tasks
- Solutions by Programming Task
- 8th
- ACL2
- ActionScript
- Aikido
- Aime
- ALGOL 68
- AppleScript
- AutoHotkey
- Bracmat
- Brat
- Burlesque
- C
- C++
- C sharp
- Clojure
- CoffeeScript
- Common Lisp
- D
- Déjà Vu
- E
- Ela
- Elixir
- Emacs Lisp
- Erlang
- Euphoria
- F Sharp
- Factor
- Fantom
- Forth
- Fortran
- Frink
- GAP
- Go
- Groovy
- Haskell
- Icon
- Unicon
- Icon Programming Library
- Ioke
- J
- Java
- JavaScript
- Joy
- Jq
- Julia
- K
- Lasso
- LFE
- Logtalk
- Lua
- Logo
- Maple
- Mathematica
- Maxima
- Mercury
- Mirah
- NewLISP
- Nim
- Objective-C
- OCaml
- Oforth
- Oz
- OoRexx
- PARI/GP
- Perl
- Perl 6
- PHP
- PicoLisp
- Pike
- PL/I
- PL/I examples needing attention
- Examples needing attention
- PostScript
- Initlib
- Prolog
- PureBasic
- Python
- R
- Racket
- REBOL
- REXX
- Ruby
- Run BASIC
- S-lang
- Scala
- Scheme
- Sidef
- Slate
- Smalltalk
- Suneido
- Swift
- Tcl
- TI-89 BASIC
- Trith
- TXR
- VBScript
- Wart
- Zkl
- Ada/Omit
- Standard ML/Omit