Flatten a list
From Rosetta Code
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
[edit] ActionScript
function flatten(input:Array):Array {
var output:Array = new Array();
for (var i:uint = 0; i < input.length; i++) {
//typeof returns "object" when applied to arrays. This line recursively evaluates nested arrays,
// although it may break if the array contains objects that are not arrays.
if (typeof input[i]=="object") {
output=output.concat(flatten(input[i]));
} else {
output.push(input[i]);
}
}
return output;
}
[edit] Aikido
function flatten (list, result) {
foreach item list {
if (typeof(item) == "vector") {
flatten (item, result)
} else {
result.append (item)
}
}
}
var l = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]
var newl = []
flatten (l, newl)
// print out the nicely formatted result list
print ('[')
var comma = ""
foreach item newl {
print (comma + item)
comma = ", "
}
println("]")
Output:
[1, 2, 3, 4, 5, 6, 7, 8]
[edit] ALGOL 68
Works with: ALGOL 68 version Revision 1 - no extensions to language used
Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny
Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8-8d
Flattening is built in to all of Algol68's transput routines. The following example also uses widening, where scalars are converted into arrays.
main:(
[][][]INT list = ((1), 2, ((3,4), 5), ((())), (((6))), 7, 8, ());
print((list, new line))
)
Output:
+1 +2 +3 +4 +5 +6 +7 +8
[edit] AutoHotkey
Works with: AutoHotkey_L
AutoHotkey doesn't have built in list data type. This examples simulates a list in a tree type object and flattens that tree.
list := object(1, object(1, 1), 2, 2, 3, object(1, object(1, 3, 2, 4)
, 2, 5), 4, object(1, object(1, object(1, object()))), 5
, object(1, object(1, 6)), 6, 7, 7, 8, 9, object())
msgbox % objPrint(list) ; (( 1 ) 2 (( 3 4 ) 5 )(((())))(( 6 )) 7 8 ())
msgbox % objPrint(objFlatten(list)) ; ( 1 2 3 4 5 6 7 8 )
return
!r::reload
!q::exitapp
objPrint(ast, reserved=0)
{
if !isobject(ast)
return " " ast " "
if !reserved
reserved := object("seen" . &ast, 1) ; to keep track of unique objects within top object
enum := ast._newenum()
while enum[key, value]
{
if reserved["seen" . &value]
continue ; don't copy repeat objects (circular references)
; string .= key . ": " . objPrint(value, reserved)
string .= objPrint(value, reserved)
}
return "(" string ")"
}
objFlatten(ast)
{
if !isobject(ast)
return ast
flat := object() ; flat object
enum := ast._newenum()
while enum[key, value]
{
if !isobject(value)
flat._Insert(value)
else
{
next := objFlatten(value)
loop % next._MaxIndex()
flat._Insert(next[A_Index])
}
}
return flat
}
[edit] C
Example in C using a quick and dirty implementation of lists as a singly-linked list of structs.
List header file:
// 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__
List functions:
// 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);
}
The Flatten algorithm (with lots comments since this is a one-off lists implementation):
// 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;
}
}
}
}
The test program:
// 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;
}
Output:
Original List : [[1],2,[[3,4],5],[[[]]],[[[6]]],7,8,[]] Flattened List: [1,2,3,4,5,6,7,8]
[edit] C++
#include <list>
#include <boost/any.hpp>
typedef std::list<boost::any> anylist;
void flatten(std::list<boost::any>& list)
{
typedef anylist::iterator iterator;
iterator current = list.begin();
while (current != list.end())
{
if (current->type() == typeid(anylist))
{
iterator next = current;
++next;
list.splice(next, boost::any_cast<anylist&>(*current));
next = current;
++next;
list.erase(current);
current = next;
}
else
++current;
}
}
Use example:
Since C++ currently doesn't have nice syntax for initializing lists, this includes a simple parser to create lists of integers and sublists. Also, there's no standard way to output this type of list, so some output code is added as well.
#include <cctype>
#include <iostream>
// *******************
// * the list parser *
// *******************
void skipwhite(char const** s)
{
while (**s && std::isspace((unsigned char)**s))
{
++*s;
}
}
anylist create_anylist_i(char const** s)
{
anylist result;
skipwhite(s);
if (**s != '[')
throw "Not a list";
++*s;
while (true)
{
skipwhite(s);
if (!**s)
throw "Error";
else if (**s == ']')
{
++*s;
return result;
}
else if (**s == '[')
result.push_back(create_anylist_i(s));
else if (std::isdigit((unsigned char)**s))
{
int i = 0;
while (std::isdigit((unsigned char)**s))
{
i = 10*i + (**s - '0');
++*s;
}
result.push_back(i);
}
else
throw "Error";
skipwhite(s);
if (**s != ',' && **s != ']')
throw "Error";
if (**s == ',')
++*s;
}
}
anylist create_anylist(char const* i)
{
return create_anylist_i(&i);
}
// *************************
// * printing nested lists *
// *************************
void print_list(anylist const& list);
void print_item(boost::any const& a)
{
if (a.type() == typeid(int))
std::cout << boost::any_cast<int>(a);
else if (a.type() == typeid(anylist))
print_list(boost::any_cast<anylist const&>(a));
else
std::cout << "???";
}
void print_list(anylist const& list)
{
std::cout << '[';
anylist::const_iterator iter = list.begin();
while (iter != list.end())
{
print_item(*iter);
++iter;
if (iter != list.end())
std::cout << ", ";
}
std::cout << ']';
}
// ***************************
// * The actual test program *
// ***************************
int main()
{
anylist list =
create_anylist("[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]");
print_list(list);
std::cout << "\n";
flatten(list);
print_list(list);
std::cout << "\n";
}
The output of this program is
[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] [1, 2, 3, 4, 5, 6, 7, 8]
[edit] C#
Works with: C# version 3+
Actual Workhorse code
using System;
using System.Collections;
using System.Linq;
namespace RosettaCodeTasks
{
static class FlattenList
{
public static ArrayList Flatten(this ArrayList List)
{
ArrayList NewList = new ArrayList ( );
NewList.AddRange ( List );
while ( NewList.OfType<ArrayList> ( ).Count ( ) > 0 )
{
int index = NewList.IndexOf ( NewList.OfType<ArrayList> ( ).ElementAt ( 0 ) );
ArrayList Temp = (ArrayList)NewList[index];
NewList.RemoveAt ( index );
NewList.InsertRange ( index, Temp );
}
return NewList;
}
}
}
Method showing population of arraylist and usage of flatten method
using System;
using System.Collections;
namespace RosettaCodeTasks
{
class Program
{
static void Main ( string[ ] args )
{
ArrayList Parent = new ArrayList ( );
Parent.Add ( new ArrayList ( ) );
((ArrayList)Parent[0]).Add ( 1 );
Parent.Add ( 2 );
Parent.Add ( new ArrayList ( ) );
( (ArrayList)Parent[2] ).Add ( new ArrayList ( ) );
( (ArrayList)( (ArrayList)Parent[2] )[0] ).Add ( 3 );
( (ArrayList)( (ArrayList)Parent[2] )[0] ).Add ( 4 );
( (ArrayList)Parent[2] ).Add ( 5 );
Parent.Add ( new ArrayList ( ) );
( (ArrayList)Parent[3] ).Add ( new ArrayList ( ) );
( (ArrayList)( (ArrayList)Parent[3] )[0] ).Add ( new ArrayList ( ) );
Parent.Add ( new ArrayList ( ) );
( (ArrayList)Parent[4] ).Add ( new ArrayList ( ) );
( (ArrayList)( (ArrayList)Parent[4] )[0] ).Add ( new ArrayList ( ) );
( (ArrayList)( (ArrayList)( (ArrayList)( (ArrayList)Parent[4] )[0] )[0] ) ).Add ( 6 );
Parent.Add ( 7 );
Parent.Add ( 8 );
Parent.Add ( new ArrayList ( ) );
foreach ( Object o in Parent.Flatten ( ) )
{
Console.WriteLine ( o.ToString ( ) );
}
}
}
}
[edit] Clojure
The following returns a lazy sequence of the flattened data structure.
(defn flatten [coll]
(lazy-seq
(when-let [s (seq coll)]
(if (coll? (first s))
(concat (flatten (first s)) (flatten (rest s)))
(cons (first s) (flatten (rest s)))))))
An alternative approach (from clojure.contrib.seq-utils).
(defn flatten [x]
(filter (complement sequential?)
(rest (tree-seq sequential? seq x))))
[edit] Common Lisp
(defun flatten (tree)
(let ((result '()))
(labels ((scan (item)
(if (listp item)
(map nil #'scan item)
(push item result))))
(scan tree))
(nreverse result)))
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.
[edit] 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 Works with: D version 2 the same way as it Works with: D version 1 using Library: tango
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());
}
}
Output:
[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] [1, 2, 3, 4, 5, 6, 7, 8]
[edit] E
def flatten(nested) {
def flat := [].diverge()
def recur(x) {
switch (x) {
match list :List { for elem in list { recur(elem) } }
match other { flat.push(other) }
}
}
recur(nested)
return flat.snapshot()
}
? flatten([[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []])
# value: [1, 2, 3, 4, 5, 6, 7, 8]
[edit] Erlang
There's a standard function (lists:flatten/2) that does it more efficiently, but this is the cleanest implementation you could have;
flatten([]) -> [];
flatten([H|T]) -> flatten(H) ++ flatten(T);
flatten(H) -> [H].
[edit] Factor
USE: sequences.deep
( scratchpad ) { { 1 } 2 { { 3 4 } 5 } { { { } } } { { { 6 } } } 7 8 { } } flatten .
{ 1 2 3 4 5 6 7 8 }
[edit] Groovy
List.flatten() is a Groovy built-in that returns a flattened copy of the source list:
assert [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []].flatten() == [1, 2, 3, 4, 5, 6, 7, 8]
[edit] Haskell
In Haskell we have to interpret this structure as an algebraic data type.
import Data.Tree
-- [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]
-- implemented as multiway tree:
-- Data.Tree represents trees where nodes have values too, unlike the trees in our problem.
-- so we use a list as that value, where a node will have an empty list value,
-- and a leaf will have a one-element list value and no subtrees
list :: Tree [Int]
list = Node [] [
Node [] [Node [1] []],
Node [2] [],
Node [] [
Node [] [ Node [3] [],Node [4] []],
Node [5] []
],
Node [] [Node [] [Node [] []]],
Node [] [Node [] [Node [6] []]],
Node [7] [],
Node [8] [],
Node [] []
]
flattenList = concat.flatten
Flattening the list:
*Main> flattenList list [1,2,3,4,5,6,7,8]
Alternately:
data Tree a = Leaf a | Node [Tree a]
flatten :: Tree a -> [a]
flatten (Leaf x) = [x]
flatten (Node xs) = concatMap flatten xs
main = print $ flatten $ Node [Node [Leaf 1],
Leaf 2,
Node [Node [Leaf 3, Leaf 4], Leaf 5],
Node [Node [Node []]],
Node [Node [Node [Leaf 6]]],
Leaf 7,
Leaf 8,
Node []]
-- output: [1,2,3,4,5,6,7,8]
Yet another choice, custom data structure, efficient lazy flattening:
data NestedList a = NList [NestedList a] | Entry a
flatten :: NestedList a -> [a]
flatten nl = flatten' nl []
where
-- By passing through a list which the results will be preprended to we allow efficient lazy evaluation
flatten' :: NestedList a -> [a] -> [a]
flatten' (Entry a) cont = a:cont
flatten' (NList entries) cont = foldr flatten' cont entries
example :: NestedList Int
example = NList [ NList [Entry 1], Entry 2, NList [NList [Entry 3, Entry 4], Entry 5], NList [NList [NList []]], NList [ NList [ NList [Entry 6]]], Entry 7, Entry 8, NList []]
main :: IO ()
main = print $ flatten example
-- output [1,2,3,4,5,6,7,8]
[edit] Icon and Unicon
[edit] 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.
link strings # for compress,deletec,pretrim
procedure sflatten(s) # uninteresting string solution
return pretrim(trim(compress(deletec(s,'[ ]'),',') ,','),',')
end
Library: Icon Programming Library The solution uses several procedures from strings in the IPL
This procedure is more in the spirit of the task handling actual lists rather than representations. It uses a recursive approach using some of the built-in list manipulation functions and operators.
procedure flatten(L) # in the spirt of the problem a structure
local l,x
l := []
every x := !L do
if type(x) == "list" then l |||:= flatten(x)
else put(l,x)
return l
end
Finally a demo routine to drive these and a helper to show how it works.
procedure main()
write(sflatten(" [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]"))
writelist(flatten( [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]))
end
procedure writelist(L)
writes("[")
every writes(" ",image(!L))
write(" ]")
return
end
[edit] Unicon
This Icon solution works in Unicon.
[edit] Ioke
iik> [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] flatten
[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] flatten
+> [1, 2, 3, 4, 5, 6, 7, 8]
[edit] J
Solution:
flatten =: [: ; <S:0
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:
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│││ │││└┘│││└─┘││ │ │ │
│ │ │││└─┴─┘││ ││└──┘│└───┘│ │ │ │
│ │ ││└─────┘│ ││ │ │ │ │ │
│ │ │└───────┴─┘│ │ │ │ │ │
└───┴─┴───────────┴────┴─────┴─┴─┴──┘
(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.)
flatten li
1 2 3 4 5 6 7 8
Alternative Solution:
The previous solution can be generalized to flatten the nesting and shape for a list of arbitrary values that include arrays of any rank:
flatten2 =: [: ; <@,S:0
Example:
]li2 =. (<1) ; 2; ((<3;4); 5 + i.3 4) ; ((<a:)) ; ((<(<17))) ; 18; 19; <a:
┌───┬─┬─────────────────────┬────┬──────┬──┬──┬──┐
│┌─┐│2│┌───────┬───────────┐│┌──┐│┌────┐│18│19│┌┐│
││1││ ││┌─────┐│ 5 6 7 8│││┌┐│││┌──┐││ │ ││││
│└─┘│ │││┌─┬─┐││ 9 10 11 12│││││││││17│││ │ │└┘│
│ │ ││││3│4│││13 14 15 16│││└┘│││└──┘││ │ │ │
│ │ │││└─┴─┘││ ││└──┘│└────┘│ │ │ │
│ │ ││└─────┘│ ││ │ │ │ │ │
│ │ │└───────┴───────────┘│ │ │ │ │ │
└───┴─┴─────────────────────┴────┴──────┴──┴──┴──┘
flatten2 li
1 2 3 4 5 6 7 8
flatten2 li2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
[edit] Java
Works with: Java version 1.5+
import java.util.LinkedList;
import java.util.List;
import java.util.Arrays;
public class Flatten {
public static List<Object> flatten(List<?> list){
List<Object> retVal = new LinkedList<Object>();
for(Object item:list){
if(item instanceof List){
retVal.addAll(flatten((List)item));
}else{
retVal.add(item);
}
}
return retVal;
}
public static void main(String[] args){
List<Object> test = Arrays.<Object>asList(
Arrays.<Object>asList(1),
2,
Arrays.<Object>asList(
Arrays.<Object>asList(3,4),
5
),
Arrays.<Object>asList(
Arrays.<Object>asList(
Arrays.<Object>asList()
)
),
Arrays.<Object>asList(
Arrays.<Object>asList(
Arrays.<Object>asList(6)
)
),
7,
8,
Arrays.<Object>asList()
);
System.out.println(test);
System.out.println(flatten(test));
}
}
Output:
[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] [1, 2, 3, 4, 5, 6, 7, 8]
[edit] JavaScript
Library: Prototype Works with: a browser
<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("<p>before</p>");
a.each(function(e){document.write("<div>" + e + " " + typeof(e) + "</div>")});
var f = a.flatten();
document.write("<p>after</p>");
f.each(function(e){document.write("<div>" + e + " " + typeof(e) + "</div>")});
</script>
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
[edit] Lua
function flatten(list)
if type(list) ~= "table" then return {list} end
local flat_list = {}
for _, elem in ipairs(list) do
for _, val in ipairs(flatten(elem)) do
flat_list[#flat_list + 1] = val
end
end
return flat_list
end
test_list = {{1}, 2, {{3,4}, 5}, {{{}}}, {{{6}}}, 7, 8, {}}
print(table.concat(flatten(test_list), ","))
[edit] 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
[edit] Mathematica
Flatten@{{1}, 2, {{3, 4}, 5}, {{{}}}, {{{6}}}, 7, 8, {}}
[edit] Objective-C
Works with: Cocoa and Works with: GNUstep
#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;
}
An alternative solution
Works with: Cocoa
#import <Foundation/Foundation.h>
@interface NSArray (FlattenExt)
@property (nonatomic, readonly) NSArray *flattened;
@end
@implementation NSArray (FlattenExt)
-(NSArray *) flattened {
NSMutableArray *flattened = [[NSMutableArray alloc] initWithCapacity:self.count];
for (id object in self) {
if ([object isKindOfClass:[NSArray class]])
[flattened addObjectsFromArray:((NSArray *)object).flattened];
else 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;
}
[edit] OCaml
# let flatten = List.concat ;;
val flatten : 'a list list -> 'a list = <fun>
# let li = [[1]; 2; [[3;4]; 5]; [[[]]]; [[[6]]]; 7; 8; []] ;;
^^^
Error: This expression has type int but is here used with type int list
# (* use another data which can be accepted by the type system *)
flatten [[1]; [2; 3; 4]; []; [5; 6]; [7]; [8]] ;;
- : int list = [1; 2; 3; 4; 5; 6; 7; 8]
Since OCaml is statically typed, it is not possible to have a value that could be both a list and a non-list. Instead, we can use an algebraic datatype:
# type 'a tree = Leaf of 'a | Node of 'a tree list ;;
type 'a tree = Leaf of 'a | Node of 'a tree list
# let rec flatten = function
Leaf x -> [x]
| Node xs -> List.concat (List.map flatten xs) ;;
val flatten : 'a tree -> 'a list = <fun>
# flatten (Node [Node [Leaf 1]; Leaf 2; Node [Node [Leaf 3; Leaf 4]; Leaf 5]; Node [Node [Node []]]; Node [Node [Node [Leaf 6]]]; Leaf 7; Leaf 8; Node []]) ;;
- : int list = [1; 2; 3; 4; 5; 6; 7; 8]
[edit] Oz
Oz has a standard library function "Flatten":
{Show {Flatten [[1] 2 [[3 4] 5] [[nil]] [[[6]]] 7 8 nil]}}
A simple, non-optimized implementation could look like this:
fun {Flatten2 Xs}
case Xs of nil then nil
[] X|Xr then
{Append {Flatten2 X} {Flatten2 Xr}}
else [Xs]
end
end
[edit] Perl
sub flatten {
map { ref eq 'ARRAY' ? flatten(@$_) : $_ } @_
}
my @lst = ([1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []);
print flatten(@lst), "\n";
[edit] Perl 6
Works with: Rakudo version #22 "Thousand Oaks"
multi flatten (@a) { map { flatten $^x }, @a }
multi flatten ($x) { $x }
[edit] PHP
/* Note: This code is only for PHP 4.
It won't work on PHP 5 due to the change in behavior of array_merge(). */
while (array_filter($lst, 'is_array'))
$lst = call_user_func_array('array_merge', $lst);
Explanation: while $lst has any elements which are themselves arrays (i.e. $lst is not flat), we merge the elements all together (in PHP 4, array_merge() treated non-array arguments as if they were 1-element arrays; PHP 5 array_merge() no longer allows non-array arguments.), thus flattening the top level of any embedded arrays. Repeat this process until the array is flat.
[edit] Recursive
<?php
function flatten($ary) {
$result = array();
foreach ($ary as $x) {
if (is_array($x))
// append flatten($x) onto $result
array_splice($result, count($result), 0, flatten($x));
else
$result[] = $x;
}
return $result;
}
$lst = array(array(1), 2, array(array(3, 4), 5), array(array(array())), array(array(array(6))), 7, 8, array());
var_dump(flatten($lst));
?>
[edit] Non-recursive
Function flat is iterative and flattens the array in-place.
<?php
function flat(&$ary) { // argument must be by reference or array will just be copied
for ($i = 0; $i < count($ary); $i++) {
while (is_array($ary[$i])) {
array_splice($ary, $i, 1, $ary[$i]);
}
}
}
$lst = array(array(1), 2, array(array(3, 4), 5), array(array(array())), array(array(array(6))), 7, 8, array());
flat($lst);
var_dump($lst);
?>
[edit] PicoLisp
(de flatten (X)
(make # Build a list
(recur (X) # recursively over 'X'
(if (atom X)
(link X) # Put atoms into the result
(mapc recurse X) ) ) ) ) # or recurse on sub-lists
or a more succint way using fish:
(de flatten (X)
(fish atom X) )
[edit] PL/I
list = translate (list, ' ', '[]' );
list = '[' || list || ']';
[edit] Prolog
flatten([], []).
flatten(E, [E]) :- atom(E).
flatten([E|T], F) :-
flatten(E, Ef),
flatten(T, Tf),
append(Ef, Tf, F), !.
[edit] Python
[edit] Recursive
Function flatten is recursive and preserves its argument:
>>> def flatten(lst):
return sum( ([x] if not isinstance(x, list) else flatten(x)
for x in lst), [] )
>>> lst = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]
>>> flatten(lst)
[1, 2, 3, 4, 5, 6, 7, 8]
[edit] Non-recursive
Function flat is iterative and flattens the list in-place. It follows the Python idiom of returning None when acting in-place:
>>> def flat(lst):
i=0
while i<len(lst):
while True:
try:
lst[i:i+1] = lst[i]
except (TypeError, IndexError):
break
i += 1
>>> lst = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]
>>> flat(lst)
>>> lst
[1, 2, 3, 4, 5, 6, 7, 8]
[edit] Generative
This method shows a solution using Python generators.
flatten is a generator that yields the non-list values of its input in order.
The primary advantage of generators is that there are no temporary values needed.
For large input, this can reduce memory usage dramatically.
The generator is converted back to a list before printing.
>>> def flatten(lst):
for x in lst:
if isinstance(x, list):
for x in flatten(x):
yield x
else:
yield x
>>>lst = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]
>>>print list(flatten(lst))
[1, 2, 3, 4, 5, 6, 7, 8]
[edit] R
x <- list(list(1), 2, list(list(3, 4), 5), list(list(list())), list(list(list(6))), 7, 8, list())
unlist(x)
[edit] REBOL
Sample:
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
]
>> flatten [[1] 2 [[3 4] 5] [[[]]] [[[6]]] 7 8 []] == [1 2 3 4 5 6 7 8]
[edit] Ruby
flatten is a built-in method of Arrays
flat = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []].flatten
p flat # => [1, 2, 3, 4, 5, 6, 7, 8]
[edit] Scala
def flatList(l: List[_]): List[Any] = l match {
case Nil => Nil
case (head: List[_]) :: tail => flatList(head) ::: flatList(tail)
case head :: tail => head :: flatList(tail)
}
Sample:
scala> List(List(1), 2, List(List(3, 4), 5), List(List(List())), List(List(List(6))), 7, 8, List()) res10: List[Any] = List(List(1), 2, List(List(3, 4), 5), List(List(List())), List(List(List(6))), 7, 8, List()) scala> flatList(res10) res12: List[Any] = List(1, 2, 3, 4, 5, 6, 7, 8)
[edit] Scheme
> (define (flatten x)
(cond ((null? x) '())
((not (pair? x)) (list x))
(else (append (flatten (car x))
(flatten (cdr x))))))
> (flatten '((1) 2 ((3 4) 5) ((())) (((6))) 7 8 ()))
(1 2 3 4 5 6 7 8)
[edit] Slate
s@(Sequence traits) flatten
[
[| :out | s flattenOn: out] writingAs: s
].
s@(Sequence traits) flattenOn: w@(WriteStream traits)
[
s do: [| :value |
(value is: s)
ifTrue: [value flattenOn: w]
ifFalse: [w nextPut: value]].
].
[edit] Smalltalk
Works with: GNU Smalltalk
OrderedCollection extend [
flatten [ |f|
f := OrderedCollection new.
self do: [ :i |
i isNumber
ifTrue: [ f add: i ]
ifFalse: [ |t|
t := (OrderedCollection withAll: i) flatten.
f addAll: t
]
].
^ f
]
].
|list|
list := OrderedCollection
withAll: { {1} . 2 . { {3 . 4} . 5 } .
{{{}}} . {{{6}}} . 7 . 8 . {} }.
(list flatten) printNl.
[edit] Suneido
ob = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]
ob.Flatten()
Output:
#(1, 2, 3, 4, 5, 6, 7, 8)
[edit] Tcl
proc flatten list {
for {set old {}} {$old ne $list} {} {
set old $list
set list [join $list]
}
return $list
}
puts [flatten {{1} 2 {{3 4} 5} {{{}}} {{{6}}} 7 8 {}}]
# ===> 1 2 3 4 5 6 7 8
Note that because lists are not syntactically distinct from strings, it is probably a mistake to use this procedure with real (especially non-numeric) data. Also note that there are no parentheses around the outside of the list when printed; this is just a feature of how Tcl regards lists, and the value is a proper list (it can be indexed into with lindex, iterated over with foreach, etc.)
Another implementation that's slightly more terse:
proc flatten {data} {
while { $data != [set data [join $data]] } { }
return $data
}
puts [flatten {{1} 2 {{3 4} 5} {{{}}} {{{6}}} 7 8 {}}]
# ===> 1 2 3 4 5 6 7 8
[edit] TI-89 BASIC
There is no nesting of lists or other data structures in TI-89 BASIC, short of using variable names as pointers.
[edit] Trith
[[1] 2 [[3 4] 5] [[[]]] [[[6]]] 7 8 []] flatten
[edit] VBScript
Working on embedded arrays as that's about the closest we get to lists.
[edit] Implementation
class flattener
dim separator
sub class_initialize
separator = ","
end sub
private function makeflat( a )
dim i
dim res
for i = lbound( a ) to ubound( a )
if isarray( a( i ) ) then
res = res & makeflat( a( i ) )
else
res = res & a( i ) & separator
end if
next
makeflat = res
end function
public function flatten( a )
dim res
res = makeflat( a )
res = left( res, len( res ) - len(separator))
res = split( res, separator )
flatten = res
end function
public property let itemSeparator( c )
separator = c
end property
end class
[edit] Invocation
dim flat
set flat = new flattener
flat.itemSeparator = "~"
wscript.echo join( flat.flatten( array( array( 1 ),2,array(array(3,4),5),array(array(array())),array(array(array(6))),7,8,array())), "!")
[edit] Output
1!2!3!4!5!6!7!8
Categories: 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 | Python | R | REBOL | Ruby | Scala | Scheme | Slate | Smalltalk | Suneido | Tcl | TI-89 BASIC | Trith | VBScript
