{{task}}

;Task: 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, []] Where the correct result would be the list: [1, 2, 3, 4, 5, 6, 7, 8]

;Related task:

• [[Tree traversal]]

8th

\ take a list (array) and flatten it:

: (flatten)  \ a -- a
	(
		\ is it a number?
		dup >kind ns:n n:= if
			\ yes.  so add to the list
			r> swap a:push >r
		else
			\ it is not, so flatten it
			(flatten)
		then
		drop
	) a:each drop ;

: flatten \ a -- a
	[] >r (flatten) r> ;

[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]
dup . cr
flatten
. cr
bye

{{out}} [[1],2,[[3,4],5],[[[]]],[[[6]]],7,8,[]]

[1,2,3,4,5,6,7,8]

ACL2

(defun flatten (tr)
   (cond ((null tr) nil)
         ((atom tr) (list tr))
         (t (append (flatten (first tr))
                    (flatten (rest tr))))))

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

Ada

nestable_lists.ads:

generic
   type Element_Type is private;
   with function To_String (E : Element_Type) return String is <>;
package Nestable_Lists is

   type Node_Kind is (Data_Node, List_Node);

   type Node (Kind : Node_Kind);

   type List is access Node;

   type Node (Kind : Node_Kind) is record
      Next : List;
      case Kind is
         when Data_Node =>
            Data    : Element_Type;
         when List_Node =>
            Sublist : List;
      end case;
   end record;

   procedure Append (L : in out List; E : Element_Type);
   procedure Append (L : in out List; N : List);

   function Flatten (L : List) return List;

   function New_List (E : Element_Type) return List;
   function New_List (N : List) return List;

   function To_String (L : List) return String;

end Nestable_Lists;

nestable_lists.adb:

with Ada.Strings.Unbounded;

package body Nestable_Lists is

   procedure Append (L : in out List; E : Element_Type) is
   begin
      if L = null then
         L := new Node (Kind => Data_Node);
         L.Data := E;
      else
         Append (L.Next, E);
      end if;
   end Append;

   procedure Append (L : in out List; N : List) is
   begin
      if L = null then
         L := new Node (Kind => List_Node);
         L.Sublist := N;
      else
         Append (L.Next, N);
      end if;
   end Append;

   function Flatten (L : List) return List is
      Result  : List;
      Current : List := L;
      Temp    : List;
   begin
      while Current /= null loop
         case Current.Kind is
            when Data_Node =>
               Append (Result, Current.Data);
            when List_Node =>
               Temp := Flatten (Current.Sublist);
               while Temp /= null loop
                  Append (Result, Temp.Data);
                  Temp := Temp.Next;
               end loop;
         end case;
         Current := Current.Next;
      end loop;
      return Result;
   end Flatten;

   function New_List (E : Element_Type) return List is
   begin
      return  new Node'(Kind => Data_Node, Data => E, Next => null);
   end New_List;

   function New_List (N : List) return List is
   begin
      return new Node'(Kind => List_Node, Sublist => N, Next => null);
   end New_List;

   function To_String (L : List) return String is
      Current : List := L;
      Result  : Ada.Strings.Unbounded.Unbounded_String;
   begin
      Ada.Strings.Unbounded.Append (Result, "[");
      while Current /= null loop
         case Current.Kind is
            when Data_Node =>
               Ada.Strings.Unbounded.Append
                 (Result, To_String (Current.Data));
            when List_Node =>
               Ada.Strings.Unbounded.Append
                 (Result, To_String (Current.Sublist));
         end case;
         if Current.Next /= null then
            Ada.Strings.Unbounded.Append (Result, ", ");
         end if;
         Current := Current.Next;
      end loop;
      Ada.Strings.Unbounded.Append (Result, "]");
      return Ada.Strings.Unbounded.To_String (Result);
   end To_String;

end Nestable_Lists;

example usage:

with Ada.Text_IO;
with Nestable_Lists;

procedure Flatten_A_List is
   package Int_List is new Nestable_Lists
     (Element_Type => Integer,
      To_String    => Integer'Image);

   List : Int_List.List := null;
begin
   Int_List.Append (List, Int_List.New_List (1));
   Int_List.Append (List, 2);
   Int_List.Append (List, Int_List.New_List (Int_List.New_List (3)));
   Int_List.Append (List.Next.Next.Sublist.Sublist, 4);
   Int_List.Append (List.Next.Next.Sublist, 5);
   Int_List.Append (List, Int_List.New_List (Int_List.New_List (null)));
   Int_List.Append (List, Int_List.New_List (Int_List.New_List
                    (Int_List.New_List (6))));
   Int_List.Append (List, 7);
   Int_List.Append (List, 8);
   Int_List.Append (List, null);

   declare
      Flattened : constant Int_List.List := Int_List.Flatten (List);
   begin
      Ada.Text_IO.Put_Line (Int_List.To_String (List));
      Ada.Text_IO.Put_Line (Int_List.To_String (Flattened));
   end;
end Flatten_A_List;

Output:

[[ 1],  2, [[ 3,  4],  5], [[[]]], [[[ 6]]],  7,  8, []]
[ 1,  2,  3,  4,  5,  6,  7,  8]

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("]")

{{out}}

 [1, 2, 3, 4, 5, 6, 7, 8]

Aime

void
show_list(list l)
{
    integer i, k;

    o_text("[");

    i = 0;
    while (i < ~l) {
        o_text(i ? ", " : "");
        if (l_j_integer(k, l, i)) {
            o_integer(k);
        } else {
            show_list(l[i]);
        }
        i += 1;
    }

    o_text("]");
}

list
flatten(list c, object o)
{
    if (__id(o) == INTEGER_ID) {
        c.append(o);
    } else {
        l_ucall(o, flatten, 1, c);
    }

    c;
}

integer
main(void)
{
    list l;

    l = list(list(1), 2, list(list(3, 4), 5),
             list(list(list())), list(list(list(6))), 7, 8, list());

    show_list(l);
    o_byte('\n');

    show_list(flatten(list(), l));
    o_byte('\n');

    return 0;
}

{{out}}

[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]
[1, 2, 3, 4, 5, 6, 7, 8]

ALGOL 68

{{works with|ALGOL 68|Revision 1 - no extensions to language used}}

{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-1.18.0/algol68g-1.18.0-9h.tiny.el5.centos.fc11.i386.rpm/download 1.18.0-9h.tiny]}}

