Flatten a list
From Rosetta Code
Flatten a list is a programming task. Visitors like you are encouraged to solve it according to the task description, using any language they may happen to 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] 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] 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 (next s)))
(cons (first s) (flatten (next 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] 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] Ioke
iik> [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] flatten
[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] flatten
+> [1, 2, 3, 4, 5, 6, 7, 8]
[edit] J
Solution:
flatten =: [: ; <S:0
Example:
NB. create and display nested noun li
]li =. (<1) ; 2; ((<3;4); 5) ; ((<a:)) ; ((<(<6))) ; 7; 8; <a:
+---+-+-----------+----+-----+-+-+--+
|+-+|2|+-------+-+|+--+|+---+|7|8|++|
||1|| ||+-----+|5|||++|||+-+|| | ||||
|+-+| |||+-+-+|| |||||||||6||| | |++|
| | ||||3|4||| |||++|||+-+|| | | |
| | |||+-+-+|| ||+--+|+---+| | | |
| | ||+-----+| || | | | | |
| | |+-------+-+| | | | | |
+---+-+-----------+----+-----+-+-+--+
flatten li
1 2 3 4 5 6 7 8
[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] 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] Python
[edit] Recursive
Function flatten is recursive and preserves its argument:
>>> def flatten(lst):
return sum( ([x] if type(x) is not 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] 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] 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.)
[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] 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 | C++ | Clojure | Common Lisp | E | Erlang | Factor | Groovy | Haskell | Ioke | J | Java | JavaScript | Prototype | Lua | Logo | OCaml | Oz | Perl | Perl 6 | PHP | PicoLisp | PL/I | Python | R | REBOL | Ruby | Scala | Scheme | Slate | Smalltalk | Tcl | TI-89 BASIC | VBScript
