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.

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>

J

Solution: flatten =: [: ; <S:0

Example:

   ]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

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 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>

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>

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>

PHP

<lang php>/* Note: This code is only for PHP 4, it won't work on PHP 5. */ while(array_filter($x,is_array)) $x=call_user_func_array(array_merge,$x); </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

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>

Smalltalk

Works with: GNU 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.

TI-89 BASIC

There is no nesting of lists or other data structures in TI-89 BASIC, short of using variable names as pointers.