{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d]}}

Flattening is built in to all of Algol68's ''transput'' routines. The following example also uses ''widening'', where scalars are converted into arrays.

main:(
  [][][]INT list = ((1), 2, ((3,4), 5), ((())), (((6))), 7, 8, ());
  print((list, new line))
)

{{out}}

         +1         +2         +3         +4         +5         +6         +7         +8

GNU APL

Using (monadic) enlist function ε. Sometimes called 'Super Ravel'.

      ⊢list←(2 3ρι6)(2 2ρ(7 8(2 2ρ9 10 11 12)13)) 'ABCD'
┏→━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃┏→━━━━┓ ┏→━━━━━━━━━┓ "ABCD"┃
┃↓1 2 3┃ ↓      7  8┃       ┃
┃┃4 5 6┃ ┃          ┃       ┃
┃┗━━━━━┛ ┃┏→━━━━┓ 13┃       ┃
┃        ┃↓ 9 10┃   ┃       ┃
┃        ┃┃11 12┃   ┃       ┃
┃        ┃┗━━━━━┛   ┃       ┃
┃        ┗∊━━━━━━━━━┛       ┃
┗∊∊━━━━━━━━━━━━━━━━━━━━━━━━━┛
      ∊list
┏→━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃1 2 3 4 5 6 7 8 9 10 11 12 13 'A''B''C''D'┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛

AppleScript

my_flatten({{1}, 2, {{3, 4}, 5}, {{{}}}, {{{6}}}, 7, 8, {}})

on my_flatten(aList)
    if class of aList is not list then
        return {aList}
    else if length of aList is 0 then
        return aList
    else
        return my_flatten(first item of aList) & (my_flatten(rest of aList))
    end if
end my_flatten

Or, expressed in terms of a generic '''concatMap''': {{trans|JavaScript}}

-- flatten :: Tree a -> [a]
on flatten(t)
    if class of t is list then
        concatMap(flatten, t)
    else
        t
    end if
end flatten

-- TEST -----------------------------------------------------------------------
on run

    flatten([[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []])

    --> {1, 2, 3, 4, 5, 6, 7, 8}
end run


-- GENERIC FUNCTIONS ----------------------------------------------------------

-- concatMap :: (a -> [b]) -> [a] -> [b]
on concatMap(f, xs)
    set lst to {}
    set lng to length of xs
    tell mReturn(f)
        repeat with i from 1 to lng
            set lst to (lst & |λ|(item i of xs, i, xs))
        end repeat
    end tell
    return lst
end concatMap

-- Lift 2nd class handler function into 1st class script wrapper
-- mReturn :: Handler -> Script
on mReturn(f)
    if class of f is script then
        f
    else
        script
            property |λ| : f
        end script
    end if
end mReturn

{{Out}}

{1, 2, 3, 4, 5, 6, 7, 8}

AutoHotkey

{{works with | AutoHotkey_L}}

AutoHotkey doesn't have built in list data type. This examples simulates a list in a tree type object and flattens that tree.

list := object(1, object(1, 1), 2, 2, 3, object(1, object(1, 3, 2, 4)
, 2, 5), 4, object(1, object(1, object(1, object()))), 5
, object(1, object(1, 6)), 6, 7, 7, 8, 9, object())
msgbox % objPrint(list) ; (( 1 ) 2 (( 3  4 ) 5 )(((())))(( 6 )) 7  8 ())
msgbox % objPrint(objFlatten(list)) ; ( 1  2  3  4  5  6  7  8 )
return

!r::reload
!q::exitapp

objPrint(ast, reserved=0)
{
  if !isobject(ast)
    return " " ast " "

  if !reserved
    reserved := object("seen" . &ast, 1)  ; to keep track of unique objects within top object

  enum := ast._newenum()
  while enum[key, value]
  {
    if reserved["seen" . &value]
      continue  ; don't copy repeat objects (circular references)
;   string .= key . ": " . objPrint(value, reserved)
    string .= objPrint(value, reserved)
  }
  return "(" string ")"
}


objFlatten(ast)
{
  if !isobject(ast)
    return ast

  flat := object() ; flat object

  enum := ast._newenum()
  while enum[key, value]
  {
    if !isobject(value)
      flat._Insert(value)
    else
    {
      next := objFlatten(value)
      loop % next._MaxIndex()
      flat._Insert(next[A_Index])

    }
  }
  return flat
}

BaCon

BaCon has the concept of delimited strings, which may contain delimited strings within delimited strings etc. Such nested delimited strings must be surrounded by (escaped) double quotes in order to avoid their delimiter messing up operations on higher level delimited strings. However, from functional point of view, a delimited string is the same as a regular list. The special function FLATTEN$ can actually flatten out lists within lists. The last SORT$ in the program below makes sure no empty items remain in the list.

OPTION COLLAPSE TRUE

lst$ = "\"1\",2,\"\\\"3,4\\\",5\",\"\\\"\\\\\"\\\\\"\\\"\",\"\\\"\\\\\"6\\\\\"\\\"\",7,8,\"\""

PRINT lst$

REPEAT
    lst$ = FLATTEN$(lst$)
UNTIL AMOUNT(lst$, ",") = AMOUNT(FLATTEN$(lst$), ",")

PRINT SORT$(lst$, ",")

{{out}}

"1",2,"\"3,4\",5","\"\\"\\"\"","\"\\"6\\"\"",7,8,""
1,2,3,4,5,6,7,8

Bracmat

A list is automatically flattened during evaluation if the items are separated by either commas, plusses, asterisks or white spaces.

On top of that, lists separated with white space, plusses or asterisks have 'nil'-elements removed when evaluated. (nil-elements are empty strings, 0 and 1 respectively.)

On top of that, lists separated with plusses or asterisks have their elements sorted and, if possible, combined when evaluated.

A list that should not be flattened upon evaluation can be separated with dots.

( (myList = ((1), 2, ((3,4), 5), ((())), (((6))), 7, 8, ()))
& put$("Unevaluated:")
& lst$myList
& !myList:?myList          { the expression !myList evaluates myList }
& put$("Flattened:")
& lst$myList
)

Brat

array.prototype.flatten = {
  true? my.empty?
    { [] }
    { true? my.first.array?
      { my.first.flatten + my.rest.flatten }
      { [my.first] + my.rest.flatten }
    }
}

list = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]
p "List: #{list}"
p "Flattened: #{list.flatten}"

