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
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>
C
Example in C using a quick and dirty implementation of lists as a singly-linked list of structs.
List header file:
<lang c> // list.h
- ifndef __LIST_H__
- define __LIST_H__
// A quick and dirty list implementation. // Not recommended for use in production software.
// Types typedef enum {
NUMBER, LIST
} ItemType;
typedef struct _Item {
ItemType type; union { int number; struct { struct _Item *head; struct _Item *tail; } list; }; struct _Item *next;
} Item;
// Functions Item *NewListItem(Item *item1, ...); Item *NewNumberItem(int number); void PrintItem(Item *item); void DeleteItem(Item *item);
void Flatten(Item *item);
- endif // __LIST_H__
</lang>
List functions:
<lang c> // list.c
- include <stdarg.h>
- include <stdlib.h>
- include <stdio.h>
- include "list.h"
// Create (malloc) a new number item struct. Item *NewNumberItem(int number) {
Item *pItem = (Item *)malloc(sizeof(Item)); pItem->type = NUMBER; pItem->number = number; pItem->next = NULL; return pItem;
}
// Create (malloc) a new list item struct, and (optionally) // populate it with the given list of items. Note, we use // a variable args function for this to make constructing // a new list easier. Make sure to terminate the args list // with a NULL. NewListItem(NULL) creates an empty list. Item *NewListItem(Item *item1, ...) {
Item *pList = (Item *)malloc(sizeof(Item)); Item *pItem = item1; va_list items; pList->type = LIST; pList->list.head = NULL; pList->list.tail = NULL; pList->next = NULL; // Warning: Not sure this will work // on all compilers when item1 is NULL. // This example uses MSVC 6. va_start(items, item1); while(pItem != NULL) { if (pList->list.tail != NULL) pList->list.tail->next = pItem; else pList->list.head = pItem; pList->list.tail = pItem; pItem->next = NULL; pItem = va_arg(items, Item *); } va_end(items); return pList;
}
// Print out a list on a single line, as in: // [[1],2,[[3,4],5],[[[]]],[[[6]]],7,8,[]] void PrintItem(Item *item) {
Item *subItem; if (item->type == LIST) { printf("["); subItem = item->list.head; while (subItem != NULL) { if (subItem != item->list.head) printf(","); PrintItem(subItem); subItem = subItem->next; } printf("]"); } else printf("%d", item->number);
}
// Delete an item. Recurse if necessary to delete sublists. void DeleteItem(Item *item) {
Item *subItem; if (item->type == LIST) { while (item->list.head != NULL) { subItem = item->list.head; item->list.head = subItem->next; DeleteItem(subItem); } } free(item);
} </lang>
The Flatten algorithm (with lots comments since this is a one-off lists implementation):
<lang c> // flatten.c
- include <stdlib.h>
- include "list.h"
void Flatten(Item *item) {
Item *subItem, *prevItem, *nextItem; // Flatten is only meaningful for list items. if (item->type == LIST) { prevItem = NULL; subItem = item->list.head; // Flatten all subitems one at a time. while (subItem != NULL) { // Again, only list items need to be flattened. if (subItem->type == LIST) { // Flatten the sublist. Flatten(subItem); // If the now-flattened sublist is non-empty, its first item // will now be the next item in the parent list. If the sublist // is empty, the next item in the parent list will be the item // after the sublist. if (subItem->list.head != NULL) nextItem = subItem->list.head; else nextItem = subItem->next; // Update the previous item's next pointer (or the parent list's // head pointer, if the sublist we are deleting was the first // item in the parent list) so that it no longer points to the // sublist that we are about to delete. It should now point to // nextItem, which we determined above. if (prevItem != NULL) prevItem->next = nextItem; else item->list.head = nextItem; // If the sublist was non-empty, then we now need to update // our prevItem pointer to point to the last item in the sublist. if (subItem->list.tail != NULL) prevItem = subItem->list.tail; // If the sublist we are about to delete is the last item in the // parent list, we need to update the parent list's tail pointer. if (subItem == item->list.tail) item->list.tail = prevItem; // Lastly, we need to make sure that prevItem's next pointer // points to the item immediately following the doomed sublist. if (prevItem != NULL) prevItem->next = subItem->next; // Finally, destroy the sublist. free(subItem); // Now update the subItem pointer to pick up where we left off // in the parent list. if (prevItem != NULL) subItem = prevItem->next; else subItem = NULL; } else { // Nothing to do for number items. Just skip past them. prevItem = subItem; subItem = subItem->next; } } }
} </lang>
The test program:
<lang c> // main.c
- include <stdlib.h>
- include <stdio.h>
- include <stdarg.h>
- include "list.h"
// Short-hand to make list construction somewhat less cumbersome.
- define L NewListItem
- define N NewNumberItem
int main(int argc, char **argv) {
Item *list = L( L(N(1),NULL), N(2), L( L(N(3),N(4),NULL), N(5), NULL), L( L( L(NULL), NULL), NULL), L( L( L(N(6), NULL), NULL), NULL), N(7), N(8), L(NULL), NULL ); printf("Original List : "); PrintItem(list); printf("\n"); Flatten(list); printf("Flattened List: "); PrintItem(list); printf("\n"); DeleteItem(list); return 0;
} </lang>
Output:
Original List : [[1],2,[[3,4],5],[[[]]],[[[6]]],7,8,[]] Flattened List: [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)); next = current; ++next; list.erase(current); current = next; } else ++current; }
}</lang>
Use example:
Since C++ currently doesn't have nice syntax for initializing lists, this includes a simple parser to create lists of integers and sublists. Also, there's no standard way to output this type of list, so some output code is added as well. <lang cpp>#include <cctype>
- 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>
An alternative approach (from clojure.contrib.seq-utils).
<lang lisp>(defn flatten [x]
(filter (complement sequential?) (rest (tree-seq sequential? seq x))))</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.
The example has been modified so it
the same way as it
using
<lang d>version(Tango) {
import tango.io.Stdout; import tango.io.device.Array; import tango.io.stream.Format;
} else {
import std.stdio : writeln; import std.conv : to;
}
struct TreeList(T) {
alias TreeList!(T) MyT; bool isArr = true; // contains an arr on default union { MyT[] arr; T data; }
static MyT opCall(Types...)(Types items) { MyT result;
foreach (i, el; items) static if (is(Types[i] == T)) { MyT item; item.isArr = 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.isArr) { foreach (el; this.arr) result.arr ~= el.flatten().arr; } else { version (D_Version2) { result.arr ~= this; } else { result.arr ~= *this; } } return result; } version(Tango) { char[] toString() { auto bf = new Array(1024); auto f = new FormatOutput!(char) (bf); if (isArr) { f(arr); } else { f(data); } return cast(char[])bf.slice; } } version (D_Version2) { string toString() { if (isArr) return to!(string)(arr, "[", ", ", "]"); else return to!(string)(data); } }
}
void main() {
alias TreeList!(int) L; // 12 bytes if T is int auto list = L(L(1), 2, L(L(3,4), 5), L(L(L())), L(L(L(6))), 7, 8, L()); version (Tango) { Stdout (list).newline; Stdout (list.flatten()).newline; } else { writeln(list); writeln(list.flatten()); }
}</lang> Output:
[[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>
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>
Factor
USE: sequences.deep ( scratchpad ) { { 1 } 2 { { 3 4 } 5 } { { { } } } { { { 6 } } } 7 8 { } } flatten . { 1 2 3 4 5 6 7 8 }
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
Icon
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>
Unicon
This Icon solution works in Unicon.
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>
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 want here.
Example: <lang j> NB. create and display nested noun li
]li =. (<1) ; 2; ((<3; 4); 5) ; ((<a:)) ; ((<(<6))) ; 7; 8; <a:</lang>
<lang text>┌───┬─┬───────────┬────┬─────┬─┬─┬──┐ │┌─┐│2│┌───────┬─┐│┌──┐│┌───┐│7│8│┌┐│ ││1││ ││┌─────┐│5│││┌┐│││┌─┐││ │ ││││ │└─┘│ │││┌─┬─┐││ │││││││││6│││ │ │└┘│ │ │ ││││3│4│││ │││└┘│││└─┘││ │ │ │ │ │ │││└─┴─┘││ ││└──┘│└───┘│ │ │ │ │ │ ││└─────┘│ ││ │ │ │ │ │ │ │ │└───────┴─┘│ │ │ │ │ │ └───┴─┴───────────┴────┴─────┴─┴─┴──┘</lang>
(Note: if you are not seeing rectangular boxes here, that is because your browser either does not support line drawing characters or is using line drawing characters from a different font than your numeric characters.)
<lang j> 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:</lang> <lang text>┌───┬─┬─────────────────────┬────┬──────┬──┬──┬──┐ │┌─┐│2│┌───────┬───────────┐│┌──┐│┌────┐│18│19│┌┐│ ││1││ ││┌─────┐│ 5 6 7 8│││┌┐│││┌──┐││ │ ││││ │└─┘│ │││┌─┬─┐││ 9 10 11 12│││││││││17│││ │ │└┘│ │ │ ││││3│4│││13 14 15 16│││└┘│││└──┘││ │ │ │ │ │ │││└─┴─┘││ ││└──┘│└────┘│ │ │ │ │ │ ││└─────┘│ ││ │ │ │ │ │ │ │ │└───────┴───────────┘│ │ │ │ │ │ └───┴─┴─────────────────────┴────┴──────┴──┴──┴──┘</lang> <lang j> 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>
Java
flattenSE
is a side-effect version of then flatten function which takes an array of Objects
(where nested lists are Object
arrays) and returns the answer in a List
given to the function. flattenList
is a version which does not disturb the list that is passed in and returns the answer in a new List
.
<lang java5>import java.util.LinkedList;
import java.util.List;
import java.util.Arrays;
public class Flatten {
public static void flattenSE(List<Object> flatList, Object[] array) { for (Object item : array) { if (item instanceof Object[]) { flatten(flatList, (Object[]) item); } else { flatList.add(item); } } } private static Object[] a(Object... o) { return o; }
public static List<Object> flattenList(List<?> list){ List<Object> retVal = new LinkedList<Object>(); for(Object item:list){ if(item instanceof List){ retVal.addAll(flatten((List)item)); }else{ retVal.add(item); } } return retVal; }
public static void main(String[] args){ List<Object> test = Arrays.<Object>asList( Arrays.<Object>asList(1), 2, Arrays.<Object>asList( Arrays.<Object>asList(3,4), 5 ), Arrays.<Object>asList( Arrays.<Object>asList( Arrays.<Object>asList() ) ), Arrays.<Object>asList( Arrays.<Object>asList( Arrays.<Object>asList(6) ) ), 7, 8, Arrays.<Object>asList() );
System.out.println(test); System.out.println("flattenList: " + flattenList(test));
Object[] array = a(a(1), 2, a(a(3, 4), 5), a(a(a())), a(a(a(6))), 7, 8, a()); ArrayList<Object> arrList = new ArrayList<Object>(); flattenSE(arrList, array); System.out.println("flattenSE: "+arrList); }
}</lang> Output:
[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] flattenList: [1, 2, 3, 4, 5, 6, 7, 8] flattenSE: [1, 2, 3, 4, 5, 6, 7, 8]
JavaScript
<lang javascript><script type="text/javascript" src="/path/to/prototype.js"></script> <script type="text/javascript">
var a = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []];
document.write("
before
"); a.each(function(e){document.write("
")});
var f = a.flatten();
document.write("
after
"); f.each(function(e){document.write("
")});
</script></lang> output:
before 1 object 2 number 3,4,5 object object 6 object 7 number 8 number object after 1 number 2 number 3 number 4 number 5 number 6 number 7 number 8 number
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>
Objective-C
and
<lang objc>#import <Foundation/Foundation.h>
@interface NSArray (FlattenExt) -(NSArray *)flatten; @end
@implementation NSArray (FlattenExt) -(NSArray *)flatten {
NSMutableArray *r = [NSMutableArray new]; NSEnumerator *en = [self objectEnumerator]; id o; while ( (o = [en nextObject]) ) { if ( [o isKindOfClass: [NSArray class]] ) { [r addObjectsFromArray: [o flatten]]; } else { if ( o != [NSNull null] )
[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 arrayWithObject: [NSNull null]], nil], nil], [NSArray arrayWithObjects: [NSArray arrayWithObjects: [NSArray arrayWithObjects: [NSNumber numberWithInt: 6], nil], nil], nil], [NSNumber numberWithInt: 7], [NSNumber numberWithInt: 8], [NSArray arrayWithObject: [NSNull null]], nil];
NSArray *f = [p flatten]; NSEnumerator *e = [f objectEnumerator]; id o; while( (o = [e nextObject]) ) { NSLog(@"%d", [o intValue]); }
[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 if (object != [NSNull null]) [flattened addObject:object]; } return [flattened autorelease];
} @end
int main(int argc, char **argv) {
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 arrayWithObject:[NSNull null]]]], [NSArray arrayWithObject:[NSArray arrayWithObject:[NSArray arrayWithObject:[NSNumber numberWithInteger:6]]]], [NSNumber numberWithInteger:7], [NSNumber numberWithInteger:8], [NSArray arrayWithObject:[NSNull null]], nil]; for (id object in unflattened.flattened) NSLog(@"%d", [object integerValue]); [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>
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>
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 || ']'; </lang>
Prolog
<lang Prolog> flatten([], []). flatten(E, [E]) :- atom(E). flatten([E|T], F) :-
flatten(E, Ef), flatten(T, Tf), append(Ef, Tf, F), !.
</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]
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>
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
- AutoHotkey
- C
- C++
- C sharp
- Clojure
- Common Lisp
- D
- Tango
- E
- Erlang
- Factor
- Groovy
- Haskell
- Icon
- Icon Programming Library
- Unicon
- Ioke
- J
- Java
- JavaScript
- Prototype
- Lua
- Logo
- Mathematica
- Objective-C
- OCaml
- Oz
- Perl
- Perl 6
- PHP
- PicoLisp
- PL/I
- Prolog
- PureBasic
- Python
- R
- REBOL
- Ruby
- Scala
- Scheme
- Slate
- Smalltalk
- Suneido
- Tcl
- TI-89 BASIC
- Trith
- VBScript