Flatten a list

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>