Burlesque

Usually flattening Blocks is done with the Concat command but it only removes one level of nesting therefore it is required to chain Concat calls until the Block does not contain Blocks anymore.

blsq ) {{1} 2 {{3 4} 5} {{{}}} {{{6}}} 7 8 {}}{\[}{)to{"Block"==}ay}w!
{1 2 3 4 5 6 7 8}

C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct list_t list_t, *list;
struct list_t{
	int is_list, ival; /* ival is either the integer value or list length */
	list *lst;
};

list new_list()
{
	list x = malloc(sizeof(list_t));
	x->ival = 0;
	x->is_list = 1;
	x->lst = 0;
	return x;
}

void append(list parent, list child)
{
	parent->lst = realloc(parent->lst, sizeof(list) * (parent->ival + 1));
	parent->lst[parent->ival++] = child;
}

list from_string(char *s, char **e, list parent)
{
	list ret = 0;
	if (!parent) parent = new_list();

	while (*s != '\0') {
		if (*s == ']') {
			if (e) *e = s + 1;
			return parent;
		}
		if (*s == '[') {
			ret = new_list();
			ret->is_list = 1;
			ret->ival = 0;
			append(parent, ret);
			from_string(s + 1, &s, ret);
			continue;
		}
		if (*s >= '0' && *s <= '9') {
			ret = new_list();
			ret->is_list = 0;
			ret->ival = strtol(s, &s, 10);
			append(parent, ret);
			continue;
		}
		s++;
	}

	if (e) *e = s;
	return parent;
}

void show_list(list l)
{
	int i;
	if (!l) return;
	if (!l->is_list) {
		printf("%d", l->ival);
		return;
	}

	printf("[");
	for (i = 0; i < l->ival; i++) {
		show_list(l->lst[i]);
		if (i < l->ival - 1) printf(", ");
	}
	printf("]");
}

list flatten(list from, list to)
{
	int i;
	list t;

	if (!to) to = new_list();
	if (!from->is_list) {
		t = new_list();
		*t = *from;
		append(to, t);
	} else
		for (i = 0; i < from->ival; i++)
			flatten(from->lst[i], to);
	return to;
}

void delete_list(list l)
{
	int i;
	if (!l) return;
	if (l->is_list && l->ival) {
		for (i = 0; i < l->ival; i++)
			delete_list(l->lst[i]);
		free(l->lst);
	}

	free(l);
}

int main()
{
	list l = from_string("[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []", 0, 0);

	printf("Nested: ");
	show_list(l);
	printf("\n");

	list flat = flatten(l, 0);
	printf("Flattened: ");
	show_list(flat);

	/* delete_list(l); delete_list(flat); */
	return 0;
}

{{out}}

Nested: [[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]
Flattened: [1, 2, 3, 4, 5, 6, 7, 8]

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));
      current = list.erase(current);
    }
    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";
}

{{out}}

[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]
[1, 2, 3, 4, 5, 6, 7, 8]

C#

