Flatten a list: Difference between revisions
Add implementation in Lua |
Added Oz solution. |
||
Line 423: | Line 423: | ||
- : int list = [1; 2; 3; 4; 5; 6; 7; 8]</lang> |
- : int list = [1; 2; 3; 4; 5; 6; 7; 8]</lang> |
||
</div> |
</div> |
||
=={{header|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> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
Revision as of 06:55, 12 December 2009
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
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
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]
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 (next s))) (cons (first s) (flatten (next 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.
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>
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>
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>
Java
<lang java5>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)); }
}</lang> Output:
[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] [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(l)
local rv rv = {} for _, outer_v in ipairs(l) do if type(outer_v) == "table" then for _, inner_v in ipairs(flatten(outer_v)) do table.insert(rv, inner_v) end else table.insert(rv, outer_v) end end return rv
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>
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>
Python
Recursive
Function flatten
is recursive and preserves its argument:
<lang python>>>> 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]</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>
R
<lang R>l <- list(list(1), 2, list(list(3, 4), 5), list(list(list())), list(list(list(6))), 7, 8, list()) unlist(l)</lang>
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>
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>
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.)
TI-89 BASIC
There is no nesting of lists or other data structures in TI-89 BASIC, short of using variable names as pointers.