Flatten a list: Difference between revisions
(Both recursive and iterative forms are encouraged (As in the original Python solution)..) |
|||
Line 1: | Line 1: | ||
{{task}} |
{{task}} |
||
Write a function to flatten the nesting |
Write a function to flatten the nesting in an arbitrary [[wp:List (computing)|list]] of values. Your program should work on the equivalent of this list: |
||
[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] |
[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] |
||
Where the correct result would be the list: |
Where the correct result would be the list: |
||
Line 43: | Line 43: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
===Recursive=== |
|||
⚫ | |||
⚫ | |||
<lang python>>>> def flatten(lst): |
<lang python>>>> def flatten(lst): |
||
return sum( ([x] if type(x) is not list else flatten(x) |
return sum( ([x] if type(x) is not list else flatten(x) |
||
Line 51: | Line 53: | ||
>>> flatten(lst) |
>>> flatten(lst) |
||
[1, 2, 3, 4, 5, 6, 7, 8]</lang> |
[1, 2, 3, 4, 5, 6, 7, 8]</lang> |
||
===Non-recursive=== |
|||
Function flat is iterative and flattens the list in-place: |
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): |
<lang python>>>> def flat(lst): |
||
i=0 |
i=0 |
Revision as of 00:46, 17 August 2009
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
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 can be a list, and therefore they can not be nil.
OCaml
<lang ocaml># let rec flatten = function
[] -> [] | l::r -> l @ flatten r ;;
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>
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>
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>
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>