{{works with|C sharp|C#|3+}}

Actual Workhorse code

using System;
using System.Collections;
using System.Linq;

namespace RosettaCodeTasks
{
	static class FlattenList
	{
		public static ArrayList Flatten(this ArrayList List)
		{
			ArrayList NewList = new ArrayList ( );

			NewList.AddRange ( List );

			while ( NewList.OfType<ArrayList> ( ).Count ( ) > 0 )
			{
				int index = NewList.IndexOf ( NewList.OfType<ArrayList> ( ).ElementAt ( 0 ) );
				ArrayList Temp = (ArrayList)NewList[index];
				NewList.RemoveAt ( index );
				NewList.InsertRange ( index, Temp );
			}

			return NewList;
		}
	}
}

Method showing population of arraylist and usage of flatten method

using System;
using System.Collections;

namespace RosettaCodeTasks
{
	class Program
	{
		static void Main ( string[ ] args )
		{

			ArrayList Parent = new ArrayList ( );
			Parent.Add ( new ArrayList ( ) );
			((ArrayList)Parent[0]).Add ( 1 );
			Parent.Add ( 2 );
			Parent.Add ( new ArrayList ( ) );
			( (ArrayList)Parent[2] ).Add ( new ArrayList ( ) );
			( (ArrayList)( (ArrayList)Parent[2] )[0] ).Add ( 3 );
			( (ArrayList)( (ArrayList)Parent[2] )[0] ).Add ( 4 );
			( (ArrayList)Parent[2] ).Add ( 5 );
			Parent.Add ( new ArrayList ( ) );
			( (ArrayList)Parent[3] ).Add ( new ArrayList ( ) );
			( (ArrayList)( (ArrayList)Parent[3] )[0] ).Add ( new ArrayList ( ) );
			Parent.Add ( new ArrayList ( ) );
			( (ArrayList)Parent[4] ).Add ( new ArrayList ( ) );
			( (ArrayList)( (ArrayList)Parent[4] )[0] ).Add ( new ArrayList ( ) );

			( (ArrayList)( (ArrayList)( (ArrayList)( (ArrayList)Parent[4] )[0] )[0] ) ).Add ( 6 );
			Parent.Add ( 7 );
			Parent.Add ( 8 );
			Parent.Add ( new ArrayList ( ) );


			foreach ( Object o in Parent.Flatten ( ) )
			{
				Console.WriteLine ( o.ToString ( ) );
			}
		}

	}
}

{{works with|C sharp|C#|4+}}

	public static class Ex {
		public static List<object> Flatten(this List<object> list) {

			var result = new List<object>();
			foreach (var item in list) {
				if (item is List<object>) {
					result.AddRange(Flatten(item as List<object>));
				} else {
					result.Add(item);
				}
			}
			return result;
		}
		public static string Join<T>(this List<T> list, string glue) {
			return string.Join(glue, list.Select(i => i.ToString()).ToArray());
		}
	}

	class Program {

		static void Main(string[] args) {
			var list = new List<object>{new List<object>{1}, 2, new List<object>{new List<object>{3,4}, 5}, new List<object>{new List<object>{new List<object>{}}}, new List<object>{new List<object>{new List<object>{6}}}, 7, 8, new List<object>{}};

			Console.WriteLine("[" + list.Flatten().Join(", ") + "]");
			Console.ReadLine();
		}
	}

Ceylon

shared void run() {
    "Lazily flatten nested streams"
    {Anything*} flatten({Anything*} stream)
        =>  stream.flatMap((element)
            =>  switch (element)
                case (is {Anything*}) flatten(element)
                else [element]);

    value list = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []];

    print(list);
    print(flatten(list).sequence());
}

{{out}}

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

(defn flatten [coll]
  (lazy-seq
    (when-let [s  (seq coll)]
      (if (coll? (first s))
        (concat (flatten (first s)) (flatten (rest s)))
        (cons (first s) (flatten (rest s)))))))

The built-in flatten is implemented as:

(defn flatten [x]
  (filter (complement sequential?)
          (rest (tree-seq sequential? seq x))))

CoffeeScript

flatten = (arr) ->
  arr.reduce ((xs, el) ->
    if Array.isArray el
      xs.concat flatten el
    else
      xs.concat [el]), []

# test
list = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]
console.log flatten list

Ouput:

coffee foo.coffee [ 1, 2, 3, 4, 5, 6, 7, 8 ]

## Common Lisp



```lisp
(defun flatten (structure)
  (cond ((null structure) nil)
        ((atom structure) (list structure))
        (t (mapcan #'flatten structure))))

or, from Paul Graham's OnLisp,

(defun flatten (ls)
  (labels ((mklist (x) (if (listp x) x (list x))))
    (mapcan #'(lambda (x) (if (atom x) (mklist x) (flatten x))) ls)))

Note that since, in Common Lisp, the empty list, boolean false and nil are the same thing, a tree of nil values cannot be flattened; they will disappear.

A third version that is recursive, imperative, and reasonably fast.

(defun flatten (obj)
  (let (result)
    (labels ((grep (obj)
               (cond ((null obj) nil)
                     ((atom obj) (push obj result))
                     (t (grep (rest obj))
                        (grep (first obj))))))
      (grep obj)
      result)))

The following version is tail recursive and functional.

(defun flatten (x &optional stack out)
  (cond ((consp x) (flatten (rest x) (cons (first x) stack) out))
        (x         (flatten (first stack) (rest stack) (cons x out)))
        (stack     (flatten (first stack) (rest stack) out))
        (t out)))

The next version is imperative, iterative and does not make use of a stack. It is faster than the versions given above.

(defun flatten (obj)
  (do* ((result (list obj))
        (node result))
       ((null node) (delete nil result))
    (cond ((consp (car node))
           (when (cdar node) (push (cdar node) (cdr node)))
           (setf (car node) (caar node)))
          (t (setf node (cdr node))))))

The above implementations of flatten give the same output on nested proper lists. {{Out}}

CL-USER> (flatten '((1) 2 ((3 4) 5) ((())) (((6))) 7 8 ()))
(1 2 3 4 5 6 7 8)

It should be noted that there are several choices that can be made when implementing flatten in Common Lisp:

-- should it work on dotted pairs?

-- should it work with non-nil atoms, presumably returning the atom or a copy of the atom?

-- when it comes to nil, should it be considered as an empty list and removed, or should it be considered as an atom and preserved?

So there are in fact several slightly different functions that correspond to flatten in common lisp. They may

-- collect all atoms, including nil,

-- collect all atoms in the car of the cons cells,

-- collect all atoms which are not in the cdr of a cell,

-- collect all non-nil atoms.

Which version is suitable for a given problem depends of course on the nature of the problem.

Crystal

[[1], 2, [[3, 4], 5], [[[] of Int32]], [[[6]]], 7, 8, [] of Int32].flatten()

[1, 2, 3, 4, 5, 6, 7, 8]

D

Instead of a Java-like class-based version, this version minimizes heap activity using a tagged union.

import std.stdio, std.algorithm, std.conv, std.range;

struct TreeList(T) {
    union { // A tagged union
        TreeList[] arr; // it's a node
        T data; // It's a leaf.
    }
    bool isArray = true; // = Contains an arr on default.

    static TreeList opCall(A...)(A items) pure nothrow {
        TreeList result;

        foreach (i, el; items)
            static if (is(A[i] == T)) {
                TreeList item;
                item.isArray = false;
                item.data = el;
                result.arr ~= item;
            } else
                result.arr ~= el;

        return result;
    }

    string toString() const pure {
        return isArray ? arr.text : data.text;
    }
}

T[] flatten(T)(in TreeList!T t) pure nothrow {
    if (t.isArray)
        return t.arr.map!flatten.join;
    else
        return [t.data];
}

void main() {
    alias TreeList!int L;
    static assert(L.sizeof == 12);
    auto l = L(L(1), 2, L(L(3,4), 5), L(L(L())), L(L(L(6))),7,8,L());
    l.writeln;
    l.flatten.writeln;
}

{{out}}

[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]
[1, 2, 3, 4, 5, 6, 7, 8]

With an Algebraic Data Type

A shorter and more cryptic version.

import std.stdio, std.variant, std.range, std.algorithm;

alias T = Algebraic!(int, This[]);

int[] flatten(T t) {
    return t.peek!int ? [t.get!int] : t.get!(T[])().map!flatten.join;
}

void main() {
    T([T([ T(1) ]),
       T(2),
       T([ T([ T(3), T(4) ]), T(5) ]),
       T([ T([ T( T[].init ) ]) ]),
       T([ T([ T([ T(6) ]) ]) ]),
       T(7),
       T(8),
       T( T[].init )
      ]).flatten.writeln;
}

{{out}} [1, 2, 3, 4, 5, 6, 7, 8]

=={{header|Déjà Vu}}==

(flatten):
	for i in copy:
		i
		if = :list type dup:
			(flatten)

flatten l:
	[ (flatten) l ]


!. flatten [ [ 1 ] 2 [ [ 3 4 ] 5 ] [ [ [] ] ] [ [ [ 6 ] ] ] 7 8 [] ]

{{out}}

[ 1 2 3 4 5 6 7 8 ]

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]

EchoLisp

The built-in '''(flatten list)''' is defined as follows:

(define (fflatten l)
(cond
[(null? l) null]
[(not (list? l)) (list l)]
[else (append (fflatten (first l)) (fflatten (rest l)))]))

;;
(define L' [[1] 2 [[3 4] 5] [[[]]] [[[6]]] 7 8 []])

(fflatten L) ;; use custom function
 → (1 2 3 4 5 6 7 8)
(flatten L) ;; use built-in
 → (1 2 3 4 5 6 7 8)

;; Remarks
;; null is the same as () - the empty list -
(flatten '(null null null))
   → null
(flatten '[ () () () ])
  → null
(flatten null)
❗ error: flatten : expected list : null

;; The 'reverse' of flatten is group
(group '( 4 5 5 5 6 6 7 8 7 7 7 9))
    → ((4) (5 5 5) (6 6) (7) (8) (7 7 7) (9))

Ela

This implementation can flattern any given list:

xs =  [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]

flat = flat' []
       where flat' n [] = n
             flat' n (x::xs)
               | x is List = flat' (flat' n xs) x
               | else = x :: flat' n xs

flat xs

{{out}}

[1,2,3,4,5,6,7,8]

An alternative solution:

flat [] = []
flat (x::xs)
  | x is List = flat x ++ flat xs
  | else = x :: flat xs

Elixir

defmodule RC do
  def flatten([]), do: []
  def flatten([h|t]), do: flatten(h) ++ flatten(t)
  def flatten(h), do: [h]
end

list = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]

# Our own implementation
IO.inspect RC.flatten(list)
# Library function
IO.inspect List.flatten(list)

{{out}}

[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]

Elm

import Graphics.Element exposing (show)

type Tree a
  = Leaf a
  | Node (List (Tree a))

flatten : Tree a -> List a
flatten tree =
  case tree of
    Leaf a -> [a]
    Node list -> List.concatMap flatten list

-- [[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]
tree : Tree Int
tree = 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 []
  ]

main =
  show (flatten tree)

Emacs Lisp

(defun flatten (mylist)
  (cond
   ((null mylist) nil)
   ((atom mylist) (list mylist))
   (t
    (append (flatten (car mylist)) (flatten (cdr mylist))))))

Erlang

There's a standard function (lists:flatten/1) 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].

Euphoria

{{works with|Euphoria|4.0.0}}

sequence a = {{1}, 2, {{3, 4}, 5}, {{{}}}, {{{6}}}, 7, 8, {}}

function flatten( object s )
	sequence res = {}
	if sequence( s ) then
		for i = 1 to length( s ) do
			sequence c = flatten( s[ i ] )
			if length( c ) > 0 then
				res &= c
			end if
		end for
	else
		if length( s ) > 0 then
			res = { s }
		end if
	end if
	return res
end function

? a
? flatten(a)

{{out}}

{
  {1},
  2,
  {
    {3,4},
    5
  },
  {
    {{}}
  },
  {
    {
      {6}
    }
  },
  7,
  8,
  {}
}
{1,2,3,4,5,6,7,8}

=={{header|F_Sharp|F#}}== As with Haskell and OCaml we have to define our list as an algebraic data type, to be strongly typed:

type 'a ll =
    | I of 'a             // leaf Item
    | L of 'a ll list     // ' <- confine the syntax colouring confusion

let rec flatten = function
    | [] -> []
    | (I x)::y -> x :: (flatten y)
    | (L x)::y -> List.append (flatten x) (flatten y)

printfn "%A" (flatten [L([I(1)]); I(2); L([L([I(3);I(4)]); I(5)]); L([L([L([])])]); L([L([L([I(6)])])]); I(7); I(8); L([])])

// -> [1; 2; 3; 4; 5; 6; 7; 8]

An alternative approach with List.collect and the same data type. Note that flatten operates on all deepLists (ll) and atoms (I) are "flatened" to lists.

let rec flatten =
    function
    | I x -> [x]
    | L x -> List.collect flatten x

printfn "%A" (flatten (L [L([I(1)]); I(2); L([L([I(3);I(4)]); I(5)]); L([L([L([])])]); L([L([L([I(6)])])]); I(7); I(8); L([])]))

// -> [1; 2; 3; 4; 5; 6; 7; 8]

Factor

USE: sequences.deep
( scratchpad ) { { 1 } 2 { { 3 4 } 5 } { { { } } } { { { 6 } } } 7 8 { } } flatten .
{ 1 2 3 4 5 6 7 8 }

Fantom

class Main
{
  // uses recursion to flatten a list
  static List myflatten (List items)
  {
    List result := [,]
    items.each |item|
    {
      if (item is List)
        result.addAll (myflatten(item))
      else
        result.add (item)
    }
    return result
  }

  public static Void main ()
  {
    List sample := [[1], 2, [[3,4], 5], [[[,]]], [[[6]]], 7, 8, [,]]
    // there is a built-in flatten method for lists
    echo ("Flattened list 1: " + sample.flatten)
    // or use the function 'myflatten'
    echo ("Flattened list 2: " + myflatten (sample))
  }
}

Forth

{{works with|Forth}} Works with any ANS Forth. Needs the FMS-SI (single inheritance) library code located here: http://soton.mpeforth.com/flag/fms/index.html

include FMS-SI.f
include FMS-SILib.f

: flatten {: list1 list2 --  :}
  list1 size: 0 ?do i list1 at:
                  dup is-a object-list2
                  if list2 recurse else list2 add: then  loop ;

object-list2 list
o{ o{ 1 } 2 o{ o{ 3 4 } 5 } o{ o{ o{ } } } o{ o{ o{ 6 } } } 7 8 o{ } }
list flatten
list p: \ o{ 1 2 3 4 5 6 7 8 } ok

Fortran

! input   : [[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]
! flatten : [1, 2, 3, 4, 5, 6, 7, 8 ]

module flat
  implicit none

  type n
     integer                             :: a
     type(n), dimension(:), pointer      :: p => null()
     logical                             :: empty = .false.
  end type

contains

  recursive subroutine del(this)
  type(n), intent(inout) :: this
  integer                :: i
  if (associated(this%p)) then
    do i = 1, size(this%p)
       call del(this%p(i))
    end do
  end if
  end subroutine

  function join(xs) result (r)
  type(n), dimension(:), target :: xs
  type(n)                       :: r
  integer                       :: i
  if (size(xs)>0) then
    allocate(r%p(size(xs)), source=xs)
    do i = 1, size(xs)
      r%p(i) = xs(i)
    end do
  else
    r%empty = .true.
  end if
  end function

  recursive subroutine flatten1(x,r)
  integer, dimension (:), allocatable, intent(inout) :: r
  type(n), intent(in)                                :: x
  integer, dimension (:), allocatable                :: tmp
  integer                                            :: i
  if (associated(x%p)) then
    do i = 1, size(x%p)
      call flatten1(x%p(i), r)
    end do
  elseif (.not. x%empty) then
    allocate(tmp(size(r)+1))
    tmp(1:size(r)) = r
    tmp(size(r)+1) = x%a
    call move_alloc(tmp, r)
  end if
  end subroutine

  function flatten(x) result (r)
  type(n), intent(in)                                :: x
  integer, dimension(:), allocatable                 :: r
  allocate(r(0))
  call flatten1(x,r)
  end function

  recursive subroutine show(x)
  type(n)   :: x
  integer   :: i
  if (x%empty) then
    write (*, "(a)", advance="no") "[]"
  elseif (associated(x%p)) then
    write (*, "(a)", advance="no") "["
    do i = 1, size(x%p)
      call show(x%p(i))
      if (i<size(x%p)) then
        write (*, "(a)", advance="no") ", "
      end if
    end do
    write (*, "(a)", advance="no") "]"
  else
    write (*, "(g0)", advance="no") x%a
  end if
  end subroutine

  function fromString(line) result (r)
  character(len=*)                      :: line
  type (n)                              :: r
  type (n), dimension(:), allocatable   :: buffer, buffer1
  integer, dimension(:), allocatable    :: stack, stack1
  integer                               :: sp,i0,i,j, a, cur, start
  character                             :: c

  if (.not. allocated(buffer)) then
    allocate (buffer(5)) ! will be re-allocated if more is needed
  end if
  if (.not. allocated(stack)) then
    allocate (stack(5))
  end if

  sp = 1; cur = 1; i = 1
  do
    if ( i > len_trim(line) ) exit
    c = line(i:i)
    if (c=="[") then
      if (sp>size(stack)) then
        allocate(stack1(2*size(stack)))
        stack1(1:size(stack)) = stack
        call move_alloc(stack1, stack)
      end if
      stack(sp) = cur;  sp = sp + 1; i = i+1
    elseif (c=="]") then
      sp = sp - 1; start = stack(sp)
      r = join(buffer(start:cur-1))
      do j = start, cur-1
        call del(buffer(j))
      end do
      buffer(start) = r; cur = start+1; i = i+1
    elseif (index(" ,",c)>0) then
      i = i + 1; continue
    elseif (index("-123456789",c)>0) then
      i0 = i
      do
        if ((i>len_trim(line)).or. &
            index("1234567890",line(i:i))==0) then
          read(line(i0:i-1),*) a
          if (cur>size(buffer)) then
            allocate(buffer1(2*size(buffer)))
            buffer1(1:size(buffer)) = buffer
            call move_alloc(buffer1, buffer)
          end if
          buffer(cur) = n(a); cur = cur + 1; exit
        else
          i = i+1
        end if
      end do
    else
       stop "input corrupted"
    end if
  end do
  end function
end module

program main
  use flat
  type (n)  :: x
  x = fromString("[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]")
  write(*, "(a)", advance="no") "input   : "
  call show(x)
  print *
  write (*,"(a)", advance="no") "flatten : ["
  write (*, "(*(i0,:,:', '))", advance="no") flatten(x)
  print *, "]"
end program

===Or, older style=== Fortran does not offer strings, only CHARACTER variables of some fixed size. Functions can return such types, but, must specify a fixed size. Or, mess about with run-time allocation as above. Since in principle a list is arbitrarily long, the plan here is to crush its content in place, and thereby never have to worry about long-enough work areas. This works because the transformations in mind never replace something by something longer. A subroutine can receive an arbitrary-sized CHARACTER variable, and can change it. No attempt is made to detect improper lists.

      SUBROUTINE CRUSH(LIST)	!Changes LIST.
Crushes a list holding multi-level entries within [...] to a list of single-level entries. Null entries are purged.
Could escalate to recognising quoted strings as list entries (preserving spaces), not just strings of digits.
       CHARACTER*(*) LIST	!The text manifesting the list.
       INTEGER I,L		!Fingers.
       LOGICAL LIVE		!Scan state.
        L = 1		!Output finger. The starting [ is already in place.
        LIVE = .FALSE.	!A list element is not in progress.
        DO I = 2,LEN(LIST)	!Scan the characters of the list.
          SELECT CASE(LIST(I:I))	!Consider one.
           CASE("[","]",","," ")	!Punctuation or spacing?
            IF (LIVE) THEN		!Yes. If previously in an element,
              L = L + 1			!Advance the finger,
              LIST(L:L) = ","		!And place its terminating comma.
              LIVE = .FALSE.		!Thus the element is finished.
            END IF		!So much for punctuation and empty space.
           CASE DEFAULT		!Everything else is an element's content.
            LIVE = .TRUE.		!So we're in an element.
            L = L + 1			!Advance the finger.
            LIST(L:L) = LIST(I:I)	!And copy the content's character.
          END SELECT		!Either we're in an element, or, we're not.
        END DO			!On to the next character.
Completed the crush. At least one ] must have followed the last character of the last element.
        LIST(L:L) = "]"		!It had provoked a trailing comma. Now it is the ending ].
        LIST(L + 1:) = ""	!Scrub any tail end, just to be neat.
      END		!Trailing spaces are the caller's problem.

      CHARACTER*88 STUFF	!Work area.
      STUFF = "[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]"	!The example.
      WRITE (6,*) "Original: ",STUFF
      CALL CRUSH(STUFF)		!Can't be a constant, as it will be changed.
      WRITE (6,*) " Crushed: ",STUFF	!Behold!
      END

Output is Original: [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] Crushed: [1,2,3,4,5,6,7,8] Note that if you insist on the rather flabby style of having spaces after commas, then there would be trouble. Instead of placing just a comma, a ", " would be required, which is ''two'' symbols going out when ''one'' symbol has come in: overwriting yet-to-be-scanned input is a bad idea. Either a more complex set of scan states would be required to squeeze in the extra or a separate work area would be needed to hold such output and the issue of "long enough" would arise.

All of this relies on the list being presented as a flat text, which text is then manipulated directly. If the list was manifested in a data structure of some kind with links and suchlike, then tree-traversal of that structure would be needed to reach the leaf entries.

Frink

a = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]
println[flatten[a]]

Gambas

'''[https://gambas-playground.proko.eu/?gist=1c0157ce2b7eab99ba4e784e183ba474 Click this link to run this code]'''

'Code 'borrowed' from Run BASIC

Public Sub Main()
Dim sComma, sString, sFlatter As String
Dim siCount As Short

sString = "[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8 []]"
For siCount = 1 To Len(sString)
 If InStr("[] ,", Mid$(sString, siCount, 1)) = 0 Then
  sFlatter = sFlatter & sComma & Mid(sString, siCount, 1)
  sComma = ","
 End If
Next
Print "["; sFlatter; "]"

End

Output:

[1,2,3,4,5,6,7,8]

GAP

Flat([[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]);

Go

package main

import "fmt"

func list(s ...interface{}) []interface{} {
    return s
}

func main() {
    s := list(list(1),
        2,
        list(list(3, 4), 5),
        list(list(list())),
        list(list(list(6))),
        7,
        8,
        list(),
    )
    fmt.Println(s)
    fmt.Println(flatten(s))
}

func flatten(s []interface{}) (r []int) {
    for _, e := range s {
        switch i := e.(type) {
        case int:
            r = append(r, i)
        case []interface{}:
            r = append(r, flatten(i)...)
        }
    }
    return
}

{{out}}

[[1] 2 [[3 4] 5] [[[]]] [[[6]]] 7 8 []]
[1 2 3 4 5 6 7 8]

In the code above, flatten uses an easy-to-read type switch to extract ints and return an int slice. The version below is generalized to return a flattened slice of interface{} type, which can of course refer to objects of any type, and not just int. Also, just to show a variation in programming style, a type assertion is used rather than a type switch.

func flatten(s []interface{}) (r []interface{}) {
    for _, e := range s {
        if i, ok := e.([]interface{}); ok {
            r = append(r, flatten(i)...)
        } else {
            r = append(r, e)
        }
    }
    return
}

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]

Haskell

In Haskell we have to interpret this structure as an algebraic data type.

import Data.Tree (Tree(..), flatten)

-- [[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 :: Tree [a] -> [a]
flattenList = concat . flatten

main :: IO ()
main = print $ flattenList list

{{Out}}

[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) = xs >>= flatten

main :: IO ()
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 []
    ]

-- [1,2,3,4,5,6,7,8]

Yet another choice, custom data structure, efficient lazy flattening:

(This is unnecessary; since Haskell is lazy, the previous solution will only do just as much work as necessary for each element that is requested from the resulting list.)

data NestedList a
  = NList [NestedList a]
  | Entry a

flatten :: NestedList a -> [a]
flatten nl = flatten_ nl []
  where
    flatten_ :: NestedList a -> [a] -> [a]
    flatten_ (Entry a) cont = a : cont
    flatten_ (NList entries) cont = foldr flatten_ cont entries

-- By passing through a list to which the results will be prepended,
-- we allow for efficient lazy evaluation
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]

Hy

(defn flatten [lst]
  (sum (genexpr (if (isinstance x list)
                    (flatten x)
                    [x])
                [x lst])
       []))

(print (flatten [[1] 2 [[3 4] 5] [[[]]] [[[6]]] 7 8 []]))
; [1, 2, 3, 4, 5, 6, 7, 8]

=={{header|Icon}} and {{header|Unicon}}== The following procedure solves the task using a string representation of nested lists and cares not if the list is well formed or not.

link strings           # for compress,deletec,pretrim

procedure sflatten(s)  # uninteresting string solution
return pretrim(trim(compress(deletec(s,'[ ]'),',') ,','),',')
end

{{libheader|Icon Programming Library}} The solution uses several procedures from [http://www.cs.arizona.edu/icon/library/src/procs/strings.icn strings in the IPL]

This procedure is more in the spirit of the task handling actual lists rather than representations. It uses a recursive approach using some of the built-in list manipulation functions and operators.

procedure flatten(L)   # in the spirt of the problem  a structure
local l,x

l := []
every x := !L do
   if type(x) == "list" then l |||:= flatten(x)
   else put(l,x)
return l
end

Finally a demo routine to drive these and a helper to show how it works.

procedure main()
write(sflatten(" [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]"))
writelist(flatten( [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]))
end

procedure writelist(L)
writes("[")
every writes(" ",image(!L))
write(" ]")
return
end

Ioke

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

J

'''Solution''':

'''Example''':

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

'''Notes:''' The primitive ; removes one level of nesting.

<S:0 takes an arbitrarily nested list and puts everything one level deep.

[: is glue, here.

We do not use ; by itself because it requires that all of the contents be the same type and nested items have a different type from unnested items.

We do not use ]S:0 (which puts everything zero levels deep) because it assembles its results as items of a list, which means that short items will be padded to be equal to the largest items, and that is not what we would want here (we do not want the empty item to be padded with a fill element).

'''Alternative Solution:'''

The previous solution can be generalized to flatten the nesting and shape for a list of arbitrary values that include arrays of any rank:

flatten2 =: [: ; <@,S:0

'''Example:'''

   ]li2 =.  (<1) ; 2; ((<3;4); 5 + i.3 4) ; ((<a:)) ; ((<(<17))) ; 18; 19; <a:
+---+-+---------------------+----+------+--+--+--+
|+-+|2|+-------+-----------+|+--+|+----+|18|19|++|
||1|| ||+-----+| 5  6  7  8|||++|||+--+||  |  ||||
|+-+| |||+-+-+|| 9 10 11 12|||||||||17|||  |  |++|
|   | ||||3|4|||13 14 15 16|||++|||+--+||  |  |  |
|   | |||+-+-+||           ||+--+|+----+|  |  |  |
|   | ||+-----+|           ||    |      |  |  |  |
|   | |+-------+-----------+|    |      |  |  |  |
+---+-+---------------------+----+------+--+--+--+

   flatten2 li
1 2 3 4 5 6 7 8
   flatten2 li2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Here, we have replaced <S:0 with <@,S:0 so our leaves are flattened before the final step where their boxes are razed.

Java

{{works with|Java|1.5+}}

The flatten method was overloaded for better separation of concerns. On the first one you can pass any List and get it flat into a LinkedList implementation. On the other one you can pass any List implementation you like for both lists.

Note that both implementations can only put the result into type List