Flatten a list: Difference between revisions
PascalABC.NET |
|||
(451 intermediate revisions by more than 100 users not shown) | |||
Line 1: | Line 1: | ||
{{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: |
|||
;Task: |
|||
[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] |
|||
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: |
Where the correct result would be the list: |
||
[1, 2, 3, 4, 5, 6, 7, 8] |
[1, 2, 3, 4, 5, 6, 7, 8] |
||
;Related task: |
|||
C.f. [[Tree traversal]] |
|||
* [[Tree traversal]] |
|||
<br><br> |
|||
=={{header|8th}}== |
|||
<syntaxhighlight lang="forth"> |
|||
\ 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 |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
[[1],2,[[3,4],5],[[[]]],[[[6]]],7,8,[]]<br> |
|||
[1,2,3,4,5,6,7,8] |
|||
=={{header|ACL2}}== |
|||
<syntaxhighlight lang="lisp">(defun flatten (tr) |
|||
(cond ((null tr) nil) |
|||
((atom tr) (list tr)) |
|||
(t (append (flatten (first tr)) |
|||
(flatten (rest tr))))))</syntaxhighlight> |
|||
=={{header|ActionScript}}== |
|||
<syntaxhighlight lang="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; |
|||
} |
|||
</syntaxhighlight> |
|||
=={{header|Ada}}== |
|||
nestable_lists.ads: |
|||
<syntaxhighlight lang="ada">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;</syntaxhighlight> |
|||
nestable_lists.adb: |
|||
<syntaxhighlight lang="ada">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;</syntaxhighlight> |
|||
example usage: |
|||
<syntaxhighlight lang="ada">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;</syntaxhighlight> |
|||
Output: |
|||
<pre>[[ 1], 2, [[ 3, 4], 5], [[[]]], [[[ 6]]], 7, 8, []] |
|||
[ 1, 2, 3, 4, 5, 6, 7, 8]</pre> |
|||
=={{header|Aikido}}== |
|||
<syntaxhighlight lang="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("]") |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[1, 2, 3, 4, 5, 6, 7, 8] |
|||
</pre> |
|||
=={{header|Aime}}== |
|||
<syntaxhighlight lang="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; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] |
|||
[1, 2, 3, 4, 5, 6, 7, 8] |
|||
</pre> |
|||
=={{header|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. |
|||
<syntaxhighlight lang="algol68">main:( |
|||
[][][]INT list = ((1), 2, ((3,4), 5), ((())), (((6))), 7, 8, ()); |
|||
print((list, new line)) |
|||
)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
+1 +2 +3 +4 +5 +6 +7 +8 |
|||
</pre> |
|||
=={{header|APL}}== |
|||
=== Dyalog APL === |
|||
Flatten is a primitive in APL, named enlist |
|||
<syntaxhighlight lang="apl">∊</syntaxhighlight> |
|||
{{out}} |
|||
<pre> ∊((1) 2 ((3 4) 5) (((⍬))) (((6))) 7 8 (⍬)) |
|||
1 2 3 4 5 6 7 8</pre> |
|||
=={{header|AppleScript}}== |
|||
<syntaxhighlight lang="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 |
|||
</syntaxhighlight> |
|||
Or, to make more productive use of the language (where "efficiency" is a function of the scripter's time, rather than the machine's) we can express this in terms of a generic '''concatMap''': |
|||
{{trans|JavaScript}} |
|||
<syntaxhighlight lang="applescript">-- 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</syntaxhighlight> |
|||
{{Out}} |
|||
<syntaxhighlight lang="applescript">{1, 2, 3, 4, 5, 6, 7, 8}</syntaxhighlight> |
|||
It can be more efficient to build just one list by appending items to it than to proliferate lists using concatenation: |
|||
<syntaxhighlight lang="applescript">on flatten(theList) |
|||
script o |
|||
property flatList : {} |
|||
-- Recursive handler dealing with the current (sub)list. |
|||
on flttn(thisList) |
|||
script p |
|||
property l : thisList |
|||
end script |
|||
repeat with i from 1 to (count thisList) |
|||
set thisItem to item i of p's l |
|||
if (thisItem's class is list) then |
|||
flttn(thisItem) |
|||
else |
|||
set end of my flatList to thisItem |
|||
end if |
|||
end repeat |
|||
end flttn |
|||
end script |
|||
if (theList's class is not list) then return theList |
|||
o's flttn(theList) |
|||
return o's flatList |
|||
end flatten</syntaxhighlight> |
|||
=={{header|Arturo}}== |
|||
<syntaxhighlight lang="rebol">print flatten [[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>1 2 3 4 5 6 7 8</pre> |
|||
=={{header|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. |
|||
<syntaxhighlight lang="autohotkey">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 |
|||
}</syntaxhighlight> |
|||
=={{header|BASIC}}== |
|||
==={{header|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. |
|||
<syntaxhighlight lang="qbasic">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$, ",")</syntaxhighlight> |
|||
{{out}} |
|||
<pre>"1",2,"\"3,4\",5","\"\\"\\"\"","\"\\"6\\"\"",7,8,"" |
|||
1,2,3,4,5,6,7,8</pre> |
|||
==={{header|BASIC256}}=== |
|||
{{trans|FreeBASIC}} |
|||
<syntaxhighlight lang="basic256">sComma = "": sFlatter = "" |
|||
sString = "[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8 []]" |
|||
For siCount = 1 To Length(sString) |
|||
If Instr("[] ,", Mid(sString, siCount, 1)) = 0 Then |
|||
sFlatter = sFlatter & sComma & Mid(sString, siCount, 1) |
|||
sComma = ", " |
|||
End If |
|||
Next siCount |
|||
Print "["; sFlatter; "]" |
|||
End</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Igual que la entrada de FreeBASIC.</pre> |
|||
==={{header|Chipmunk Basic}}=== |
|||
{{works with|Chipmunk Basic|3.6.4}} |
|||
{{works with|QBasic}} |
|||
<syntaxhighlight lang="qbasic">10 cls |
|||
20 sstring$ = "[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8 []]" |
|||
30 for sicount = 1 to len(sstring$) |
|||
40 if instr("[] ,",mid$(sstring$,sicount,1)) = 0 then |
|||
50 sflatter$ = sflatter$+scomma$+mid$(sstring$,sicount,1) |
|||
60 scomma$ = ", " |
|||
70 endif |
|||
80 next sicount |
|||
90 print "[";sflatter$;"]" |
|||
100 end</syntaxhighlight> |
|||
==={{header|FreeBASIC}}=== |
|||
{{trans|Gambas}} |
|||
<syntaxhighlight lang="freebasic">Dim As String sComma, sString, sFlatter |
|||
Dim As Short siCount |
|||
sString = "[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8 []]" |
|||
For siCount = 1 To Len(sString) |
|||
If Instr("[] ,", Mid(sString, siCount, 1)) = 0 Then |
|||
sFlatter += sComma + Mid(sString, siCount, 1) |
|||
sComma = ", " |
|||
End If |
|||
Next siCount |
|||
Print "["; sFlatter; "]" |
|||
Sleep</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[1, 2, 3, 4, 5, 6, 7, 8]</pre> |
|||
==={{header|Gambas}}=== |
|||
'''[https://gambas-playground.proko.eu/?gist=1c0157ce2b7eab99ba4e784e183ba474 Click this link to run this code]''' |
|||
<syntaxhighlight lang="gambas">'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</syntaxhighlight> |
|||
Output: |
|||
<pre>[1,2,3,4,5,6,7,8]</pre> |
|||
==={{header|GW-BASIC}}=== |
|||
{{works with|Chipmunk Basic}} |
|||
{{works with|QBasic}} |
|||
<syntaxhighlight lang="qbasic">10 CLS |
|||
20 SSTRING$ = "[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8 []]" |
|||
30 FOR SICOUNT = 1 TO LEN(SSTRING$) |
|||
40 IF INSTR("[] ,",MID$(SSTRING$,SICOUNT,1)) = 0 THEN SFLATTER$ = SFLATTER$+SCOMMA$+MID$(SSTRING$,SICOUNT,1): SCOMMA$ = ", " |
|||
50 NEXT SICOUNT |
|||
60 PRINT "[";SFLATTER$;"]" |
|||
70 END</syntaxhighlight> |
|||
==={{header|MSX Basic}}=== |
|||
{{works with|QBasic}} |
|||
{{works with|Chipmunk Basic}} |
|||
{{works with|GW-BASIC}} |
|||
<syntaxhighlight lang="qbasic">10 CLS |
|||
20 S$ = "[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8 []]" |
|||
30 FOR SICOUNT = 1 TO LEN(S$) |
|||
40 IF INSTR("[] ,",MID$(S$,SICOUNT,1)) = 0 THEN SFLATTER$ = SFLATTER$+SCOMMA$+MID$(S$,SICOUNT,1): SCOMMA$ = ", " |
|||
50 NEXT SICOUNT |
|||
60 PRINT "[";SFLATTER$;"]" |
|||
70 END</syntaxhighlight> |
|||
==={{header|PureBasic}}=== |
|||
<syntaxhighlight lang="purebasic">Structure RCList |
|||
Value.i |
|||
List A.RCList() |
|||
EndStructure |
|||
Procedure Flatten(List A.RCList()) |
|||
ResetList(A()) |
|||
While NextElement(A()) |
|||
With A() |
|||
If \Value |
|||
Continue |
|||
Else |
|||
ResetList(\A()) |
|||
While NextElement(\A()) |
|||
If \A()\Value: A()\Value=\A()\Value: EndIf |
|||
Wend |
|||
EndIf |
|||
While ListSize(\A()): DeleteElement(\A()): Wend |
|||
If Not \Value: DeleteElement(A()): EndIf |
|||
EndWith |
|||
Wend |
|||
EndProcedure</syntaxhighlight> |
|||
Set up the MD-List & test the Flattening procedure. |
|||
<syntaxhighlight lang="purebasic">;- Set up two lists, one multi dimensional and one 1-D. |
|||
NewList A.RCList() |
|||
;- Create a deep list |
|||
With A() |
|||
AddElement(A()): AddElement(\A()): AddElement(\A()): \A()\Value=1 |
|||
AddElement(A()): A()\Value=2 |
|||
AddElement(A()): AddElement(\A()): \A()\Value=3 |
|||
AddElement(\A()): \A()\Value=4 |
|||
AddElement(A()): AddElement(\A()): \A()\Value=5 |
|||
AddElement(A()): AddElement(\A()): AddElement(\A()): AddElement(\A()) |
|||
AddElement(A()): AddElement(\A()): AddElement(\A()): \A()\Value=6 |
|||
AddElement(A()): A()\Value=7 |
|||
AddElement(A()): A()\Value=8 |
|||
AddElement(A()): AddElement(\A()): AddElement(\A()) |
|||
EndWith |
|||
Flatten(A()) |
|||
;- Present the result |
|||
If OpenConsole() |
|||
Print("Flatten: [") |
|||
ForEach A() |
|||
Print(Str(A()\Value)) |
|||
If ListIndex(A())<(ListSize(A())-1) |
|||
Print(", ") |
|||
Else |
|||
PrintN("]") |
|||
EndIf |
|||
Next |
|||
Print(#CRLF$+"Press ENTER to quit"): Input() |
|||
EndIf</syntaxhighlight><pre>Flatten: [1, 2, 4, 5, 6, 7, 8]</pre> |
|||
==={{header|QBasic}}=== |
|||
{{works with|QBasic|1.1}} |
|||
{{works with|QuickBasic|4.5}} |
|||
<syntaxhighlight lang="qbasic">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 siCount |
|||
PRINT "["; sFlatter$; "]" |
|||
END</syntaxhighlight> |
|||
==={{header|Run BASIC}}=== |
|||
{{incorrect|Run BASIC| The task is not in string translation but in list translation.}} |
|||
<syntaxhighlight lang="runbasic">n$ = "[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8 []]" |
|||
for i = 1 to len(n$) |
|||
if instr("[] ,",mid$(n$,i,1)) = 0 then |
|||
flatten$ = flatten$ + c$ + mid$(n$,i,1) |
|||
c$ = "," |
|||
end if |
|||
next i |
|||
print "[";flatten$;"]"</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[1,2,3,4,5,6,7,8]</pre> |
|||
==={{header|TI-89 BASIC}}=== |
|||
There is no nesting of lists or other data structures in TI-89 BASIC, short of using variable names as pointers. |
|||
==={{header|True BASIC}}=== |
|||
<syntaxhighlight lang="qbasic">LET sstring$ = "[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8 []]" |
|||
FOR sicount = 1 TO LEN(sstring$) |
|||
IF pos("[] ,",(sstring$)[sicount:sicount+1-1]) = 0 THEN |
|||
LET sflatter$ = sflatter$ & scomma$ & (sstring$)[sicount:sicount+1-1] |
|||
LET scomma$ = ", " |
|||
END IF |
|||
NEXT sicount |
|||
PRINT "["; sflatter$; "]" |
|||
END</syntaxhighlight> |
|||
==={{header|XBasic}}=== |
|||
{{works with|Windows XBasic}} |
|||
<syntaxhighlight lang="xbasic">PROGRAM "Flatten a list" |
|||
DECLARE FUNCTION Entry () |
|||
FUNCTION Entry () |
|||
n$ = "[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8 []]" |
|||
FOR i = 1 TO LEN(n$) |
|||
IF INSTR("[] ,",MID$(n$,i,1)) = 0 THEN |
|||
flatten$ = flatten$ + c$ + MID$(n$,i,1) |
|||
c$ = ", " |
|||
END IF |
|||
NEXT i |
|||
PRINT "[";flatten$;"]" |
|||
END FUNCTION |
|||
END PROGRAM</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[1, 2, 3, 4, 5, 6, 7, 8]</pre> |
|||
==={{header|Yabasic}}=== |
|||
{{trans|FreeBASIC}} |
|||
<syntaxhighlight lang="yabasic">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 siCount |
|||
Print "[", sFlatter$, "]" |
|||
End</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Igual que la entrada de FreeBASIC.</pre> |
|||
==={{header|ZX Spectrum Basic}}=== |
|||
{{incorrect|ZX Spectrum Basic| The task is not in string translation but in list translation.}} |
|||
<syntaxhighlight lang="zxbasic">10 LET f$="[" |
|||
20 LET n$="[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8 []]" |
|||
30 FOR i=2 TO (LEN n$)-1 |
|||
40 IF n$(i)>"/" AND n$(i)<":" THEN LET f$=f$+n$(i): GO TO 60 |
|||
50 IF n$(i)="," AND f$(LEN f$)<>"," THEN LET f$=f$+"," |
|||
60 NEXT i |
|||
70 LET f$=f$+"]": PRINT f$</syntaxhighlight> |
|||
=={{header|BQN}}== |
|||
<syntaxhighlight lang="bqn">Enlist ← {(∾𝕊¨)⍟(1<≡)⥊𝕩}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Enlist ⟨⟨1⟩, 2, ⟨⟨3, 4⟩, 5⟩, ⟨⟨⟨⟩⟩⟩, ⟨⟨⟨6⟩⟩⟩, 7, 8, ⟨⟩⟩ |
|||
⟨ 1 2 3 4 5 6 7 8 ⟩ |
|||
</pre> |
|||
=={{header|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. |
|||
<syntaxhighlight lang="bracmat"> |
|||
( (myList = ((1), 2, ((3,4), 5), ((())), (((6))), 7, 8, ())) |
|||
& put$("Unevaluated:") |
|||
& lst$myList |
|||
& !myList:?myList { the expression !myList evaluates myList } |
|||
& put$("Flattened:") |
|||
& lst$myList |
|||
) |
|||
</syntaxhighlight> |
|||
=={{header|Brat}}== |
|||
<syntaxhighlight lang="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}"</syntaxhighlight> |
|||
=={{header|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. |
|||
<syntaxhighlight lang="burlesque"> |
|||
blsq ) {{1} 2 {{3 4} 5} {{{}}} {{{6}}} 7 8 {}}{\[}{)to{"Block"==}ay}w! |
|||
{1 2 3 4 5 6 7 8} |
|||
</syntaxhighlight> |
|||
=={{header|C}}== |
|||
<syntaxhighlight lang="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; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Nested: [[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] |
|||
Flattened: [1, 2, 3, 4, 5, 6, 7, 8]</pre> |
|||
=={{header|C sharp|C#}}== |
|||
{{works with|C sharp|C#|3+}} |
|||
Actual Workhorse code |
|||
<syntaxhighlight lang="csharp"> |
|||
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; |
|||
} |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
Method showing population of arraylist and usage of flatten method |
|||
<syntaxhighlight lang="csharp"> |
|||
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 ( ) ); |
|||
} |
|||
} |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
{{works with|C sharp|C#|4+}} |
|||
<syntaxhighlight lang="csharp"> |
|||
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(); |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
=={{header|C++}}== |
=={{header|C++}}== |
||
< |
<syntaxhighlight lang="cpp">#include <list> |
||
#include <boost/any.hpp> |
#include <boost/any.hpp> |
||
Line 25: | Line 1,050: | ||
++next; |
++next; |
||
list.splice(next, boost::any_cast<anylist&>(*current)); |
list.splice(next, boost::any_cast<anylist&>(*current)); |
||
current = list.erase(current); |
|||
++next; |
|||
list.erase(current); |
|||
current = next; |
|||
} |
} |
||
else |
else |
||
++current; |
++current; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
Use example: |
Use example: |
||
Since C++ currently doesn't have nice syntax for initializing lists, |
Since C++ currently doesn't have nice syntax for initializing lists, |
||
this includes a simple parser to create lists of integers and sublists. |
|||
<lang cpp>#include <cctype> |
|||
Also, there's no standard way to output this type of list, |
|||
so some output code is added as well. |
|||
<syntaxhighlight lang="cpp">#include <cctype> |
|||
#include <iostream> |
#include <iostream> |
||
Line 141: | Line 1,166: | ||
print_list(list); |
print_list(list); |
||
std::cout << "\n"; |
std::cout << "\n"; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
|||
The output of this program is |
|||
<pre> |
|||
[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] |
|||
[1, 2, 3, 4, 5, 6, 7, 8] |
|||
</pre> |
|||
=={{header|Ceylon}}== |
|||
<syntaxhighlight lang="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()); |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
<pre> |
||
[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] |
[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] |
||
Line 150: | Line 1,195: | ||
=={{header|Clojure}}== |
=={{header|Clojure}}== |
||
The following returns a lazy sequence of the flattened data structure. |
The following returns a lazy sequence of the flattened data structure. |
||
< |
<syntaxhighlight lang="lisp">(defn flatten [coll] |
||
(lazy-seq |
(lazy-seq |
||
(when-let [s (seq coll)] |
(when-let [s (seq coll)] |
||
(if (coll? (first s)) |
(if (coll? (first s)) |
||
(concat (flatten (first s)) (flatten ( |
(concat (flatten (first s)) (flatten (rest s))) |
||
(cons (first s) (flatten ( |
(cons (first s) (flatten (rest s)))))))</syntaxhighlight> |
||
The built-in flatten is implemented as: |
|||
<syntaxhighlight lang="lisp">(defn flatten [x] |
|||
(filter (complement sequential?) |
|||
(rest (tree-seq sequential? seq x))))</syntaxhighlight> |
|||
=={{header|CoffeeScript}}== |
|||
<syntaxhighlight lang="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 |
|||
</syntaxhighlight> |
|||
Ouput: |
|||
<syntaxhighlight lang="text"> |
|||
> coffee foo.coffee |
|||
[ 1, 2, 3, 4, 5, 6, 7, 8 ] |
|||
</syntaxhighlight> |
|||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |
||
< |
<syntaxhighlight lang="lisp">(defun flatten (structure) |
||
( |
(cond ((null structure) nil) |
||
((atom structure) (list structure)) |
|||
(t (mapcan #'flatten structure))))</syntaxhighlight> |
|||
(if (listp item) |
|||
or, from Paul Graham's OnLisp, |
|||
(map nil #'scan item) |
|||
<syntaxhighlight lang="lisp"> |
|||
(push item result)))) |
|||
(defun flatten (ls) |
|||
(scan tree)) |
|||
(labels ((mklist (x) (if (listp x) x (list x)))) |
|||
(nreverse result)))</lang> |
|||
(mapcan #'(lambda (x) (if (atom x) (mklist x) (flatten x))) ls))) |
|||
</syntaxhighlight> |
|||
Note that since, in Common Lisp, the empty list, boolean false and <code>nil</code> are the same thing, a tree of <code>nil</code> values cannot be flattened; they will disappear. |
|||
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. |
|||
A third version that is recursive, imperative, and reasonably fast. |
|||
<syntaxhighlight lang="lisp">(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)))</syntaxhighlight> |
|||
The following version is tail recursive and functional. |
|||
<syntaxhighlight lang="lisp">(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)))</syntaxhighlight> |
|||
The next version is imperative, iterative and does not make use of a stack. It is faster than the versions given above. |
|||
<syntaxhighlight lang="lisp">(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))))))</syntaxhighlight> |
|||
The above implementations of flatten give the same output on nested proper lists. |
|||
{{Out}} |
|||
<pre>CL-USER> (flatten '((1) 2 ((3 4) 5) ((())) (((6))) 7 8 ())) |
|||
(1 2 3 4 5 6 7 8)</pre> |
|||
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. |
|||
=={{header|Crystal}}== |
|||
<syntaxhighlight lang="ruby"> |
|||
[[1], 2, [[3, 4], 5], [[[] of Int32]], [[[6]]], 7, 8, [] of Int32].flatten() |
|||
</syntaxhighlight> |
|||
<syntaxhighlight lang="bash"> |
|||
[1, 2, 3, 4, 5, 6, 7, 8] |
|||
</syntaxhighlight> |
|||
=={{header|D}}== |
|||
Instead of a Java-like class-based version, this version minimizes heap activity using a tagged union. |
|||
<syntaxhighlight lang="d">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; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] |
|||
[1, 2, 3, 4, 5, 6, 7, 8]</pre> |
|||
===With an Algebraic Data Type=== |
|||
A shorter and more cryptic version. |
|||
<syntaxhighlight lang="d">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; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
[1, 2, 3, 4, 5, 6, 7, 8] |
|||
=={{header|Déjà Vu}}== |
|||
<syntaxhighlight lang="dejavu">(flatten): |
|||
for i in copy: |
|||
i |
|||
if = :list type dup: |
|||
(flatten) |
|||
flatten l: |
|||
[ (flatten) l ] |
|||
!. flatten [ [ 1 ] 2 [ [ 3 4 ] 5 ] [ [ [] ] ] [ [ [ 6 ] ] ] 7 8 [] ]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[ 1 2 3 4 5 6 7 8 ]</pre> |
|||
=={{header|E}}== |
=={{header|E}}== |
||
< |
<syntaxhighlight lang="e">def flatten(nested) { |
||
def flat := [].diverge() |
def flat := [].diverge() |
||
def recur(x) { |
def recur(x) { |
||
Line 182: | Line 1,402: | ||
recur(nested) |
recur(nested) |
||
return flat.snapshot() |
return flat.snapshot() |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang="e">? flatten([[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]) |
||
# value: [1, 2, 3, 4, 5, 6, 7, 8]</ |
# value: [1, 2, 3, 4, 5, 6, 7, 8]</syntaxhighlight> |
||
=={{header|EchoLisp}}== |
|||
The built-in '''(flatten list)''' is defined as follows: |
|||
<syntaxhighlight lang="lisp"> |
|||
(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)) |
|||
</syntaxhighlight> |
|||
=={{header|Ela}}== |
|||
This implementation can flattern any given list: |
|||
<syntaxhighlight lang="ela">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</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[1,2,3,4,5,6,7,8]</pre> |
|||
An alternative solution: |
|||
<syntaxhighlight lang="ela">flat [] = [] |
|||
flat (x::xs) |
|||
| x is List = flat x ++ flat xs |
|||
| else = x :: flat xs</syntaxhighlight> |
|||
=={{header|Elixir}}== |
|||
<syntaxhighlight lang="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) |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[1, 2, 3, 4, 5, 6, 7, 8] |
|||
[1, 2, 3, 4, 5, 6, 7, 8] |
|||
</pre> |
|||
=={{header|Elm}}== |
|||
<syntaxhighlight lang="haskell"> |
|||
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) |
|||
</syntaxhighlight> |
|||
=={{header|Emacs Lisp}}== |
|||
<syntaxhighlight lang="lisp">(defun flatten (mylist) |
|||
(cond |
|||
((null mylist) nil) |
|||
((atom mylist) (list mylist)) |
|||
(t |
|||
(append (flatten (car mylist)) (flatten (cdr mylist))))))</syntaxhighlight> |
|||
The flatten-tree function was added in Emacs 27.1 or earlier. |
|||
<syntaxhighlight lang="lisp"> |
|||
(flatten-tree mylist) |
|||
</syntaxhighlight> |
|||
=={{header|Erlang}}== |
=={{header|Erlang}}== |
||
There's a standard function (lists:flatten/ |
There's a standard function (lists:flatten/1) that does it more efficiently, but this is the cleanest implementation you could have; |
||
< |
<syntaxhighlight lang="erlang">flatten([]) -> []; |
||
flatten([H|T]) -> flatten(H) ++ flatten(T); |
flatten([H|T]) -> flatten(H) ++ flatten(T); |
||
flatten(H) -> [H].</ |
flatten(H) -> [H].</syntaxhighlight> |
||
=={{header|Euphoria}}== |
|||
{{works with|Euphoria|4.0.0}} |
|||
<syntaxhighlight lang="euphoria">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)</syntaxhighlight> |
|||
{{out}} |
|||
<pre>{ |
|||
{1}, |
|||
2, |
|||
{ |
|||
{3,4}, |
|||
5 |
|||
}, |
|||
{ |
|||
{{}} |
|||
}, |
|||
{ |
|||
{ |
|||
{6} |
|||
} |
|||
}, |
|||
7, |
|||
8, |
|||
{} |
|||
} |
|||
{1,2,3,4,5,6,7,8}</pre> |
|||
=={{header|F_Sharp|F#}}== |
|||
As with Haskell and OCaml we have to define our list as an algebraic data type, to be strongly typed: |
|||
<syntaxhighlight lang="fsharp">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]</syntaxhighlight> |
|||
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. |
|||
<syntaxhighlight lang="fsharp"> |
|||
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] |
|||
</syntaxhighlight> |
|||
=={{header|Factor}}== |
|||
USE: sequences.deep |
|||
( scratchpad ) { { 1 } 2 { { 3 4 } 5 } { { { } } } { { { 6 } } } 7 8 { } } flatten . |
|||
{ 1 2 3 4 5 6 7 8 } |
|||
=={{header|Fantom}}== |
|||
<syntaxhighlight lang="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)) |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
=={{header|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 |
|||
<syntaxhighlight lang="forth">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</syntaxhighlight> |
|||
=={{header|Fortran}}== |
|||
<syntaxhighlight lang="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 |
|||
</syntaxhighlight> |
|||
===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. |
|||
<syntaxhighlight lang="fortran"> |
|||
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</syntaxhighlight> |
|||
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. |
|||
=={{header|Frink}}== |
|||
<syntaxhighlight lang="frink"> |
|||
a = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] |
|||
println[flatten[a]] |
|||
</syntaxhighlight> |
|||
=={{header|FutureBasic}}== |
|||
Definitely old school. |
|||
<syntaxhighlight lang="futurebasic"> |
|||
local fn FlattenList( list as Str255 ) as Str255 |
|||
long i |
|||
Str255 flatStr, commaStr |
|||
flatStr = "" |
|||
for i = 1 to len$(list) |
|||
if ( instr$( 0, "[] ,", mid$( list, i, 1 ) ) === 0 ) |
|||
flatStr += commaStr + mid$( list, i, 1 ) |
|||
commaStr = ", " |
|||
end if |
|||
next |
|||
end fn = flatStr |
|||
window 1, @"Flatten a list", ( 0, 0, 350, 150 ) |
|||
print "["; fn FlattenList( "[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8 []]" ); "]" |
|||
HandleEvents</syntaxhighlight> |
|||
{{output}} |
|||
<pre>[1, 2, 3, 4, 5, 6, 7, 8]</pre> |
|||
Modern and a little outside the box. |
|||
<syntaxhighlight lang="futurebasic"> |
|||
void local fn FlattenAList |
|||
CFStringRef listStr = @"[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]" |
|||
CFArrayRef listArr = fn StringComponentsSeparatedByCharactersInSet( listStr, fn CharacterSetWithCharactersInString( @"\"[ ]," ) ) |
|||
CFMutableArrayRef mutArr = fn MutableArrayWithArray( listArr ) |
|||
MutableArrayRemoveObject( mutArr, @"" ) |
|||
CFStringRef flatStr = fn ArrayComponentsJoinedByString( mutArr, @", " ) |
|||
printf @"[%@]", flatStr |
|||
end fn |
|||
fn FlattenAList |
|||
HandleEvents |
|||
</syntaxhighlight> |
|||
{{output}} |
|||
<pre>[1, 2, 3, 4, 5, 6, 7, 8]</pre> |
|||
=={{header|GAP}}== |
|||
<syntaxhighlight lang="gap">Flat([[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]);</syntaxhighlight> |
|||
=={{header|GNU APL}}== |
|||
Using (monadic) enlist function ε. Sometimes called 'Super Ravel'. |
|||
<syntaxhighlight lang="apl"> |
|||
⊢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'┃ |
|||
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛ |
|||
</syntaxhighlight> |
|||
=={{header|Go}}== |
|||
<syntaxhighlight lang="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 |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[[1] 2 [[3 4] 5] [[[]]] [[[6]]] 7 8 []] |
|||
[1 2 3 4 5 6 7 8] |
|||
</pre> |
|||
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. |
|||
<syntaxhighlight lang="go">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 |
|||
}</syntaxhighlight> |
|||
=={{header|Groovy}}== |
=={{header|Groovy}}== |
||
Line 197: | Line 1,988: | ||
<code>List.flatten()</code> is a Groovy built-in that returns a flattened copy of the source list: |
<code>List.flatten()</code> is a Groovy built-in that returns a flattened copy of the source list: |
||
< |
<syntaxhighlight lang="groovy">assert [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []].flatten() == [1, 2, 3, 4, 5, 6, 7, 8]</syntaxhighlight> |
||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
Line 203: | Line 1,994: | ||
In Haskell we have to interpret this structure as an algebraic data type. |
In Haskell we have to interpret this structure as an algebraic data type. |
||
< |
<syntaxhighlight lang="haskell">import Data.Tree (Tree(..), flatten) |
||
-- [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] |
-- [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] |
||
-- implemented as multiway tree: |
-- implemented as multiway tree: |
||
-- Data.Tree represents trees where nodes have values too, unlike the trees in our problem. |
-- 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, |
-- 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 |
-- and a leaf will have a one-element list value and no subtrees |
||
list :: Tree [Int] |
list :: Tree [Int] |
||
list = |
list = |
||
Node |
|||
Node [] [Node [1] []], |
|||
[] |
|||
[ 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 [] [] |
|||
] |
|||
Node [] [] |
|||
] |
|||
flattenList |
flattenList :: Tree [a] -> [a] |
||
flattenList = concat . flatten |
|||
Flattening the list: |
|||
<pre>*Main> flattenList list |
|||
[1,2,3,4,5,6,7,8]</pre> |
|||
main :: IO () |
|||
Alternately: |
|||
main = print $ flattenList list</syntaxhighlight> |
|||
<lang haskell>data Tree a = Leaf a | Node [Tree a] |
|||
{{Out}} |
|||
<pre>[1,2,3,4,5,6,7,8]</pre> |
|||
Alternately: |
|||
<syntaxhighlight lang="haskell">data Tree a |
|||
= Leaf a |
|||
| Node [Tree a] |
|||
flatten :: Tree a -> [a] |
flatten :: Tree a -> [a] |
||
flatten (Leaf x) = [x] |
flatten (Leaf x) = [x] |
||
flatten (Node xs) = |
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]</syntaxhighlight> |
|||
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.) |
|||
<syntaxhighlight lang="haskell">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]</syntaxhighlight> |
|||
=={{header|Hy}}== |
|||
<syntaxhighlight lang="clojure">(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]</syntaxhighlight> |
|||
=={{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. |
|||
<syntaxhighlight lang="icon">link strings # for compress,deletec,pretrim |
|||
procedure sflatten(s) # uninteresting string solution |
|||
return pretrim(trim(compress(deletec(s,'[ ]'),',') ,','),',') |
|||
end</syntaxhighlight> |
|||
{{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. |
|||
<syntaxhighlight lang="icon">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</syntaxhighlight> |
|||
Finally a demo routine to drive these and a helper to show how it works. |
|||
<syntaxhighlight lang="icon">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</syntaxhighlight> |
|||
=={{header|Insitux}}== |
|||
Insitux has a built-in flatten function. |
|||
<syntaxhighlight lang="insitux"> |
|||
(flatten [[1] 2 [[3 4] 5] [[[]]] [[[6]]] 7 8 []]) |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[1 2 3 4 5 6 7 8] |
|||
</pre> |
|||
=={{header|Ioke}}== |
|||
<syntaxhighlight lang="ioke">iik> [[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]</syntaxhighlight> |
|||
=={{header|Isabelle}}== |
|||
<syntaxhighlight lang="isabelle">theory Scratch |
|||
imports Main |
|||
begin |
|||
datatype 'a tree = Leaf 'a ("<_>") |
|||
| Node "'a tree list" ("⟦ _ ⟧") |
|||
text‹The datatype introduces special pretty printing:› |
|||
lemma "Leaf a = <a>" by simp |
|||
lemma "Node [] = ⟦ [] ⟧" by simp |
|||
definition "example ≡ ⟦[ ⟦[<1>]⟧, <2>, ⟦[ ⟦[<3>, <4>]⟧, <5>]⟧, ⟦[⟦[⟦[]⟧]⟧]⟧, ⟦[⟦[⟦[<6>]⟧]⟧]⟧, <7>, <8>, ⟦[]⟧ ]⟧" |
|||
lemma "example = |
|||
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 [] |
|||
]" |
|||
by(simp add: example_def) |
|||
fun flatten :: "'a tree ⇒ 'a list" where |
|||
"flatten (Leaf a) = [a]" |
|||
| "flatten (Node xs) = concat (map flatten xs)" |
|||
lemma "flatten example = [1, 2, 3, 4, 5, 6, 7, 8]" |
|||
main = print $ flatten $ Node [Node [Leaf 1], |
|||
by(simp add: example_def) |
|||
Leaf 2, |
|||
Node [Node [Leaf 3, Leaf 4], Leaf 5], |
|||
Node [Node [Node []]], |
|||
Node [Node [Node [Leaf 6]]], |
|||
Leaf 7, |
|||
Leaf 8, |
|||
Node []] |
|||
end</syntaxhighlight> |
|||
-- output: [1,2,3,4,5,6,7,8]</lang> |
|||
=={{header|J}}== |
=={{header|J}}== |
||
'''Solution''': |
'''Solution''': |
||
< |
<syntaxhighlight lang="j">flatten =: [: ; <S:0</syntaxhighlight> |
||
'''Example''': |
'''Example''': |
||
< |
<syntaxhighlight lang="j"> NB. create and display nested noun li |
||
]li =. (<1) ; 2; ((<3;4); 5) ; ((<a:)) ; ((<(<6))) ; 7; 8; <a: |
]li =. (<1) ; 2; ((<3; 4); 5) ; ((<a:)) ; ((<(<6))) ; 7; 8; <a: |
||
+---+-+-----------+----+-----+-+-+--+ |
+---+-+-----------+----+-----+-+-+--+ |
||
|+-+|2|+-------+-+|+--+|+---+|7|8|++| |
|+-+|2|+-------+-+|+--+|+---+|7|8|++| |
||
Line 266: | Line 2,196: | ||
| | |+-------+-+| | | | | | |
| | |+-------+-+| | | | | | |
||
+---+-+-----------+----+-----+-+-+--+ |
+---+-+-----------+----+-----+-+-+--+ |
||
flatten li |
|||
flatten li |
|||
1 2 3 4 5 6 7 8</lang> |
|||
1 2 3 4 5 6 7 8</syntaxhighlight> |
|||
'''Notes:''' |
|||
The primitive <code>;</code> removes one level of nesting. |
|||
<code><S:0</code> takes an arbitrarily nested list and puts everything one level deep. |
|||
<code>[:</code> is glue, here. |
|||
We do not use <code>;</code> 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 <code>]S:0</code> (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:'''<br> |
|||
The previous solution can be generalized to flatten the nesting and shape for a list of arbitrary values that include arrays of any rank: |
|||
<syntaxhighlight lang="j">flatten2 =: [: ; <@,S:0</syntaxhighlight> |
|||
'''Example:''' |
|||
<syntaxhighlight lang="j"> ]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</syntaxhighlight> |
|||
Here, we have replaced <code><S:0</code> with <code><@,S:0</code> so our leaves are flattened before the final step where their boxes are razed. |
|||
=={{header|Java}}== |
=={{header|Java}}== |
||
{{works with|Java|1.5+}} |
{{works with|Java|1.5+}} |
||
<lang java5>import java.util.LinkedList; |
|||
The <code>flatten</code> method was overloaded for better separation of concerns. On the first one you can pass any <code>List</code> and get it flat into a <code>LinkedList</code> implementation. On the other one you can pass any <code>List</code> implementation you like for both lists. |
|||
Note that both implementations can only put the result into type <code>List<Object></code>. We cannot type-safely put the result into a generic type <code>List<T></code> because there is no way to enforce that the original list contains elements of "type T or lists of elements which are T or further lists..."; there is no generic type parameter that will express that restriction. Since we must accept lists of any elements as an argument, we can only safely put them in a <code>List<Object></code>. |
|||
Actual Workhorse code |
|||
<syntaxhighlight lang="java5">import java.util.LinkedList; |
|||
import java.util.List; |
import java.util.List; |
||
import java.util.Arrays; |
|||
public class Flatten { |
|||
public final class FlattenUtil { |
|||
List<Object> retVal = new LinkedList<Object>(); |
|||
public static List<Object> flatten(List<?> list) { |
|||
for(Object item:list){ |
|||
List<Object> retVal = new LinkedList<Object>(); |
|||
if(item instanceof List){ |
|||
flatten(list, retVal); |
|||
retVal.addAll(flatten((List)item)); |
|||
return retVal; |
|||
}else{ |
|||
} |
|||
retVal.add(item); |
|||
public static void flatten(List<?> fromTreeList, List<Object> toFlatList) { |
|||
for (Object item : fromTreeList) { |
|||
if (item instanceof List<?>) { |
|||
flatten((List<?>) item, toFlatList); |
|||
} else { |
|||
toFlatList.add(item); |
|||
} |
|||
} |
|||
} |
|||
}</syntaxhighlight> |
|||
Method showing population of the test List and usage of flatten method. |
|||
<syntaxhighlight lang="java5">import static java.util.Arrays.asList; |
|||
import java.util.List; |
|||
public final class FlattenTestMain { |
|||
public static void main(String[] args) { |
|||
List<Object> treeList = a(a(1), 2, a(a(3, 4), 5), a(a(a())), a(a(a(6))), 7, 8, a()); |
|||
List<Object> flatList = FlattenUtil.flatten(treeList); |
|||
System.out.println(treeList); |
|||
System.out.println("flatten: " + flatList); |
|||
} |
|||
private static List<Object> a(Object... a) { |
|||
return asList(a); |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] |
|||
flatten: [1, 2, 3, 4, 5, 6, 7, 8]</pre> |
|||
;Functional version |
|||
{{works with|Java|8+}} |
|||
<syntaxhighlight lang="java5">import java.util.List; |
|||
import java.util.stream.Stream; |
|||
import java.util.stream.Collectors; |
|||
public final class FlattenUtil { |
|||
public static Stream<Object> flattenToStream(List<?> list) { |
|||
return list.stream().flatMap(item -> |
|||
item instanceof List<?> ? |
|||
flattenToStream((List<?>)item) : |
|||
Stream.of(item)); |
|||
} |
|||
public static List<Object> flatten(List<?> list) { |
|||
return flattenToStream(list).collect(Collectors.toList()); |
|||
} |
|||
}</syntaxhighlight> |
|||
=={{header|JavaScript}}== |
|||
===ES5=== |
|||
<syntaxhighlight lang="javascript">function flatten(list) { |
|||
return list.reduce(function (acc, val) { |
|||
return acc.concat(val.constructor === Array ? flatten(val) : val); |
|||
}, []); |
|||
}</syntaxhighlight> |
|||
Or, expressed in terms of the more generic '''concatMap''' function: |
|||
<syntaxhighlight lang="javascript">(function () { |
|||
'use strict'; |
|||
// flatten :: Tree a -> [a] |
|||
function flatten(t) { |
|||
return (t instanceof Array ? concatMap(flatten, t) : t); |
|||
} |
|||
// concatMap :: (a -> [b]) -> [a] -> [b] |
|||
function concatMap(f, xs) { |
|||
return [].concat.apply([], xs.map(f)); |
|||
} |
|||
return flatten( |
|||
[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] |
|||
); |
|||
})();</syntaxhighlight> |
|||
From fusion of ''flatten'' with ''concatMap'' we can then derive: |
|||
<syntaxhighlight lang="javascript"> // flatten :: Tree a -> [a] |
|||
function flatten(a) { |
|||
return a instanceof Array ? [].concat.apply([], a.map(flatten)) : a; |
|||
}</syntaxhighlight> |
|||
For example: |
|||
<syntaxhighlight lang="javascript">(function () { |
|||
'use strict'; |
|||
// flatten :: Tree a -> [a] |
|||
function flatten(a) { |
|||
return a instanceof Array ? [].concat.apply([], a.map(flatten)) : a; |
|||
} |
|||
return flatten( |
|||
[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] |
|||
); |
|||
})();</syntaxhighlight> |
|||
{{Out}} |
|||
<pre>[1, 2, 3, 4, 5, 6, 7, 8]</pre> |
|||
===ES6=== |
|||
====Built-in==== |
|||
<syntaxhighlight lang="javascript">// flatten :: NestedList a -> [a] |
|||
const flatten = nest => |
|||
nest.flat(Infinity);</syntaxhighlight> |
|||
====Recursive==== |
|||
<syntaxhighlight lang="javascript">// flatten :: NestedList a -> [a] |
|||
const flatten = t => { |
|||
const go = x => |
|||
Array.isArray(x) ? ( |
|||
x.flatMap(go) |
|||
) : x; |
|||
return go(t); |
|||
};</syntaxhighlight> |
|||
====Iterative==== |
|||
<syntaxhighlight lang="javascript">function flatten(list) { |
|||
for (let i = 0; i < list.length; i++) { |
|||
while (true) { |
|||
if (Array.isArray(list[i])) { |
|||
list.splice(i, 1, ...list[i]); |
|||
} else { |
|||
break; |
|||
} |
} |
||
} |
} |
||
return retVal; |
|||
} |
} |
||
return list; |
|||
}</syntaxhighlight> |
|||
Or alternatively: |
|||
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() |
|||
); |
|||
<syntaxhighlight lang="javascript">// flatten :: Nested List a -> a |
|||
System.out.println(test); |
|||
const flatten = t => { |
|||
System.out.println(flatten(test)); |
|||
let xs = t; |
|||
} |
|||
}</lang> |
|||
Output: |
|||
<pre>[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] |
|||
[1, 2, 3, 4, 5, 6, 7, 8]</pre> |
|||
while (xs.some(Array.isArray)) { |
|||
=={{header|JavaScript}}== |
|||
xs = [].concat(...xs); |
|||
{{libheader|Prototype}} |
|||
} |
|||
{{works with|a browser}} |
|||
<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("<p>before</p>"); |
|||
a.each(function(e){document.write("<div>" + e + " " + typeof(e) + "</div>")}); |
|||
var f = a.flatten(); |
|||
document.write("<p>after</p>"); |
|||
f.each(function(e){document.write("<div>" + e + " " + typeof(e) + "</div>")}); |
|||
</script></lang> |
|||
output: |
|||
<pre style="height:25ex;overflow:scroll">before |
|||
return xs; |
|||
1 object |
|||
};</syntaxhighlight> |
|||
2 number |
|||
3,4,5 object |
|||
object |
|||
6 object |
|||
7 number |
|||
8 number |
|||
object |
|||
Result is always: |
|||
after |
|||
<pre>[1, 2, 3, 4, 5, 6, 7, 8]</pre> |
|||
=={{header|Joy}}== |
|||
1 number |
|||
<syntaxhighlight lang="joy"> |
|||
2 number |
|||
"seqlib" libload. |
|||
3 number |
|||
4 number |
|||
[[1] 2 [[3 4] 5] [[[]]] [[[6]]] 7 8 []] treeflatten. |
|||
5 number |
|||
6 number |
|||
(* output: [1 2 3 4 5 6 7 8] *) |
|||
7 number |
|||
</syntaxhighlight> |
|||
8 number</pre> |
|||
=={{header|jq}}== |
|||
Recent (1.4+) versions of jq include the following flatten filter:<syntaxhighlight lang="jq">def flatten: |
|||
reduce .[] as $i |
|||
([]; |
|||
if $i | type == "array" then . + ($i | flatten) |
|||
else . + [$i] |
|||
end);</syntaxhighlight>Example:<syntaxhighlight lang="jq"> |
|||
[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] | flatten |
|||
[1,2,3,4,5,6,7,8]</syntaxhighlight> |
|||
=={{header|Jsish}}== |
|||
From Javascript entry, with change to test for ''typeof'' equal ''"array"''. |
|||
<syntaxhighlight lang="javascript">/* Flatten list, in Jsish */ |
|||
function flatten(list) { |
|||
return list.reduce(function (acc, val) { |
|||
return acc.concat(typeof val === "array" ? flatten(val) : val); |
|||
}, []); |
|||
} |
|||
if (Interp.conf('unitTest')) { |
|||
; flatten([[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]); |
|||
} |
|||
/* |
|||
=!EXPECTSTART!= |
|||
flatten([[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]) ==> [ 1, 2, 3, 4, 5, 6, 7, 8 ] |
|||
=!EXPECTEND!= |
|||
*/</syntaxhighlight> |
|||
{{out}} |
|||
<pre>prompt$ jsish --U flatten.jsi |
|||
flatten([[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]) ==> [ 1, 2, 3, 4, 5, 6, 7, 8 ]</pre> |
|||
=={{header|Julia}}== |
|||
(Note that Julia versions prior to 0.5 automatically flattened nested arrays.) |
|||
The following version of flatten makes use of the higher order function ''mapreduce''. |
|||
<syntaxhighlight lang="julia">isflat(x) = isempty(x) || first(x) === x |
|||
function flat_mapreduce(arr) |
|||
mapreduce(vcat, arr, init=[]) do x |
|||
isflat(x) ? x : flat(x) |
|||
end |
|||
end</syntaxhighlight> |
|||
An iterative recursive version that uses less memory but is slower: |
|||
<syntaxhighlight lang="julia">function flat_recursion(arr) |
|||
res = [] |
|||
function grep(v) |
|||
for x in v |
|||
if x isa Array |
|||
grep(x) |
|||
else |
|||
push!(res, x) |
|||
end |
|||
end |
|||
end |
|||
grep(arr) |
|||
res |
|||
end</syntaxhighlight> |
|||
Using the Iterators library from the Julia base: |
|||
<syntaxhighlight lang="julia">function flat_iterators(arr) |
|||
while any(a -> a isa Array, arr) |
|||
arr = collect(Iterators.flatten(arr)) |
|||
end |
|||
arr |
|||
end</syntaxhighlight> |
|||
Benchmarking these three functions using the BenchmarkTools package yields the following results: |
|||
<syntaxhighlight lang="julia">using BenchmarkTools |
|||
arr = [[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] |
|||
@show flat_mapreduce(arr) |
|||
@show flat_recursion(arr) |
|||
@show flat_iterators(arr) |
|||
@btime flat_mapreduce($arr) |
|||
@btime flat_recursion($arr) |
|||
@btime flat_iterators($arr)</syntaxhighlight>{{out}} |
|||
<pre> |
|||
flat_mapreduce(arr) = Any[1, 2, 3, 4, 5, 6, 7, 8] |
|||
flat_recursion(arr) = Any[1, 2, 3, 4, 5, 6, 7, 8] |
|||
flat_iterators(arr) = [1, 2, 3, 4, 5, 6, 7, 8] |
|||
14.163 μs (131 allocations: 4.27 KiB) |
|||
500.824 ns (4 allocations: 176 bytes) |
|||
28.223 μs (133 allocations: 4.33 KiB) |
|||
</pre> |
|||
=={{header|K}}== |
|||
In K, join is: <code>,</code> and reduce/fold (called "over") is: <code>/</code>. With a monadic argument (as ,/ is), over repeats application until reaching a fixed-point. |
|||
So to flatten a list of arbitrary depth, you can join-over-over, or reduce a list with a function that reduces a list with a join function: |
|||
<syntaxhighlight lang="k">,//((1); 2; ((3;4); 5); ((())); (((6))); 7; 8; ())</syntaxhighlight> |
|||
=={{header|Kotlin}}== |
|||
<syntaxhighlight lang="scala">// version 1.0.6 |
|||
@Suppress("UNCHECKED_CAST") |
|||
fun flattenList(nestList: List<Any>, flatList: MutableList<Int>) { |
|||
for (e in nestList) |
|||
if (e is Int) |
|||
flatList.add(e) |
|||
else |
|||
// using unchecked cast here as can't check for instance of 'erased' generic type |
|||
flattenList(e as List<Any>, flatList) |
|||
} |
|||
fun main(args: Array<String>) { |
|||
val nestList : List<Any> = listOf( |
|||
listOf(1), |
|||
2, |
|||
listOf(listOf(3, 4), 5), |
|||
listOf(listOf(listOf<Int>())), |
|||
listOf(listOf(listOf(6))), |
|||
7, |
|||
8, |
|||
listOf<Int>() |
|||
) |
|||
println("Nested : " + nestList) |
|||
val flatList = mutableListOf<Int>() |
|||
flattenList(nestList, flatList) |
|||
println("Flattened : " + flatList) |
|||
}</syntaxhighlight> |
|||
Or, using a more functional approach: |
|||
<syntaxhighlight lang="scala"> |
|||
fun flatten(list: List<*>): List<*> { |
|||
fun flattenElement(elem: Any?): Iterable<*> { |
|||
return if (elem is List<*>) |
|||
if (elem.isEmpty()) elem |
|||
else flattenElement(elem.first()) + flattenElement(elem.drop(1)) |
|||
else listOf(elem) |
|||
} |
|||
return list.flatMap { elem -> flattenElement(elem) } |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Nested : [[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] |
|||
Flattened : [1, 2, 3, 4, 5, 6, 7, 8] |
|||
</pre> |
|||
=={{header|Lambdatalk}}== |
|||
Lambdatalk doesn't have a builtin primitive flattening a multidimensionnal array. |
|||
<syntaxhighlight lang="scheme"> |
|||
1) Let's create this function |
|||
{def A.flatten |
|||
{def A.flatten.r |
|||
{lambda {:a} |
|||
{if {A.empty? :a} |
|||
then |
|||
else {let { {:b {A.first :a}} |
|||
} {if {A.array? :b} |
|||
then {A.flatten.r :b} |
|||
else :b} } |
|||
{A.flatten.r {A.rest :a}} }}} |
|||
{lambda {:a} |
|||
{A.new {A.flatten.r :a}}}} |
|||
-> A.flatten |
|||
and test it |
|||
{def list |
|||
{A.new |
|||
{A.new 1} |
|||
2 |
|||
{A.new {A.new 3 4} 5} |
|||
{A.new {A.new {A.new }}} |
|||
{A.new {A.new {A.new 6}}} |
|||
7 |
|||
8 |
|||
{A.new} |
|||
}} |
|||
-> [[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] |
|||
{A.flatten {list}} |
|||
-> [1,2,3,4,5,6,7,8] |
|||
</syntaxhighlight> |
|||
=={{header|Lasso}}== |
|||
Lasso Delve is a Lasso utility method explicitly for handling embedded arrays. With one array which contain other arrays, delve allows you to treat one array as a single series of elements, thus enabling easy access to an entire tree of values. [http://www.lassosoft.com/lassoDocs/languageReference/obj/delve www.lassosoft.com/lassoDocs/languageReference/obj/delve Lasso reference on Delve] |
|||
<syntaxhighlight lang="lasso">local(original = json_deserialize('[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]')) |
|||
#original |
|||
'<br />' |
|||
(with item in delve(#original) |
|||
select #item) -> asstaticarray</syntaxhighlight> |
|||
<pre>array(array(1), 2, array(array(3, 4), 5), array(array(array())), array(array(array(6))), 7, 8, array()) |
|||
staticarray(1, 2, 3, 4, 5, 6, 7, 8)</pre> |
|||
=={{header|LFE}}== |
|||
<syntaxhighlight lang="lisp"> |
|||
> (: lists flatten '((1) 2 ((3 4) 5) ((())) (((6))) 7 8 ())) |
|||
(1 2 3 4 5 6 7 8) |
|||
</syntaxhighlight> |
|||
=={{header|Logo}}== |
=={{header|Logo}}== |
||
< |
<syntaxhighlight lang="logo">to flatten :l |
||
if not list? :l [output :l] |
if not list? :l [output :l] |
||
if empty? :l [output []] |
if empty? :l [output []] |
||
Line 366: | Line 2,634: | ||
make "a [[1] 2 [[3 4] 5] [[[]]] [[[6]]] 7 8 []] |
make "a [[1] 2 [[3 4] 5] [[[]]] [[[6]]] 7 8 []] |
||
show flatten :a</ |
show flatten :a</syntaxhighlight> |
||
=={{header|Logtalk}}== |
|||
<syntaxhighlight lang="logtalk">flatten(List, Flatted) :- |
|||
flatten(List, [], Flatted). |
|||
flatten(Var, Tail, [Var| Tail]) :- |
|||
var(Var), |
|||
!. |
|||
flatten([], Flatted, Flatted) :- |
|||
!. |
|||
flatten([Head| Tail], List, Flatted) :- |
|||
!, |
|||
flatten(Tail, List, Aux), |
|||
flatten(Head, Aux, Flatted). |
|||
flatten(Head, Tail, [Head| Tail]).</syntaxhighlight> |
|||
=={{header|Lua}}== |
|||
<syntaxhighlight lang="lua">function flatten(list) |
|||
if type(list) ~= "table" then return {list} end |
|||
local flat_list = {} |
|||
for _, elem in ipairs(list) do |
|||
for _, val in ipairs(flatten(elem)) do |
|||
flat_list[#flat_list + 1] = val |
|||
end |
|||
end |
|||
return flat_list |
|||
end |
|||
test_list = {{1}, 2, {{3,4}, 5}, {{{}}}, {{{6}}}, 7, 8, {}} |
|||
print(table.concat(flatten(test_list), ","))</syntaxhighlight> |
|||
=={{header|Maple}}== |
|||
This can be accomplished using the <code>Flatten</code> command from the <code>ListTools</code>, or with a custom recursive procedure. |
|||
<syntaxhighlight lang="maple"> |
|||
L := [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]: |
|||
with(ListTools): |
|||
Flatten(L); |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[1, 2, 3, 4, 5, 6, 7, 8] |
|||
</pre> |
|||
<syntaxhighlight lang="maple"> |
|||
flatten := proc(x) |
|||
`if`(type(x,'list'),seq(procname(i),i = x),x); |
|||
end proc: |
|||
L := [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]: |
|||
[flatten(L)]; |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[1, 2, 3, 4, 5, 6, 7, 8] |
|||
</pre> |
|||
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
|||
<syntaxhighlight lang="mathematica">Flatten[{{1}, 2, {{3, 4}, 5}, {{{}}}, {{{6}}}, 7, 8, {}}]</syntaxhighlight> |
|||
=={{header|Maxima}}== |
|||
<syntaxhighlight lang="maxima">flatten([[[1, 2, 3], 4, [5, [6, 7]], 8], [[9, 10], 11], 12]); |
|||
/* [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] */</syntaxhighlight> |
|||
=={{header|Mercury}}== |
|||
As with Haskell we need to use an algebraic data type. |
|||
<syntaxhighlight lang="mercury">:- module flatten_a_list. |
|||
:- interface. |
|||
:- import_module io. |
|||
:- pred main(io::di, io::uo) is det. |
|||
:- implementation. |
|||
:- import_module list. |
|||
:- type tree(T) |
|||
---> leaf(T) |
|||
; node(list(tree(T))). |
|||
:- func flatten(tree(T)) = list(T). |
|||
flatten(leaf(X)) = [X]. |
|||
flatten(node(Xs)) = condense(map(flatten, Xs)). |
|||
main(!IO) :- |
|||
List = 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([]) |
|||
]), |
|||
io.print_line(flatten(List), !IO). |
|||
:- end_module flatten_a_list. |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[1, 2, 3, 4, 5, 6, 7, 8] |
|||
</pre> |
|||
=={{header|min}}== |
|||
{{works with|min|0.37.0}} |
|||
<syntaxhighlight lang="min">( |
|||
(dup 'quotation? any?) 'flatten while |
|||
) ^deep-flatten |
|||
((1) 2 ((3 4) 5) ((())) (((6))) 7 8 ()) deep-flatten puts!</syntaxhighlight> |
|||
{{out}} |
|||
<pre>(1 2 3 4 5 6 7 8)</pre> |
|||
=={{header|Mirah}}== |
|||
<syntaxhighlight lang="mirah">import java.util.ArrayList |
|||
import java.util.List |
|||
import java.util.Collection |
|||
def flatten(list: Collection) |
|||
flatten(list, ArrayList.new) |
|||
end |
|||
def flatten(source: Collection, result: List) |
|||
source.each do |x| |
|||
if x.kind_of?(Collection) |
|||
flatten(Collection(x), result) |
|||
else |
|||
result.add(x) |
|||
result # if branches must return same type |
|||
end |
|||
end |
|||
result |
|||
end |
|||
# creating a list-of-list-of-list fails currently, so constructor calls are needed |
|||
source = [[1], 2, [[3, 4], 5], [[ArrayList.new]], [[[6]]], 7, 8, ArrayList.new] |
|||
puts flatten(source)</syntaxhighlight> |
|||
=={{header|NewLISP}}== |
|||
<syntaxhighlight lang="newlisp">> (flat '((1) 2 ((3 4) 5) ((())) (((6))) 7 8 ())) |
|||
(1 2 3 4 5 6 7 8) |
|||
</syntaxhighlight> |
|||
=={{header|NGS}}== |
|||
Note that when '''kern''' method is called, the multi-dispatch tries to match '''kern''' parameters with given arguments last added '''F''' first: if '''x''' is an array, the second '''F kern''' is invoked, otherwise the first '''F kern''' is invoked. |
|||
NGS defines '''flatten''' as a shallow flatten, hence using '''flatten_r''' here. |
|||
<syntaxhighlight lang="ngs">F flatten_r(a:Arr) |
|||
collector { |
|||
local kern |
|||
F kern(x) collect(x) |
|||
F kern(x:Arr) x.each(kern) |
|||
kern(a) |
|||
} |
|||
echo(flatten_r([[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]))</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[1,2,3,4,5,6,7,8]</pre> |
|||
=={{header|Nim}}== |
|||
Nim is statically-typed, so we need to use an object variant |
|||
<syntaxhighlight lang="nim">type |
|||
TreeList[T] = object |
|||
case isLeaf: bool |
|||
of true: data: T |
|||
of false: list: seq[TreeList[T]] |
|||
proc L[T](list: varargs[TreeList[T]]): TreeList[T] = |
|||
for x in list: |
|||
result.list.add x |
|||
proc N[T](data: T): TreeList[T] = |
|||
TreeList[T](isLeaf: true, data: data) |
|||
proc flatten[T](n: TreeList[T]): seq[T] = |
|||
if n.isLeaf: result = @[n.data] |
|||
else: |
|||
for x in n.list: |
|||
result.add flatten x |
|||
var x = L(L(N 1), N 2, L(L(N 3, N 4), N 5), L(L(L[int]())), L(L(L(N 6))), N 7, N 8, L[int]()) |
|||
echo flatten(x)</syntaxhighlight> |
|||
{{out}} |
|||
<pre>@[1, 2, 3, 4, 5, 6, 7, 8]</pre> |
|||
=={{header|Objective-C}}== |
|||
{{works with|Cocoa}} |
|||
<syntaxhighlight lang="objc2">#import <Foundation/Foundation.h> |
|||
@interface NSArray (FlattenExt) |
|||
@property (nonatomic, readonly) NSArray *flattened; |
|||
@end |
|||
@implementation NSArray (FlattenExt) |
|||
-(NSArray *) flattened { |
|||
NSMutableArray *flattened = [[NSMutableArray alloc] initWithCapacity:self.count]; |
|||
for (id object in self) { |
|||
if ([object isKindOfClass:[NSArray class]]) |
|||
[flattened addObjectsFromArray:((NSArray *)object).flattened]; |
|||
else |
|||
[flattened addObject:object]; |
|||
} |
|||
return [flattened autorelease]; |
|||
} |
|||
@end |
|||
int main() { |
|||
@autoreleasepool { |
|||
NSArray *p = @[ |
|||
@[ @1 ], |
|||
@2, |
|||
@[ @[@3, @4], @5], |
|||
@[ @[ @[ ] ] ], |
|||
@[ @[ @[ @6 ] ] ], |
|||
@7, |
|||
@8, |
|||
@[ ] ]; |
|||
for (id object in unflattened.flattened) |
|||
NSLog(@"%@", object); |
|||
} |
|||
return 0; |
|||
}</syntaxhighlight> |
|||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
||
< |
<syntaxhighlight lang="ocaml"># let flatten = List.concat ;; |
||
val flatten : 'a list list -> 'a list = <fun> |
val flatten : 'a list list -> 'a list = <fun> |
||
Line 378: | Line 2,885: | ||
# (* use another data which can be accepted by the type system *) |
# (* use another data which can be accepted by the type system *) |
||
flatten [[1]; [2; 3; 4]; []; [5; 6]; [7]; [8]] ;; |
flatten [[1]; [2; 3; 4]; []; [5; 6]; [7]; [8]] ;; |
||
- : int list = [1; 2; 3; 4; 5; 6; 7; 8]</ |
- : int list = [1; 2; 3; 4; 5; 6; 7; 8]</syntaxhighlight> |
||
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: |
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: |
||
<syntaxhighlight lang="ocaml"># type 'a tree = Leaf of 'a | Node of 'a tree list ;; |
|||
<div style="width:100%;overflow:scroll"> |
|||
<lang ocaml># type 'a tree = Leaf of 'a | Node of 'a tree list ;; |
|||
type 'a tree = Leaf of 'a | Node of 'a tree list |
type 'a tree = Leaf of 'a | Node of 'a tree list |
||
Line 392: | Line 2,898: | ||
# 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 []]) ;; |
# 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]</ |
- : int list = [1; 2; 3; 4; 5; 6; 7; 8]</syntaxhighlight> |
||
</div> |
|||
=={{header|Oforth}}== |
|||
<syntaxhighlight lang="oforth">[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] expand println</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[1, 2, 3, 4, 5, 6, 7, 8] |
|||
</pre> |
|||
=={{header|Ol}}== |
|||
<syntaxhighlight lang="scheme"> |
|||
(define (flatten x) |
|||
(cond |
|||
((null? x) |
|||
'()) |
|||
((not (pair? x)) |
|||
(list x)) |
|||
(else |
|||
(append (flatten (car x)) |
|||
(flatten (cdr x)))))) |
|||
(print |
|||
(flatten '((1) 2 ((3 4) 5) ((())) (((6))) 7 8 ()))) |
|||
</syntaxhighlight> |
|||
{{Out}} |
|||
<pre> |
|||
(1 2 3 4 5 6 7 8) |
|||
</pre> |
|||
=={{header|ooRexx}}== |
|||
<syntaxhighlight lang="oorexx"> |
|||
sub1 = .array~of(1) |
|||
sub2 = .array~of(3, 4) |
|||
sub3 = .array~of(sub2, 5) |
|||
sub4 = .array~of(.array~of(.array~new)) |
|||
sub5 = .array~of(.array~of(.array~of(6))) |
|||
sub6 = .array~new |
|||
-- final list construction |
|||
list = .array~of(sub1, 2, sub3, sub4, sub5, 7, 8, sub6) |
|||
-- flatten |
|||
flatlist = flattenList(list) |
|||
say "["flatlist~toString("line", ", ")"]" |
|||
::routine flattenList |
|||
use arg list |
|||
-- we could use a list or queue, but let's just use an array |
|||
accumulator = .array~new |
|||
-- now go to the recursive processing version |
|||
call flattenSublist list, accumulator |
|||
return accumulator |
|||
::routine flattenSublist |
|||
use arg list, accumulator |
|||
-- ask for the items explicitly, since this will allow |
|||
-- us to flatten indexed collections as well |
|||
do item over list~allItems |
|||
-- if the object is some sort of collection, flatten this out rather |
|||
-- than add to the accumulator |
|||
if item~isA(.collection) then call flattenSublist item, accumulator |
|||
else accumulator~append(item) |
|||
end |
|||
</syntaxhighlight> |
|||
=={{header|Oz}}== |
|||
Oz has a standard library function "Flatten": |
|||
<syntaxhighlight lang="oz">{Show {Flatten [[1] 2 [[3 4] 5] [[nil]] [[[6]]] 7 8 nil]}}</syntaxhighlight> |
|||
A simple, non-optimized implementation could look like this: |
|||
<syntaxhighlight lang="oz">fun {Flatten2 Xs} |
|||
case Xs of nil then nil |
|||
[] X|Xr then |
|||
{Append {Flatten2 X} {Flatten2 Xr}} |
|||
else [Xs] |
|||
end |
|||
end |
|||
</syntaxhighlight> |
|||
=={{header|PARI/GP}}== |
|||
<syntaxhighlight lang="parigp">flatten(v)={ |
|||
my(u=[]); |
|||
for(i=1,#v, |
|||
u=concat(u,if(type(v[i])=="t_VEC",flatten(v[i]),v[i])) |
|||
); |
|||
u |
|||
};</syntaxhighlight> |
|||
=={{header|PascalABC.NET}}== |
|||
<syntaxhighlight lang="delphi"> |
|||
function Flatten(lst: List<object>): List<object>; |
|||
begin |
|||
Result := new List<object>; |
|||
foreach var x in lst do |
|||
if x is List<object> then |
|||
Result.Addrange(Flatten(x as List<object>)) |
|||
else Result.Add(x) |
|||
end; |
|||
function LstObj(params a: array of object): List<Object> := new List<Object>(a); |
|||
begin |
|||
var lst := LstObj(1,LstObj(2, LstObj(3,4), LstObj(5,6)), LstObj(LstObj(7,8), 9)); |
|||
Println(lst); |
|||
Println(Flatten(lst)); |
|||
end. |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[1,[2,[3,4],[5,6]],[[7,8],9]] |
|||
[1,2,3,4,5,6,7,8,9] |
|||
</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
< |
<syntaxhighlight lang="perl">sub flatten { |
||
map { ref eq 'ARRAY' ? flatten(@$_) : $_ } @_ |
map { ref eq 'ARRAY' ? flatten(@$_) : $_ } @_ |
||
} |
} |
||
my @lst = ([1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []); |
my @lst = ([1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []); |
||
print flatten(@lst), "\n";</ |
print flatten(@lst), "\n";</syntaxhighlight> |
||
=={{header| |
=={{header|Phix}}== |
||
standard builtin |
|||
{{works with|Rakudo|#22 "Thousand Oaks"}} |
|||
<syntaxhighlight lang="phix">?flatten({{1},2,{{3,4},5},{{{}}},{{{6}}},7,8,{}})</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
{1,2,3,4,5,6,7,8} |
|||
</pre> |
|||
=={{header|Phixmonti}}== |
|||
<lang perl6>multi flatten (@a) { map { flatten $^x }, @a } |
|||
<syntaxhighlight lang="phixmonti">1 2 3 10 20 30 3 tolist 4 5 6 3 tolist 2 tolist 1000 "Hello" 6 tolist |
|||
multi flatten ($x) { $x }</lang> |
|||
dup print nl flatten print</syntaxhighlight> |
|||
With syntactic sugar |
|||
<syntaxhighlight lang="phixmonti">include ..\Utilitys.pmt |
|||
( 1 2 3 ( ( 10 20 30 ) ( 4 5 6 ) ) 1000 "Hola" ) |
|||
dup ? flatten ?</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[1, 2, 3, [[10, 20, 30], [4, 5, 6]], 1000, "Hello"] |
|||
[1, 2, 3, 10, 20, 30, 4, 5, 6, 1000, "Hello"] |
|||
</pre> |
|||
=={{header|PHP}}== |
=={{header|PHP}}== |
||
{{works with|PHP|4.x only, not 5.x}} |
|||
<lang php>/* Note: This code is only for PHP 4. |
|||
<syntaxhighlight 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(). */ |
It won't work on PHP 5 due to the change in behavior of array_merge(). */ |
||
while (array_filter($lst, 'is_array')) |
while (array_filter($lst, 'is_array')) |
||
$lst = call_user_func_array('array_merge', $lst);</ |
$lst = call_user_func_array('array_merge', $lst);</syntaxhighlight> |
||
Explanation: while <code>$lst</code> has any elements which are themselves arrays (i.e. <code>$lst</code> is not flat), we merge the elements all together (in PHP 4, <code>array_merge()</code> treated non-array arguments as if they were 1-element arrays; PHP 5 <code>array_merge()</code> no longer allows non-array arguments.), thus flattening the top level of any embedded arrays. Repeat this process until the array is flat. |
Explanation: while <code>$lst</code> has any elements which are themselves arrays (i.e. <code>$lst</code> is not flat), we merge the elements all together (in PHP 4, <code>array_merge()</code> treated non-array arguments as if they were 1-element arrays; PHP 5 <code>array_merge()</code> no longer allows non-array arguments.), thus flattening the top level of any embedded arrays. Repeat this process until the array is flat. |
||
===Recursive=== |
===Recursive=== |
||
< |
<syntaxhighlight lang="php"><?php |
||
function flatten($ary) { |
function flatten($ary) { |
||
$result = array(); |
$result = array(); |
||
Line 433: | Line 3,076: | ||
$lst = array(array(1), 2, array(array(3, 4), 5), array(array(array())), array(array(array(6))), 7, 8, array()); |
$lst = array(array(1), 2, array(array(3, 4), 5), array(array(array())), array(array(array(6))), 7, 8, array()); |
||
var_dump(flatten($lst)); |
var_dump(flatten($lst)); |
||
?></ |
?></syntaxhighlight> |
||
Alternatively:{{works with|PHP|5.3+}} |
|||
<syntaxhighlight lang="php"><?php |
|||
function flatten($ary) { |
|||
$result = array(); |
|||
array_walk_recursive($ary, function($x, $k) use (&$result) { $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)); |
|||
?></syntaxhighlight> |
|||
<syntaxhighlight lang="php"><?php |
|||
function flatten_helper($x, $k, $obj) { |
|||
$obj->flattened[] = $x; |
|||
} |
|||
function flatten($ary) { |
|||
$obj = (object)array('flattened' => array()); |
|||
array_walk_recursive($ary, 'flatten_helper', $obj); |
|||
return $obj->flattened; |
|||
} |
|||
$lst = array(array(1), 2, array(array(3, 4), 5), array(array(array())), array(array(array(6))), 7, 8, array()); |
|||
var_dump(flatten($lst)); |
|||
?></syntaxhighlight> |
|||
Using the standard library (warning: objects will also be flattened by this method): |
|||
<syntaxhighlight lang="php"><?php |
|||
$lst = array(array(1), 2, array(array(3, 4), 5), array(array(array())), array(array(array(6))), 7, 8, array()); |
|||
$result = iterator_to_array(new RecursiveIteratorIterator(new RecursiveArrayIterator($lst)), false); |
|||
var_dump($result); |
|||
?></syntaxhighlight> |
|||
===Non-recursive=== |
===Non-recursive=== |
||
Function flat is iterative and flattens the array in-place. |
Function flat is iterative and flattens the array in-place. |
||
< |
<syntaxhighlight lang="php"><?php |
||
function flat(&$ary) { // argument must be by reference or array will just be copied |
function flat(&$ary) { // argument must be by reference or array will just be copied |
||
for ($i = 0; $i < count($ary); $i++) { |
for ($i = 0; $i < count($ary); $i++) { |
||
Line 450: | Line 3,129: | ||
flat($lst); |
flat($lst); |
||
var_dump($lst); |
var_dump($lst); |
||
?></ |
?></syntaxhighlight> |
||
=={{header|PicoLisp}}== |
|||
<syntaxhighlight lang="picolisp">(de flatten (X) |
|||
(make # Build a list |
|||
(recur (X) # recursively over 'X' |
|||
(if (atom X) |
|||
(link X) # Put atoms into the result |
|||
(mapc recurse X) ) ) ) ) # or recurse on sub-lists</syntaxhighlight> |
|||
or a more succint way using [http://www.software-lab.de/doc/refF.html#fish fish]: |
|||
<syntaxhighlight lang="picolisp">(de flatten (X) |
|||
(fish atom X) )</syntaxhighlight> |
|||
=={{header|Pike}}== |
|||
There's a built-in function called <code>Array.flatten()</code> which does this, but here's a custom function: |
|||
<syntaxhighlight lang="pike">array flatten(array a) { |
|||
array r = ({ }); |
|||
foreach (a, mixed n) { |
|||
if (arrayp(n)) r += flatten(n); |
|||
else r += ({ n }); |
|||
} |
|||
return r; |
|||
}</syntaxhighlight> |
|||
=={{header|PL/I}}== |
|||
The Translate(text,that,this) intrinsic function returns ''text'' with any character in ''text'' that is found in ''this'' (say the third) replaced by the corresponding third character in ''that''. Suppose the availability of a function Replace(text,that,this) which returns ''text'' with all occurrences of ''this'' (a single text, possibly many characters) replaced by ''that'', possibly zero characters. The Translate function does not change the length of its string, simply translate its characters in place. |
|||
<syntaxhighlight lang="pl/i"> |
|||
list = translate (list, ' ', '[]' ); /*Produces " 1 , 2, 3,4 , 5 , , 6 , 7, 8, " */ |
|||
list = Replace(list,'',' '); /*Converts spaces to nothing. Same parameter order as Translate.*/ |
|||
do while index(list,',,') > 0; /*Is there a double comma anywhere? |
|||
list = Replace(list,',',',,'); /*Yes. Convert double commas to single, nullifying empty lists*/ |
|||
end; /*And search afresh, in case of multiple commas in a row.*/ |
|||
list = '[' || list || ']'; /*Repackage the list.*/ |
|||
</syntaxhighlight> |
|||
This is distinctly crude. A user-written Replace function is confronted by the requirement to specify a maximum size for its returned result, for instance <code>Replace:Procedure(text,that,this) Returns(Character 200 Varying);</code> which is troublesome for general use. The intrinsic function Translate has no such restriction. |
|||
An alternative would be to translate the commas into spaces also (thereby the null entry vanishes) then scan along the result. |
|||
=={{header|PostScript}}== |
|||
{{libheader|initlib}} |
|||
<syntaxhighlight lang="postscript"> |
|||
/flatten { |
|||
/.f {{type /arraytype eq} {{.f} map aload pop} ift}. |
|||
[exch .f] |
|||
}. |
|||
</syntaxhighlight> |
|||
<syntaxhighlight lang="text"> |
|||
[[1] 2 [[3 4] 5] [[[]]] [[[6]]] 7 8 []] flatten |
|||
</syntaxhighlight> |
|||
=={{header|PowerShell}}== |
|||
<syntaxhighlight lang="powershell"> |
|||
function flatten($a) { |
|||
if($a.Count -gt 1) { |
|||
$a | foreach{ $(flatten $_)} |
|||
} else {$a} |
|||
} |
|||
$a = @(@(1), 2, @(@(3,4), 5), @(@(@())), @(@(@(6))), 7, 8, @()) |
|||
"$(flatten $a)" |
|||
</syntaxhighlight> |
|||
<b>Output:</b> |
|||
<pre> |
|||
1 2 3 4 5 6 7 8 |
|||
</pre> |
|||
=={{header|Prolog}}== |
|||
<syntaxhighlight lang="prolog"> |
|||
flatten(List, FlatList) :- |
|||
flatten(List, [], FlatList). |
|||
flatten(Var, T, [Var|T]) :- |
|||
var(Var), !. |
|||
flatten([], T, T) :- !. |
|||
flatten([H|T], TailList, List) :- !, |
|||
flatten(H, FlatTail, List), |
|||
flatten(T, TailList, FlatTail). |
|||
flatten(NonList, T, [NonList|T]). |
|||
</syntaxhighlight> |
|||
=={{header|Python}}== |
=={{header|Python}}== |
||
===Recursive=== |
===Recursive=== |
||
<syntaxhighlight lang="python">>>> def flatten(lst): |
|||
return sum( ([x] if not isinstance(x, list) else flatten(x) |
|||
Function <code>flatten</code> 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), [] ) |
for x in lst), [] ) |
||
>>> lst = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] |
>>> lst = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] |
||
>>> flatten(lst) |
>>> flatten(lst) |
||
[1, 2, 3, 4, 5, 6, 7, 8]</ |
[1, 2, 3, 4, 5, 6, 7, 8]</syntaxhighlight> |
||
===Non-recursive=== |
|||
===Recursive, generative and working with any type of iterable object=== |
|||
<syntaxhighlight lang="python">>>> def flatten(itr): |
|||
>>> for x in itr: |
|||
>>> try: |
|||
>>> yield from flatten(x) |
|||
>>> except: |
|||
>>> yield x |
|||
>>> lst = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] |
|||
>>> list(flatten(lst)) |
|||
[1, 2, 3, 4, 5, 6, 7, 8] |
|||
>>> tuple(flatten(lst)) |
|||
(1, 2, 3, 4, 5, 6, 7, 8) |
|||
>>>for i in flatten(lst): |
|||
>>> print(i) |
|||
1 |
|||
2 |
|||
3 |
|||
4 |
|||
5 |
|||
6 |
|||
7 |
|||
8</syntaxhighlight> |
|||
===Non-recursive=== |
|||
Function flat is iterative and flattens the list in-place. It follows the Python idiom of returning None when acting in-place: |
Function flat is iterative and flattens the list in-place. It follows the Python idiom of returning None when acting in-place: |
||
< |
<syntaxhighlight lang="python">>>> def flat(lst): |
||
i=0 |
i=0 |
||
while i<len(lst): |
while i<len(lst): |
||
Line 479: | Line 3,265: | ||
>>> flat(lst) |
>>> flat(lst) |
||
>>> lst |
>>> lst |
||
[1, 2, 3, 4, 5, 6, 7, 8]</ |
[1, 2, 3, 4, 5, 6, 7, 8]</syntaxhighlight> |
||
===Generative=== |
|||
This method shows a solution using Python generators. |
|||
<code>flatten</code> is a generator that yields the non-list values of its input in order. |
|||
In this case, the generator is converted back to a list before printing. |
|||
<syntaxhighlight lang="python">>>> def flatten(lst): |
|||
for x in lst: |
|||
if isinstance(x, list): |
|||
for x in flatten(x): |
|||
yield x |
|||
else: |
|||
yield x |
|||
>>> lst = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] |
|||
>>> print list(flatten(lst)) |
|||
[1, 2, 3, 4, 5, 6, 7, 8]</syntaxhighlight> |
|||
===Functional Recursive=== |
|||
And, as [[Rosetta_Code|the idea of Rosetta Code]] is to demonstrate how languages are '''similar''' as well as different, and to thus to 'aid a person with a grounding in one approach to a problem in learning another', here it is in terms of '''concatMap''', which can be defined in any language, including mathematics, and which can be variously expressed in Python. (The fastest Python implementation of the '''concat''' component of the (concat . map) composition seems to be in terms of ''itertools.chain''). |
|||
{{Works with|Python|3.7}} |
|||
<syntaxhighlight lang="python">'''Flatten a nested list''' |
|||
from itertools import (chain) |
|||
# ----------------------- FLATTEN ------------------------ |
|||
# flatten :: NestedList a -> [a] |
|||
def flatten(x): |
|||
'''A list of atomic values resulting from fully |
|||
flattening an arbitrarily nested list. |
|||
''' |
|||
return concatMap(flatten)(x) if ( |
|||
isinstance(x, list) |
|||
) else [x] |
|||
# ------------------------- TEST ------------------------- |
|||
def main(): |
|||
'''Test: flatten an arbitrarily nested list. |
|||
''' |
|||
print( |
|||
fTable(__doc__ + ':')(showList)(showList)( |
|||
flatten |
|||
)([ |
|||
[[[]]], |
|||
[[1, 2, 3]], |
|||
[[1], [[2]], [[[3, 4]]]], |
|||
[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] |
|||
]) |
|||
) |
|||
# ----------------------- GENERIC ------------------------ |
|||
# compose (<<<) :: (b -> c) -> (a -> b) -> a -> c |
|||
def compose(g): |
|||
'''Right to left function composition.''' |
|||
return lambda f: lambda x: g(f(x)) |
|||
# concatMap :: (a -> [b]) -> [a] -> [b] |
|||
def concatMap(f): |
|||
'''A concatenated list over which a function has been mapped. |
|||
The list monad can be derived by using a function f which |
|||
wraps its output in a list, |
|||
(using an empty list to represent computational failure). |
|||
''' |
|||
def go(xs): |
|||
return chain.from_iterable(map(f, xs)) |
|||
return go |
|||
# fTable :: String -> (a -> String) -> |
|||
# (b -> String) -> |
|||
# (a -> b) -> [a] -> String |
|||
def fTable(s): |
|||
'''Heading -> x display function -> |
|||
fx display function -> |
|||
f -> value list -> tabular string.''' |
|||
def go(xShow, fxShow, f, xs): |
|||
w = max(map(compose(len)(xShow), xs)) |
|||
return s + '\n' + '\n'.join([ |
|||
xShow(x).rjust(w, ' ') + (' -> ') + fxShow(f(x)) |
|||
for x in xs |
|||
]) |
|||
return lambda xShow: lambda fxShow: lambda f: lambda xs: go( |
|||
xShow, fxShow, f, xs |
|||
) |
|||
# showList :: [a] -> String |
|||
def showList(xs): |
|||
'''Stringification of a list.''' |
|||
return '[' + ','.join(str(x) for x in xs) + ']' |
|||
if __name__ == '__main__': |
|||
main()</syntaxhighlight> |
|||
{{Out}} |
|||
<pre>Flatten a nested list: |
|||
[[[]]] -> [] |
|||
[[1, 2, 3]] -> [1,2,3] |
|||
[[1],[[2]],[[[3, 4]]]] -> [1,2,3,4] |
|||
[[1],2,[[3, 4], 5],[[[]]],[[[6]]],7,8,[]] -> [1,2,3,4,5,6,7,8]</pre> |
|||
===Functional Non-recursive=== |
|||
And, in contexts where it may be desirable to avoid not just recursion, but also: |
|||
# mutation of the original list, and |
|||
# dependence on error-events for evaluation control, |
|||
we can again use the universal '''concat . map''' composition (see the second recursive example above) by embedding it in a fold / reduction, and using it with a pure, but iteratively-implemented, '''until''' function. |
|||
( Note that the generic functions in the following example are ''curried'', enabling not only more flexible composition, but also some simplifying reductions – here eliminating the need for two uses of Python's ''lambda'' keyword ): |
|||
{{Works with|Python|3.7}} |
|||
<syntaxhighlight lang="python">'''Flatten a list''' |
|||
from functools import (reduce) |
|||
from itertools import (chain) |
|||
def flatten(xs): |
|||
'''A flat list of atomic values derived |
|||
from a nested list. |
|||
''' |
|||
return reduce( |
|||
lambda a, x: a + list(until(every(notList))( |
|||
concatMap(pureList) |
|||
)([x])), |
|||
xs, [] |
|||
) |
|||
# TEST ---------------------------------------------------- |
|||
def main(): |
|||
'''From nested list to flattened list''' |
|||
print(main.__doc__ + ':\n\n') |
|||
xs = [[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] |
|||
print( |
|||
repr(xs) + ' -> ' + repr(flatten(xs)) |
|||
) |
|||
# GENERIC ------------------------------------------------- |
|||
# concatMap :: (a -> [b]) -> [a] -> [b] |
|||
def concatMap(f): |
|||
'''A concatenated list over which a function has been mapped. |
|||
The list monad can be derived by using a function f which |
|||
wraps its output in a list, |
|||
(using an empty list to represent computational failure). |
|||
''' |
|||
return lambda xs: list( |
|||
chain.from_iterable(map(f, xs)) |
|||
) |
|||
# every :: (a -> Bool) -> [a] -> Bool |
|||
def every(p): |
|||
'''True if p(x) holds for every x in xs''' |
|||
def go(p, xs): |
|||
return all(map(p, xs)) |
|||
return lambda xs: go(p, xs) |
|||
# notList :: a -> Bool |
|||
def notList(x): |
|||
'''True if the value x is not a list.''' |
|||
return not isinstance(x, list) |
|||
# pureList :: a -> [b] |
|||
def pureList(x): |
|||
'''x if x is a list, othewise [x]''' |
|||
return x if isinstance(x, list) else [x] |
|||
# until :: (a -> Bool) -> (a -> a) -> a -> a |
|||
def until(p): |
|||
'''The result of repeatedly applying f until p holds. |
|||
The initial seed value is x.''' |
|||
def go(f, x): |
|||
v = x |
|||
while not p(v): |
|||
v = f(v) |
|||
return v |
|||
return lambda f: lambda x: go(f, x) |
|||
if __name__ == '__main__': |
|||
main()</syntaxhighlight> |
|||
{{Out}} |
|||
<pre>From nested list to flattened list: |
|||
[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] -> [1, 2, 3, 4, 5, 6, 7, 8]</pre> |
|||
=={{header|Q}}== |
|||
{{trans|K}} |
|||
We repeatedly apply <tt>raze</tt> until the return value converges to a fixed value. |
|||
<syntaxhighlight lang="q">(raze/) ((1); 2; ((3;4); 5); ((())); (((6))); 7; 8; ())</syntaxhighlight> |
|||
=={{header|Quackery}}== |
|||
<syntaxhighlight lang="quackery">forward is flatten |
|||
[ [] swap |
|||
witheach |
|||
[ dup nest? |
|||
if flatten |
|||
join ] ] resolves flatten ( [ --> [ )</syntaxhighlight> |
|||
'''Output:''' |
|||
<syntaxhighlight lang="quackery">/O> ' [ [ 1 ] 2 [ [ 3 4 ] 5 ] [ [ [ ] ] ] [ [ [ 6 ] ] ] 7 8 [ ] ] flatten |
|||
... |
|||
Stack: [ 1 2 3 4 5 6 7 8 ]</syntaxhighlight> |
|||
=={{header|R}}== |
=={{header|R}}== |
||
< |
<syntaxhighlight lang="r">x <- list(list(1), 2, list(list(3, 4), 5), list(list(list())), list(list(list(6))), 7, 8, list()) |
||
unlist(l)</lang> |
|||
unlist(x)</syntaxhighlight> |
|||
=={{header|Racket}}== |
|||
Racket has a built-in flatten function: |
|||
<syntaxhighlight lang="racket"> |
|||
#lang racket |
|||
(flatten '(1 (2 (3 4 5) (6 7)) 8 9)) |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
'(1 2 3 4 5 6 7 8 9) |
|||
</pre> |
|||
or, writing it explicitly with the same result: |
|||
<syntaxhighlight lang="racket"> |
|||
#lang racket |
|||
(define (flatten l) |
|||
(cond [(empty? l) null] |
|||
[(not (list? l)) (list l)] |
|||
[else (append (flatten (first l)) (flatten (rest l)))])) |
|||
(flatten '(1 (2 (3 4 5) (6 7)) 8 9)) |
|||
</syntaxhighlight> |
|||
=={{header|Raku}}== |
|||
(formerly Perl 6) |
|||
{{works with|Rakudo Star|2018.03}} |
|||
<syntaxhighlight lang="raku" line>my @l = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]; |
|||
say .perl given gather @l.deepmap(*.take); # lazy recursive version |
|||
# Another way to do it is with a recursive function (here actually a Block calling itself with the &?BLOCK dynamic variable): |
|||
say { |(@$_ > 1 ?? map(&?BLOCK, @$_) !! $_) }(@l)</syntaxhighlight> |
|||
=={{header|REBOL}}== |
|||
<syntaxhighlight lang="rebol"> |
|||
flatten: func [ |
|||
"Flatten the block in place." |
|||
block [any-block!] |
|||
][ |
|||
parse block [ |
|||
any [block: any-block! (change/part block first block 1) :block | skip] |
|||
] |
|||
head block |
|||
] |
|||
</syntaxhighlight> |
|||
Sample: <pre> |
|||
>> flatten [[1] 2 [[3 4] 5] [[[]]] [[[6]]] 7 8 []] |
|||
== [1 2 3 4 5 6 7 8] |
|||
</pre> |
|||
=={{header|Red}}== |
|||
<syntaxhighlight lang="red"> |
|||
flatten: function [ |
|||
"Flatten the block" |
|||
block [any-block!] |
|||
][ |
|||
load form block |
|||
] |
|||
red>> flatten [[1] 2 [[3 4] 5] [[[]]] [[[6]]] 7 8 []] |
|||
== [1 2 3 4 5 6 7 8] |
|||
;flatten a list to a string |
|||
>> blk: [1 2 ["test"] "a" [["bb"]] 3 4 [[[99]]]] |
|||
>> form blk |
|||
== "1 2 test a bb 3 4 99"</syntaxhighlight> |
|||
=={{header|Refal}}== |
|||
<syntaxhighlight lang="refal">$ENTRY Go { |
|||
, ((1) 2 ((3 4) 5) ((())) (((6))) 7 8 ()): e.List |
|||
= <Prout e.List ' -> ' <Flatten e.List>> |
|||
}; |
|||
Flatten { |
|||
= ; |
|||
s.I e.X = s.I <Flatten e.X>; |
|||
(e.X) e.Y = <Flatten e.X> <Flatten e.Y>; |
|||
};</syntaxhighlight> |
|||
{{out}} |
|||
<pre>((1 )2 ((3 4 )5 )((()))(((6 )))7 8 ()) -> 1 2 3 4 5 6 7 8</pre> |
|||
=={{header|REXX}}== |
|||
{{trans|PL/I}} |
|||
<syntaxhighlight lang="rexx">/*REXX program (translated from PL/I) flattens a list (the data need not be numeric).*/ |
|||
list= '[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]' /*the list to be flattened. */ |
|||
say list /*display the original list. */ |
|||
c= ',' /*define a literal (1 comma). */ |
|||
cc= ',,' /* " " " (2 commas).*/ |
|||
list= translate(list, , "[]") /*translate brackets to blanks.*/ |
|||
list= space(list, 0) /*Converts spaces to nulls. */ |
|||
do while index(list, cc) > 0 /*any double commas ? */ |
|||
list= changestr(cc, list, c) /*convert ,, to single comma.*/ |
|||
end /*while*/ |
|||
list= strip(list, 'T', c) /*strip the last trailing comma*/ |
|||
list = '['list"]" /*repackage the list. */ |
|||
say list /*display the flattened list. */</syntaxhighlight> |
|||
{{out|output|:}} |
|||
<pre> |
|||
[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] |
|||
[1,2,3,4,5,6,7,8] |
|||
</pre> |
|||
=={{header|Ring}}== |
|||
<syntaxhighlight lang="ring"> |
|||
aString = "[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]" |
|||
bString = "" |
|||
cString = "" |
|||
for n=1 to len(aString) |
|||
if ascii(aString[n]) >= 48 and ascii(aString[n]) <= 57 |
|||
bString = bString + ", " + aString[n] |
|||
ok |
|||
next |
|||
cString = substr(bString,3,Len(bString)-2) |
|||
cString = '"' + cString + '"' |
|||
see cString + nl |
|||
</syntaxhighlight> |
|||
<pre> |
|||
"1, 2, 3, 4, 5, 6, 7, 8" |
|||
</pre> |
|||
=={{header|RPL}}== |
|||
Soberly recursive. |
|||
{{works with|Halcyon Calc|4.2.7}} |
|||
≪ '''IF''' DUP SIZE '''THEN''' |
|||
{ } 1 LAST '''FOR''' j |
|||
OVER j GET |
|||
'''IF''' DUP TYPE 5 == '''THEN FLATL END''' |
|||
+ '''NEXT''' |
|||
SWAP DROP '''END''' |
|||
≫ ‘'''FLATL'''’ STO |
|||
{{1} 2 {{3 4} 5} {{{}}} {{{6}}} 7 8 {}} '''FLATL''' |
|||
{{out}} |
|||
<pre> |
|||
1: { 1 2 3 4 5 6 7 8 } |
|||
</pre> |
|||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
<code>flatten</code> is a built-in method of Arrays |
<code>flatten</code> is a built-in method of Arrays |
||
< |
<syntaxhighlight lang="ruby">flat = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []].flatten |
||
p flat # => [1, 2, 3, 4, 5, 6, 7, 8]</ |
p flat # => [1, 2, 3, 4, 5, 6, 7, 8]</syntaxhighlight> |
||
The <code>flatten</code> method takes an optional argument, which dedicates the amount of levels to be flattened. |
|||
<syntaxhighlight lang="ruby">p flatten_once = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []].flatten(1) |
|||
# => [1, 2, [3, 4], 5, [[]], [[6]], 7, 8] |
|||
</syntaxhighlight> |
|||
=={{header|Rust}}== |
|||
First we have to create a type that supports arbitrary nesting: |
|||
<syntaxhighlight lang="rust">use std::{vec, mem, iter}; |
|||
enum List<T> { |
|||
Node(Vec<List<T>>), |
|||
Leaf(T), |
|||
} |
|||
impl<T> IntoIterator for List<T> { |
|||
type Item = List<T>; |
|||
type IntoIter = ListIter<T>; |
|||
fn into_iter(self) -> Self::IntoIter { |
|||
match self { |
|||
List::Node(vec) => ListIter::NodeIter(vec.into_iter()), |
|||
leaf @ List::Leaf(_) => ListIter::LeafIter(iter::once(leaf)), |
|||
} |
|||
} |
|||
} |
|||
enum ListIter<T> { |
|||
NodeIter(vec::IntoIter<List<T>>), |
|||
LeafIter(iter::Once<List<T>>), |
|||
} |
|||
impl<T> ListIter<T> { |
|||
fn flatten(self) -> Flatten<T> { |
|||
Flatten { |
|||
stack: Vec::new(), |
|||
curr: self, |
|||
} |
|||
} |
|||
} |
|||
impl<T> Iterator for ListIter<T> { |
|||
type Item = List<T>; |
|||
fn next(&mut self) -> Option<Self::Item> { |
|||
match *self { |
|||
ListIter::NodeIter(ref mut v_iter) => v_iter.next(), |
|||
ListIter::LeafIter(ref mut o_iter) => o_iter.next(), |
|||
} |
|||
} |
|||
} |
|||
struct Flatten<T> { |
|||
stack: Vec<ListIter<T>>, |
|||
curr: ListIter<T>, |
|||
} |
|||
// Flatten code is a little messy since we are shoehorning recursion into an Iterator |
|||
impl<T> Iterator for Flatten<T> { |
|||
type Item = T; |
|||
fn next(&mut self) -> Option<Self::Item> { |
|||
loop { |
|||
match self.curr.next() { |
|||
Some(list) => { |
|||
match list { |
|||
node @ List::Node(_) => { |
|||
self.stack.push(node.into_iter()); |
|||
let len = self.stack.len(); |
|||
mem::swap(&mut self.stack[len - 1], &mut self.curr); |
|||
} |
|||
List::Leaf(item) => return Some(item), |
|||
} |
|||
} |
|||
None => { |
|||
if let Some(next) = self.stack.pop() { |
|||
self.curr = next; |
|||
} else { |
|||
return None; |
|||
} |
|||
} |
|||
} |
|||
} |
|||
} |
|||
} |
|||
use List::*; |
|||
fn main() { |
|||
let list = Node(vec![Node(vec![Leaf(1)]), |
|||
Leaf(2), |
|||
Node(vec![Node(vec![Leaf(3), Leaf(4)]), Leaf(5)]), |
|||
Node(vec![Node(vec![Node(vec![])])]), |
|||
Node(vec![Node(vec![Node(vec![Leaf(6)])])]), |
|||
Leaf(7), |
|||
Leaf(8), |
|||
Node(vec![])]); |
|||
for elem in list.into_iter().flatten() { |
|||
print!("{} ", elem); |
|||
} |
|||
println!(); |
|||
}</syntaxhighlight> |
|||
{{output}} |
|||
<pre>1 2 3 4 5 6 7 8 |
|||
</pre> |
|||
=={{header|S-lang}}== |
|||
<syntaxhighlight lang="s-lang">define flatten (); |
|||
define flatten (list) { |
|||
variable item, |
|||
retval, |
|||
val; |
|||
if (typeof(list) != List_Type) { |
|||
retval = list; |
|||
} else { |
|||
retval = {}; |
|||
foreach item (list) { |
|||
foreach val (flatten(item)) { |
|||
list_append(retval, val); |
|||
} |
|||
} |
|||
} |
|||
return retval; |
|||
}</syntaxhighlight> |
|||
Sample: |
|||
<pre> |
|||
slsh> variable data = {{1}, 2, {{3,4}, 5}, {{{}}}, {{{6}}}, 7, 8, {}}, |
|||
result = flatten(data); |
|||
slsh> print(result); |
|||
{ |
|||
1 |
|||
2 |
|||
3 |
|||
4 |
|||
5 |
|||
6 |
|||
7 |
|||
8 |
|||
} |
|||
</pre> |
|||
=={{header|Scala}}== |
|||
<syntaxhighlight lang="scala">def flatList(l: List[_]): List[Any] = l match { |
|||
case Nil => Nil |
|||
case (head: List[_]) :: tail => flatList(head) ::: flatList(tail) |
|||
case head :: tail => head :: flatList(tail) |
|||
}</syntaxhighlight> |
|||
Sample: |
|||
<pre> |
|||
scala> List(List(1), 2, List(List(3, 4), 5), List(List(List())), List(List(List(6))), 7, 8, List()) |
|||
res10: List[Any] = List(List(1), 2, List(List(3, 4), 5), List(List(List())), List(List(List(6))), 7, 8, List()) |
|||
scala> flatList(res10) |
|||
res12: List[Any] = List(1, 2, 3, 4, 5, 6, 7, 8) |
|||
</pre> |
|||
=={{header|Scheme}}== |
=={{header|Scheme}}== |
||
< |
<syntaxhighlight lang="scheme">> (define (flatten x) |
||
(cond ((null? x) '()) |
(cond ((null? x) '()) |
||
((not (pair? x)) (list x)) |
((not (pair? x)) (list x)) |
||
Line 498: | Line 3,805: | ||
> (flatten '((1) 2 ((3 4) 5) ((())) (((6))) 7 8 ())) |
> (flatten '((1) 2 ((3 4) 5) ((())) (((6))) 7 8 ())) |
||
(1 2 3 4 5 6 7 8)</ |
(1 2 3 4 5 6 7 8)</syntaxhighlight> |
||
=={{header|Shen}}== |
|||
<syntaxhighlight lang="shen"> |
|||
(define flatten |
|||
[] -> [] |
|||
[X|Y] -> (append (flatten X) (flatten Y)) |
|||
X -> [X]) |
|||
(flatten [[1] 2 [[3 4] 5] [[[]]] [[[6]]] 7 8 []]) |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[1 2 3 4 5 6 7 8] |
|||
</pre> |
|||
=={{header|Sidef}}== |
|||
<syntaxhighlight lang="ruby">func flatten(a) { |
|||
var flat = [] |
|||
a.each { |item| |
|||
flat += (item.kind_of(Array) ? flatten(item) : [item]) |
|||
} |
|||
return flat |
|||
} |
|||
var arr = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] |
|||
say flatten(arr) # used-defined function |
|||
say arr.flatten # built-in Array method</syntaxhighlight> |
|||
=={{header|Slate}}== |
=={{header|Slate}}== |
||
< |
<syntaxhighlight lang="slate">s@(Sequence traits) flatten |
||
[ |
[ |
||
[| :out | s flattenOn: out] writingAs: s |
[| :out | s flattenOn: out] writingAs: s |
||
Line 512: | Line 3,846: | ||
ifTrue: [value flattenOn: w] |
ifTrue: [value flattenOn: w] |
||
ifFalse: [w nextPut: value]]. |
ifFalse: [w nextPut: value]]. |
||
].</ |
].</syntaxhighlight> |
||
=={{header|Smalltalk}}== |
=={{header|Smalltalk}}== |
||
{{works with|GNU Smalltalk}} |
{{works with|GNU Smalltalk}} |
||
< |
<syntaxhighlight lang="smalltalk">OrderedCollection extend [ |
||
flatten [ |f| |
flatten [ |f| |
||
f := OrderedCollection new. |
f := OrderedCollection new. |
||
Line 538: | Line 3,872: | ||
{{{}}} . {{{6}}} . 7 . 8 . {} }. |
{{{}}} . {{{6}}} . 7 . 8 . {} }. |
||
(list flatten) printNl.</ |
(list flatten) printNl.</syntaxhighlight> |
||
Here is a non-OOP (but functional) version, which uses a block-closure as function (showing higher order features of Smalltalk): |
|||
<syntaxhighlight lang="smalltalk"> |
|||
flatDo := |
|||
[:element :action | |
|||
element isCollection ifTrue:[ |
|||
element do:[:el | flatDo value:el value:action] |
|||
] ifFalse:[ |
|||
action value:element |
|||
]. |
|||
]. |
|||
collection := { |
|||
{1} . 2 . { {3 . 4} . 5 } . |
|||
{{{}}} . {{{6}}} . 7 . 8 . {} |
|||
}. |
|||
newColl := OrderedCollection new. |
|||
flatDo |
|||
value:collection |
|||
value:[:el | newColl add: el]</syntaxhighlight> |
|||
of course, many Smalltalk libraries already provide such functionality. |
|||
{{works with|Smalltalk/X}} {{works with|Pharo}} |
|||
<syntaxhighlight lang="smalltalk">collection flatDo:[:el | newColl add:el]</syntaxhighlight> |
|||
=={{header|Standard ML}}== |
|||
In Standard ML, list must be homogeneous, but nested lists can be implemented as a tree-like data structure using a <code>datatype</code> statement: |
|||
<syntaxhighlight lang="sml">datatype 'a nestedList = |
|||
L of 'a (* leaf *) |
|||
| N of 'a nestedList list (* node *) |
|||
</syntaxhighlight> |
|||
Flattening of this structure is similar to flatten trees: |
|||
<syntaxhighlight lang="sml">fun flatten (L x) = [x] |
|||
| flatten (N xs) = List.concat (map flatten xs)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
- flatten (N [ L 1, N [L 2, N []], L 3]); |
|||
val it = [1,2,3] : int list |
|||
</pre> |
|||
=={{header|Suneido}}== |
|||
<syntaxhighlight lang="suneido">ob = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] |
|||
ob.Flatten()</syntaxhighlight> |
|||
{{out}} |
|||
<pre>#(1, 2, 3, 4, 5, 6, 7, 8)</pre> |
|||
=={{header|SuperCollider}}== |
|||
SuperCollider has the method "flat", which completely flattens nested lists, and the method "flatten(n)" to flatten a certain number of levels. |
|||
<syntaxhighlight lang="supercollider"> |
|||
a = [[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]; |
|||
a.flatten(1); // answers [ 1, 2, [ 3, 4 ], 5, [ [ ] ], [ [ 6 ] ], 7, 8 ] |
|||
a.flat; // answers [ 1, 2, 3, 4, 5, 6, 7, 8 ] |
|||
</syntaxhighlight> |
|||
Written as a function: |
|||
<syntaxhighlight lang="supercollider"> |
|||
( |
|||
f = { |x| |
|||
var res = res ?? List.new; |
|||
if(x.isSequenceableCollection) { |
|||
x.do { |each| |
|||
res.addAll(f.(each)) |
|||
} |
|||
} { |
|||
res.add(x); |
|||
}; |
|||
res |
|||
}; |
|||
f.([[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]); |
|||
)</syntaxhighlight> |
|||
=={{header|Swift}}== |
|||
=== Recursive === |
|||
<syntaxhighlight lang="swift">func list(s: Any...) -> [Any] { |
|||
return s |
|||
} |
|||
func flatten<T>(s: [Any]) -> [T] { |
|||
var r = [T]() |
|||
for e in s { |
|||
switch e { |
|||
case let a as [Any]: |
|||
r += flatten(a) |
|||
case let x as T: |
|||
r.append(x) |
|||
default: |
|||
assert(false, "value of wrong type") |
|||
} |
|||
} |
|||
return r |
|||
} |
|||
let s = list(list(1), |
|||
2, |
|||
list(list(3, 4), 5), |
|||
list(list(list())), |
|||
list(list(list(6))), |
|||
7, |
|||
8, |
|||
list() |
|||
) |
|||
println(s) |
|||
let result : [Int] = flatten(s) |
|||
println(result)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[[1] 2 [[3 4] 5] [[[]]] [[[6]]] 7 8 []] |
|||
[1 2 3 4 5 6 7 8] |
|||
</pre> |
|||
More functionally: |
|||
{{works with|Swift|1.2+}} |
|||
<syntaxhighlight lang="swift">func list(s: Any...) -> [Any] { |
|||
return s |
|||
} |
|||
func flatten<T>(s: [Any]) -> [T] { |
|||
return s.flatMap { |
|||
switch $0 { |
|||
case let a as [Any]: |
|||
return flatten(a) |
|||
case let x as T: |
|||
return [x] |
|||
default: |
|||
assert(false, "value of wrong type") |
|||
} |
|||
} |
|||
} |
|||
let s = list(list(1), |
|||
2, |
|||
list(list(3, 4), 5), |
|||
list(list(list())), |
|||
list(list(list(6))), |
|||
7, |
|||
8, |
|||
list() |
|||
) |
|||
println(s) |
|||
let result : [Int] = flatten(s) |
|||
println(result)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[[1] 2 [[3 4] 5] [[[]]] [[[6]]] 7 8 []] |
|||
[1 2 3 4 5 6 7 8] |
|||
</pre> |
|||
=== Non-recursive === |
|||
{{works with|Swift|2.0+}} |
|||
<syntaxhighlight lang="swift">func list(s: Any...) -> [Any] |
|||
{ |
|||
return s |
|||
} |
|||
func flatten<T>(array: [Any]) -> [T] |
|||
{ |
|||
var result: [T] = [] |
|||
var workstack: [(array: [Any], lastIndex: Int)] = [(array, 0)] |
|||
workstackLoop: while !workstack.isEmpty |
|||
{ |
|||
for element in workstack.last!.array.suffixFrom(workstack.last!.lastIndex) |
|||
{ |
|||
workstack[workstack.endIndex - 1].lastIndex++ |
|||
if let element = element as? [Any] |
|||
{ |
|||
workstack.append((element, 0)) |
|||
continue workstackLoop |
|||
} |
|||
result.append(element as! T) |
|||
} |
|||
workstack.removeLast() |
|||
} |
|||
return result |
|||
} |
|||
let input = list(list(1), |
|||
2, |
|||
list(list(3, 4), 5), |
|||
list(list(list())), |
|||
list(list(list(6))), |
|||
7, |
|||
8, |
|||
list() |
|||
) |
|||
print(input) |
|||
let result: [Int] = flatten(input) |
|||
print(result)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] |
|||
[1, 2, 3, 4, 5, 6, 7, 8] |
|||
</pre> |
|||
=={{header|Tailspin}}== |
|||
<syntaxhighlight lang="tailspin"> |
|||
templates flatten |
|||
[ $ -> # ] ! |
|||
when <[]> do |
|||
$... -> # |
|||
otherwise |
|||
$ ! |
|||
end flatten |
|||
[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] -> flatten -> !OUT::write |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[1, 2, 3, 4, 5, 6, 7, 8] |
|||
</pre> |
|||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
< |
<syntaxhighlight lang="tcl">proc flatten list { |
||
for {set old {}} {$old ne $list} {} { |
for {set old {}} {$old ne $list} {} { |
||
set old $list |
set old $list |
||
Line 550: | Line 4,106: | ||
puts [flatten {{1} 2 {{3 4} 5} {{{}}} {{{6}}} 7 8 {}}] |
puts [flatten {{1} 2 {{3 4} 5} {{{}}} {{{6}}} 7 8 {}}] |
||
# ===> 1 2 3 4 5 6 7 8</ |
# ===> 1 2 3 4 5 6 7 8</syntaxhighlight> |
||
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 <code>lindex</code>, iterated over with <code>foreach</code>, etc.) |
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 <code>lindex</code>, iterated over with <code>foreach</code>, etc.) |
||
Another implementation that's slightly more terse: |
|||
=={{header|TI-89 BASIC}}== |
|||
<syntaxhighlight lang="tcl">proc flatten {data} { |
|||
There is no nesting of lists or other data structures in TI-89 BASIC, short of using variable names as pointers. |
|||
while { $data != [set data [join $data]] } { } |
|||
return $data |
|||
} |
|||
puts [flatten {{1} 2 {{3 4} 5} {{{}}} {{{6}}} 7 8 {}}] |
|||
# ===> 1 2 3 4 5 6 7 8</syntaxhighlight> |
|||
=={{header|Trith}}== |
|||
<syntaxhighlight lang="trith">[[1] 2 [[3 4] 5] [[[]]] [[[6]]] 7 8 []] flatten</syntaxhighlight> |
|||
{{omit from|UNIX Shell}} |
|||
=={{header|TXR}}== |
|||
An important builtin. |
|||
<syntaxhighlight lang="txr">@(bind foo ((1) 2 ((3 4) 5) ((())) (((6))) 7 8 ())) |
|||
@(bind bar foo) |
|||
@(flatten bar)</syntaxhighlight> |
|||
Run: |
|||
<pre>$ txr -a 5 flatten.txr # show variable bindings in array notation to depth 5 |
|||
foo[0][0]="1" |
|||
foo[1]="2" |
|||
foo[2][0][0]="3" |
|||
foo[2][0][1]="4" |
|||
foo[2][1]="5" |
|||
foo[4][0][0][0]="6" |
|||
foo[5]="7" |
|||
foo[6]="8" |
|||
bar[0]="1" |
|||
bar[1]="2" |
|||
bar[2]="3" |
|||
bar[3]="4" |
|||
bar[4]="5" |
|||
bar[5]="6" |
|||
bar[6]="7" |
|||
bar[7]="8"</pre> |
|||
=={{header|Uiua}}== |
|||
Keep joining elements until we're done. |
|||
<syntaxhighlight lang="Uiua"> |
|||
⍥/◇⊂∞{{1} 2 {{3 4} 5} {{{}}} {{{6}}} 7 8 {}} |
|||
</syntaxhighlight> |
|||
=={{header|VBScript}}== |
|||
Working on embedded arrays as that's about the closest we get to lists. |
|||
=====Implementation===== |
|||
<syntaxhighlight lang="vb"> |
|||
class flattener |
|||
dim separator |
|||
sub class_initialize |
|||
separator = "," |
|||
end sub |
|||
private function makeflat( a ) |
|||
dim i |
|||
dim res |
|||
for i = lbound( a ) to ubound( a ) |
|||
if isarray( a( i ) ) then |
|||
res = res & makeflat( a( i ) ) |
|||
else |
|||
res = res & a( i ) & separator |
|||
end if |
|||
next |
|||
makeflat = res |
|||
end function |
|||
public function flatten( a ) |
|||
dim res |
|||
res = makeflat( a ) |
|||
res = left( res, len( res ) - len(separator)) |
|||
res = split( res, separator ) |
|||
flatten = res |
|||
end function |
|||
public property let itemSeparator( c ) |
|||
separator = c |
|||
end property |
|||
end class |
|||
</syntaxhighlight> |
|||
=====Invocation===== |
|||
<syntaxhighlight lang="vb"> |
|||
dim flat |
|||
set flat = new flattener |
|||
flat.itemSeparator = "~" |
|||
wscript.echo join( flat.flatten( array( array( 1 ),2,array(array(3,4),5),array(array(array())),array(array(array(6))),7,8,array())), "!") |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
1!2!3!4!5!6!7!8 |
|||
</pre> |
|||
=====Alternative (classless) Version===== |
|||
{{works with|Windows Script Host|*}} |
|||
<syntaxhighlight lang="vbscript"> |
|||
' Flatten the example array... |
|||
a = FlattenArray(Array(Array(1), 2, Array(Array(3,4), 5), Array(Array(Array())), Array(Array(Array(6))), 7, 8, Array())) |
|||
' Print the list, comma-separated... |
|||
WScript.Echo Join(a, ",") |
|||
Function FlattenArray(a) |
|||
If IsArray(a) Then DoFlatten a, FlattenArray: FlattenArray = Split(Trim(FlattenArray)) |
|||
End Function |
|||
Sub DoFlatten(a, s) |
|||
For i = 0 To UBound(a) |
|||
If IsArray(a(i)) Then DoFlatten a(i), s Else s = s & a(i) & " " |
|||
Next |
|||
End Sub |
|||
</syntaxhighlight> |
|||
=={{header|V (Vlang)}}== |
|||
{{trans|PL/I}} |
|||
<syntaxhighlight lang="Zig"> |
|||
fn main() { |
|||
arr := "[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]" |
|||
println(convert(arr)) |
|||
} |
|||
fn convert(arr string) []int { |
|||
mut new_arr := []int{} |
|||
for value in arr.replace_each(["[","","]",""]).split_any(", ") {if value !="" {new_arr << value.int()}} |
|||
return new_arr |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[1, 2, 3, 4, 5, 6, 7, 8] |
|||
</pre> |
|||
=={{header|Wart}}== |
|||
Here's how Wart implements <code>flatten</code>: |
|||
<syntaxhighlight lang="python">def (flatten seq acc) |
|||
if no.seq |
|||
acc |
|||
~list?.seq |
|||
(cons seq acc) |
|||
:else |
|||
(flatten car.seq (flatten cdr.seq acc))</syntaxhighlight> |
|||
{{out}} |
|||
<pre>(flatten '((1) 2 ((3 4) 5) ((())) (((6))) 7 8 ())) |
|||
=> (1 2 3 4 5 6 7 8)</pre> |
|||
=={{header|WDTE}}== |
|||
<syntaxhighlight lang="wdte">let a => import 'arrays'; |
|||
let s => import 'stream'; |
|||
let flatten array => |
|||
a.stream array |
|||
-> s.flatMap (@ f v => v { |
|||
reflect 'Array' => a.stream v -> s.flatMap f; |
|||
}) |
|||
-> s.collect |
|||
;</syntaxhighlight> |
|||
'''Usage:''' |
|||
<syntaxhighlight lang="wdte">flatten [[1]; 2; [[3; 4]; 5]; [[[]]]; [[[6]]]; 7; 8; []] -- io.writeln io.stdout;</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[1; 2; 3; 4; 5; 6; 7; 8]</pre> |
|||
=={{header|Wren}}== |
|||
{{libheader|Wren-seq}} |
|||
A method already exists for this operation in the above module. |
|||
<syntaxhighlight lang="wren">import "./seq" for Lst |
|||
var a = [[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] |
|||
System.print(Lst.flatten(a))</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[1, 2, 3, 4, 5, 6, 7, 8] |
|||
</pre> |
|||
=={{header|zkl}}== |
|||
<syntaxhighlight lang="zkl">fcn flatten(list){ list.pump(List, |
|||
fcn(i){ if(List.isType(i)) return(Void.Recurse,i,self.fcn); i}) } |
|||
flatten(L(L(1), L(2), L(L(3,4), 5), L(L(L())), L(L(L(6))), 7, 8, L())) |
|||
//-->L(1,2,3,4,5,6,7,8)</syntaxhighlight> |
|||
This works by recursively writing the contents of lists to a new list. If a list is recursive or cyclic, it will blow the stack and throw an exception. |
Latest revision as of 14:12, 1 June 2024
![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.
- Task
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]
- Related task
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
- Output:
[[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("]")
- Output:
[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;
}
- Output:
[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] [1, 2, 3, 4, 5, 6, 7, 8]
ALGOL 68
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))
)
- Output:
+1 +2 +3 +4 +5 +6 +7 +8
APL
Dyalog APL
Flatten is a primitive in APL, named enlist
∊
- Output:
∊((1) 2 ((3 4) 5) (((⍬))) (((6))) 7 8 (⍬)) 1 2 3 4 5 6 7 8
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, to make more productive use of the language (where "efficiency" is a function of the scripter's time, rather than the machine's) we can express this in terms of a generic concatMap:
-- 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
- Output:
{1, 2, 3, 4, 5, 6, 7, 8}
It can be more efficient to build just one list by appending items to it than to proliferate lists using concatenation:
on flatten(theList)
script o
property flatList : {}
-- Recursive handler dealing with the current (sub)list.
on flttn(thisList)
script p
property l : thisList
end script
repeat with i from 1 to (count thisList)
set thisItem to item i of p's l
if (thisItem's class is list) then
flttn(thisItem)
else
set end of my flatList to thisItem
end if
end repeat
end flttn
end script
if (theList's class is not list) then return theList
o's flttn(theList)
return o's flatList
end flatten
Arturo
print flatten [[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]
- Output:
1 2 3 4 5 6 7 8
AutoHotkey
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
}
BASIC
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$, ",")
- Output:
"1",2,"\"3,4\",5","\"\\"\\"\"","\"\\"6\\"\"",7,8,"" 1,2,3,4,5,6,7,8
BASIC256
sComma = "": sFlatter = ""
sString = "[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8 []]"
For siCount = 1 To Length(sString)
If Instr("[] ,", Mid(sString, siCount, 1)) = 0 Then
sFlatter = sFlatter & sComma & Mid(sString, siCount, 1)
sComma = ", "
End If
Next siCount
Print "["; sFlatter; "]"
End
- Output:
Igual que la entrada de FreeBASIC.
Chipmunk Basic
10 cls
20 sstring$ = "[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8 []]"
30 for sicount = 1 to len(sstring$)
40 if instr("[] ,",mid$(sstring$,sicount,1)) = 0 then
50 sflatter$ = sflatter$+scomma$+mid$(sstring$,sicount,1)
60 scomma$ = ", "
70 endif
80 next sicount
90 print "[";sflatter$;"]"
100 end
FreeBASIC
Dim As String sComma, sString, sFlatter
Dim As Short siCount
sString = "[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8 []]"
For siCount = 1 To Len(sString)
If Instr("[] ,", Mid(sString, siCount, 1)) = 0 Then
sFlatter += sComma + Mid(sString, siCount, 1)
sComma = ", "
End If
Next siCount
Print "["; sFlatter; "]"
Sleep
- Output:
[1, 2, 3, 4, 5, 6, 7, 8]
Gambas
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]
GW-BASIC
10 CLS
20 SSTRING$ = "[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8 []]"
30 FOR SICOUNT = 1 TO LEN(SSTRING$)
40 IF INSTR("[] ,",MID$(SSTRING$,SICOUNT,1)) = 0 THEN SFLATTER$ = SFLATTER$+SCOMMA$+MID$(SSTRING$,SICOUNT,1): SCOMMA$ = ", "
50 NEXT SICOUNT
60 PRINT "[";SFLATTER$;"]"
70 END
MSX Basic
10 CLS
20 S$ = "[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8 []]"
30 FOR SICOUNT = 1 TO LEN(S$)
40 IF INSTR("[] ,",MID$(S$,SICOUNT,1)) = 0 THEN SFLATTER$ = SFLATTER$+SCOMMA$+MID$(S$,SICOUNT,1): SCOMMA$ = ", "
50 NEXT SICOUNT
60 PRINT "[";SFLATTER$;"]"
70 END
PureBasic
Structure RCList
Value.i
List A.RCList()
EndStructure
Procedure Flatten(List A.RCList())
ResetList(A())
While NextElement(A())
With A()
If \Value
Continue
Else
ResetList(\A())
While NextElement(\A())
If \A()\Value: A()\Value=\A()\Value: EndIf
Wend
EndIf
While ListSize(\A()): DeleteElement(\A()): Wend
If Not \Value: DeleteElement(A()): EndIf
EndWith
Wend
EndProcedure
Set up the MD-List & test the Flattening procedure.
;- Set up two lists, one multi dimensional and one 1-D.
NewList A.RCList()
;- Create a deep list
With A()
AddElement(A()): AddElement(\A()): AddElement(\A()): \A()\Value=1
AddElement(A()): A()\Value=2
AddElement(A()): AddElement(\A()): \A()\Value=3
AddElement(\A()): \A()\Value=4
AddElement(A()): AddElement(\A()): \A()\Value=5
AddElement(A()): AddElement(\A()): AddElement(\A()): AddElement(\A())
AddElement(A()): AddElement(\A()): AddElement(\A()): \A()\Value=6
AddElement(A()): A()\Value=7
AddElement(A()): A()\Value=8
AddElement(A()): AddElement(\A()): AddElement(\A())
EndWith
Flatten(A())
;- Present the result
If OpenConsole()
Print("Flatten: [")
ForEach A()
Print(Str(A()\Value))
If ListIndex(A())<(ListSize(A())-1)
Print(", ")
Else
PrintN("]")
EndIf
Next
Print(#CRLF$+"Press ENTER to quit"): Input()
EndIf
Flatten: [1, 2, 4, 5, 6, 7, 8]
QBasic
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 siCount
PRINT "["; sFlatter$; "]"
END
Run BASIC
n$ = "[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8 []]"
for i = 1 to len(n$)
if instr("[] ,",mid$(n$,i,1)) = 0 then
flatten$ = flatten$ + c$ + mid$(n$,i,1)
c$ = ","
end if
next i
print "[";flatten$;"]"
- Output:
[1,2,3,4,5,6,7,8]
TI-89 BASIC
There is no nesting of lists or other data structures in TI-89 BASIC, short of using variable names as pointers.
True BASIC
LET sstring$ = "[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8 []]"
FOR sicount = 1 TO LEN(sstring$)
IF pos("[] ,",(sstring$)[sicount:sicount+1-1]) = 0 THEN
LET sflatter$ = sflatter$ & scomma$ & (sstring$)[sicount:sicount+1-1]
LET scomma$ = ", "
END IF
NEXT sicount
PRINT "["; sflatter$; "]"
END
XBasic
PROGRAM "Flatten a list"
DECLARE FUNCTION Entry ()
FUNCTION Entry ()
n$ = "[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8 []]"
FOR i = 1 TO LEN(n$)
IF INSTR("[] ,",MID$(n$,i,1)) = 0 THEN
flatten$ = flatten$ + c$ + MID$(n$,i,1)
c$ = ", "
END IF
NEXT i
PRINT "[";flatten$;"]"
END FUNCTION
END PROGRAM
- Output:
[1, 2, 3, 4, 5, 6, 7, 8]
Yabasic
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 siCount
Print "[", sFlatter$, "]"
End
- Output:
Igual que la entrada de FreeBASIC.
ZX Spectrum Basic
10 LET f$="["
20 LET n$="[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8 []]"
30 FOR i=2 TO (LEN n$)-1
40 IF n$(i)>"/" AND n$(i)<":" THEN LET f$=f$+n$(i): GO TO 60
50 IF n$(i)="," AND f$(LEN f$)<>"," THEN LET f$=f$+","
60 NEXT i
70 LET f$=f$+"]": PRINT f$
BQN
Enlist ← {(∾𝕊¨)⍟(1<≡)⥊𝕩}
- Output:
Enlist ⟨⟨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;
}
- Output:
Nested: [[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] Flattened: [1, 2, 3, 4, 5, 6, 7, 8]
C#
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 ( ) );
}
}
}
}
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();
}
}
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";
}
- Output:
[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] [1, 2, 3, 4, 5, 6, 7, 8]
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());
}
- Output:
[[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
(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.
- Output:
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;
}
- Output:
[[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;
}
- Output:
[1, 2, 3, 4, 5, 6, 7, 8]
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 [] ]
- Output:
[ 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
- Output:
[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)
- Output:
[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))))))
The flatten-tree function was added in Emacs 27.1 or earlier.
(flatten-tree 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
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)
- Output:
{ {1}, 2, { {3,4}, 5 }, { {{}} }, { { {6} } }, 7, 8, {} } {1,2,3,4,5,6,7,8}
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 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]]
FutureBasic
Definitely old school.
local fn FlattenList( list as Str255 ) as Str255
long i
Str255 flatStr, commaStr
flatStr = ""
for i = 1 to len$(list)
if ( instr$( 0, "[] ,", mid$( list, i, 1 ) ) === 0 )
flatStr += commaStr + mid$( list, i, 1 )
commaStr = ", "
end if
next
end fn = flatStr
window 1, @"Flatten a list", ( 0, 0, 350, 150 )
print "["; fn FlattenList( "[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8 []]" ); "]"
HandleEvents
- Output:
[1, 2, 3, 4, 5, 6, 7, 8]
Modern and a little outside the box.
void local fn FlattenAList
CFStringRef listStr = @"[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]"
CFArrayRef listArr = fn StringComponentsSeparatedByCharactersInSet( listStr, fn CharacterSetWithCharactersInString( @"\"[ ]," ) )
CFMutableArrayRef mutArr = fn MutableArrayWithArray( listArr )
MutableArrayRemoveObject( mutArr, @"" )
CFStringRef flatStr = fn ArrayComponentsJoinedByString( mutArr, @", " )
printf @"[%@]", flatStr
end fn
fn FlattenAList
HandleEvents
- Output:
[1, 2, 3, 4, 5, 6, 7, 8]
GAP
Flat([[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'┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
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
}
- Output:
[[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
- Output:
[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]
Icon and 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.
The solution uses several procedures from 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.
Finally a demo routine to drive these and a helper to show how it works.
Insitux
Insitux has a built-in flatten function.
(flatten [[1] 2 [[3 4] 5] [[[]]] [[[6]]] 7 8 []])
- Output:
[1 2 3 4 5 6 7 8]
Ioke
iik> [[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]
Isabelle
theory Scratch
imports Main
begin
datatype 'a tree = Leaf 'a ("<_>")
| Node "'a tree list" ("⟦ _ ⟧")
text‹The datatype introduces special pretty printing:›
lemma "Leaf a = <a>" by simp
lemma "Node [] = ⟦ [] ⟧" by simp
definition "example ≡ ⟦[ ⟦[<1>]⟧, <2>, ⟦[ ⟦[<3>, <4>]⟧, <5>]⟧, ⟦[⟦[⟦[]⟧]⟧]⟧, ⟦[⟦[⟦[<6>]⟧]⟧]⟧, <7>, <8>, ⟦[]⟧ ]⟧"
lemma "example =
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 []
]"
by(simp add: example_def)
fun flatten :: "'a tree ⇒ 'a list" where
"flatten (Leaf a) = [a]"
| "flatten (Node xs) = concat (map flatten xs)"
lemma "flatten example = [1, 2, 3, 4, 5, 6, 7, 8]"
by(simp add: example_def)
end
J
Solution:
flatten =: [: ; <S:0
Example:
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
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<Object>
. We cannot type-safely put the result into a generic type List<T>
because there is no way to enforce that the original list contains elements of "type T or lists of elements which are T or further lists..."; there is no generic type parameter that will express that restriction. Since we must accept lists of any elements as an argument, we can only safely put them in a List<Object>
.
Actual Workhorse code
import java.util.LinkedList;
import java.util.List;
public final class FlattenUtil {
public static List<Object> flatten(List<?> list) {
List<Object> retVal = new LinkedList<Object>();
flatten(list, retVal);
return retVal;
}
public static void flatten(List<?> fromTreeList, List<Object> toFlatList) {
for (Object item : fromTreeList) {
if (item instanceof List<?>) {
flatten((List<?>) item, toFlatList);
} else {
toFlatList.add(item);
}
}
}
}
Method showing population of the test List and usage of flatten method.
import static java.util.Arrays.asList;
import java.util.List;
public final class FlattenTestMain {
public static void main(String[] args) {
List<Object> treeList = a(a(1), 2, a(a(3, 4), 5), a(a(a())), a(a(a(6))), 7, 8, a());
List<Object> flatList = FlattenUtil.flatten(treeList);
System.out.println(treeList);
System.out.println("flatten: " + flatList);
}
private static List<Object> a(Object... a) {
return asList(a);
}
}
- Output:
[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] flatten: [1, 2, 3, 4, 5, 6, 7, 8]
- Functional version
import java.util.List;
import java.util.stream.Stream;
import java.util.stream.Collectors;
public final class FlattenUtil {
public static Stream<Object> flattenToStream(List<?> list) {
return list.stream().flatMap(item ->
item instanceof List<?> ?
flattenToStream((List<?>)item) :
Stream.of(item));
}
public static List<Object> flatten(List<?> list) {
return flattenToStream(list).collect(Collectors.toList());
}
}
JavaScript
ES5
function flatten(list) {
return list.reduce(function (acc, val) {
return acc.concat(val.constructor === Array ? flatten(val) : val);
}, []);
}
Or, expressed in terms of the more generic concatMap function:
(function () {
'use strict';
// flatten :: Tree a -> [a]
function flatten(t) {
return (t instanceof Array ? concatMap(flatten, t) : t);
}
// concatMap :: (a -> [b]) -> [a] -> [b]
function concatMap(f, xs) {
return [].concat.apply([], xs.map(f));
}
return flatten(
[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]
);
})();
From fusion of flatten with concatMap we can then derive:
// flatten :: Tree a -> [a]
function flatten(a) {
return a instanceof Array ? [].concat.apply([], a.map(flatten)) : a;
}
For example:
(function () {
'use strict';
// flatten :: Tree a -> [a]
function flatten(a) {
return a instanceof Array ? [].concat.apply([], a.map(flatten)) : a;
}
return flatten(
[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]
);
})();
- Output:
[1, 2, 3, 4, 5, 6, 7, 8]
ES6
Built-in
// flatten :: NestedList a -> [a]
const flatten = nest =>
nest.flat(Infinity);
Recursive
// flatten :: NestedList a -> [a]
const flatten = t => {
const go = x =>
Array.isArray(x) ? (
x.flatMap(go)
) : x;
return go(t);
};
Iterative
function flatten(list) {
for (let i = 0; i < list.length; i++) {
while (true) {
if (Array.isArray(list[i])) {
list.splice(i, 1, ...list[i]);
} else {
break;
}
}
}
return list;
}
Or alternatively:
// flatten :: Nested List a -> a
const flatten = t => {
let xs = t;
while (xs.some(Array.isArray)) {
xs = [].concat(...xs);
}
return xs;
};
Result is always:
[1, 2, 3, 4, 5, 6, 7, 8]
Joy
"seqlib" libload.
[[1] 2 [[3 4] 5] [[[]]] [[[6]]] 7 8 []] treeflatten.
(* output: [1 2 3 4 5 6 7 8] *)
jq
Recent (1.4+) versions of jq include the following flatten filter:
def flatten:
reduce .[] as $i
([];
if $i | type == "array" then . + ($i | flatten)
else . + [$i]
end);
Example:
[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] | flatten
[1,2,3,4,5,6,7,8]
Jsish
From Javascript entry, with change to test for typeof equal "array".
/* Flatten list, in Jsish */
function flatten(list) {
return list.reduce(function (acc, val) {
return acc.concat(typeof val === "array" ? flatten(val) : val);
}, []);
}
if (Interp.conf('unitTest')) {
; flatten([[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]);
}
/*
=!EXPECTSTART!=
flatten([[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]) ==> [ 1, 2, 3, 4, 5, 6, 7, 8 ]
=!EXPECTEND!=
*/
- Output:
prompt$ jsish --U flatten.jsi flatten([[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]) ==> [ 1, 2, 3, 4, 5, 6, 7, 8 ]
Julia
(Note that Julia versions prior to 0.5 automatically flattened nested arrays.)
The following version of flatten makes use of the higher order function mapreduce.
isflat(x) = isempty(x) || first(x) === x
function flat_mapreduce(arr)
mapreduce(vcat, arr, init=[]) do x
isflat(x) ? x : flat(x)
end
end
An iterative recursive version that uses less memory but is slower:
function flat_recursion(arr)
res = []
function grep(v)
for x in v
if x isa Array
grep(x)
else
push!(res, x)
end
end
end
grep(arr)
res
end
Using the Iterators library from the Julia base:
function flat_iterators(arr)
while any(a -> a isa Array, arr)
arr = collect(Iterators.flatten(arr))
end
arr
end
Benchmarking these three functions using the BenchmarkTools package yields the following results:
using BenchmarkTools
arr = [[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]
@show flat_mapreduce(arr)
@show flat_recursion(arr)
@show flat_iterators(arr)
@btime flat_mapreduce($arr)
@btime flat_recursion($arr)
@btime flat_iterators($arr)
- Output:
flat_mapreduce(arr) = Any[1, 2, 3, 4, 5, 6, 7, 8] flat_recursion(arr) = Any[1, 2, 3, 4, 5, 6, 7, 8] flat_iterators(arr) = [1, 2, 3, 4, 5, 6, 7, 8] 14.163 μs (131 allocations: 4.27 KiB) 500.824 ns (4 allocations: 176 bytes) 28.223 μs (133 allocations: 4.33 KiB)
K
In K, join is: ,
and reduce/fold (called "over") is: /
. With a monadic argument (as ,/ is), over repeats application until reaching a fixed-point.
So to flatten a list of arbitrary depth, you can join-over-over, or reduce a list with a function that reduces a list with a join function:
,//((1); 2; ((3;4); 5); ((())); (((6))); 7; 8; ())
Kotlin
// version 1.0.6
@Suppress("UNCHECKED_CAST")
fun flattenList(nestList: List<Any>, flatList: MutableList<Int>) {
for (e in nestList)
if (e is Int)
flatList.add(e)
else
// using unchecked cast here as can't check for instance of 'erased' generic type
flattenList(e as List<Any>, flatList)
}
fun main(args: Array<String>) {
val nestList : List<Any> = listOf(
listOf(1),
2,
listOf(listOf(3, 4), 5),
listOf(listOf(listOf<Int>())),
listOf(listOf(listOf(6))),
7,
8,
listOf<Int>()
)
println("Nested : " + nestList)
val flatList = mutableListOf<Int>()
flattenList(nestList, flatList)
println("Flattened : " + flatList)
}
Or, using a more functional approach:
fun flatten(list: List<*>): List<*> {
fun flattenElement(elem: Any?): Iterable<*> {
return if (elem is List<*>)
if (elem.isEmpty()) elem
else flattenElement(elem.first()) + flattenElement(elem.drop(1))
else listOf(elem)
}
return list.flatMap { elem -> flattenElement(elem) }
}
- Output:
Nested : [[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] Flattened : [1, 2, 3, 4, 5, 6, 7, 8]
Lambdatalk
Lambdatalk doesn't have a builtin primitive flattening a multidimensionnal array.
1) Let's create this function
{def A.flatten
{def A.flatten.r
{lambda {:a}
{if {A.empty? :a}
then
else {let { {:b {A.first :a}}
} {if {A.array? :b}
then {A.flatten.r :b}
else :b} }
{A.flatten.r {A.rest :a}} }}}
{lambda {:a}
{A.new {A.flatten.r :a}}}}
-> A.flatten
and test it
{def list
{A.new
{A.new 1}
2
{A.new {A.new 3 4} 5}
{A.new {A.new {A.new }}}
{A.new {A.new {A.new 6}}}
7
8
{A.new}
}}
-> [[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]
{A.flatten {list}}
-> [1,2,3,4,5,6,7,8]
Lasso
Lasso Delve is a Lasso utility method explicitly for handling embedded arrays. With one array which contain other arrays, delve allows you to treat one array as a single series of elements, thus enabling easy access to an entire tree of values. www.lassosoft.com/lassoDocs/languageReference/obj/delve Lasso reference on Delve
local(original = json_deserialize('[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]'))
#original
'<br />'
(with item in delve(#original)
select #item) -> asstaticarray
array(array(1), 2, array(array(3, 4), 5), array(array(array())), array(array(array(6))), 7, 8, array()) staticarray(1, 2, 3, 4, 5, 6, 7, 8)
LFE
> (: lists flatten '((1) 2 ((3 4) 5) ((())) (((6))) 7 8 ()))
(1 2 3 4 5 6 7 8)
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
Logtalk
flatten(List, Flatted) :-
flatten(List, [], Flatted).
flatten(Var, Tail, [Var| Tail]) :-
var(Var),
!.
flatten([], Flatted, Flatted) :-
!.
flatten([Head| Tail], List, Flatted) :-
!,
flatten(Tail, List, Aux),
flatten(Head, Aux, Flatted).
flatten(Head, Tail, [Head| Tail]).
Lua
function flatten(list)
if type(list) ~= "table" then return {list} end
local flat_list = {}
for _, elem in ipairs(list) do
for _, val in ipairs(flatten(elem)) do
flat_list[#flat_list + 1] = val
end
end
return flat_list
end
test_list = {{1}, 2, {{3,4}, 5}, {{{}}}, {{{6}}}, 7, 8, {}}
print(table.concat(flatten(test_list), ","))
Maple
This can be accomplished using the Flatten
command from the ListTools
, or with a custom recursive procedure.
L := [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]:
with(ListTools):
Flatten(L);
- Output:
[1, 2, 3, 4, 5, 6, 7, 8]
flatten := proc(x)
`if`(type(x,'list'),seq(procname(i),i = x),x);
end proc:
L := [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]:
[flatten(L)];
- Output:
[1, 2, 3, 4, 5, 6, 7, 8]
Mathematica / Wolfram Language
Flatten[{{1}, 2, {{3, 4}, 5}, {{{}}}, {{{6}}}, 7, 8, {}}]
Maxima
flatten([[[1, 2, 3], 4, [5, [6, 7]], 8], [[9, 10], 11], 12]);
/* [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] */
Mercury
As with Haskell we need to use an algebraic data type.
:- module flatten_a_list.
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is det.
:- implementation.
:- import_module list.
:- type tree(T)
---> leaf(T)
; node(list(tree(T))).
:- func flatten(tree(T)) = list(T).
flatten(leaf(X)) = [X].
flatten(node(Xs)) = condense(map(flatten, Xs)).
main(!IO) :-
List = 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([])
]),
io.print_line(flatten(List), !IO).
:- end_module flatten_a_list.
- Output:
[1, 2, 3, 4, 5, 6, 7, 8]
min
(
(dup 'quotation? any?) 'flatten while
) ^deep-flatten
((1) 2 ((3 4) 5) ((())) (((6))) 7 8 ()) deep-flatten puts!
- Output:
(1 2 3 4 5 6 7 8)
Mirah
import java.util.ArrayList
import java.util.List
import java.util.Collection
def flatten(list: Collection)
flatten(list, ArrayList.new)
end
def flatten(source: Collection, result: List)
source.each do |x|
if x.kind_of?(Collection)
flatten(Collection(x), result)
else
result.add(x)
result # if branches must return same type
end
end
result
end
# creating a list-of-list-of-list fails currently, so constructor calls are needed
source = [[1], 2, [[3, 4], 5], [[ArrayList.new]], [[[6]]], 7, 8, ArrayList.new]
puts flatten(source)
NewLISP
> (flat '((1) 2 ((3 4) 5) ((())) (((6))) 7 8 ()))
(1 2 3 4 5 6 7 8)
NGS
Note that when kern method is called, the multi-dispatch tries to match kern parameters with given arguments last added F first: if x is an array, the second F kern is invoked, otherwise the first F kern is invoked.
NGS defines flatten as a shallow flatten, hence using flatten_r here.
F flatten_r(a:Arr)
collector {
local kern
F kern(x) collect(x)
F kern(x:Arr) x.each(kern)
kern(a)
}
echo(flatten_r([[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]))
- Output:
[1,2,3,4,5,6,7,8]
Nim
Nim is statically-typed, so we need to use an object variant
type
TreeList[T] = object
case isLeaf: bool
of true: data: T
of false: list: seq[TreeList[T]]
proc L[T](list: varargs[TreeList[T]]): TreeList[T] =
for x in list:
result.list.add x
proc N[T](data: T): TreeList[T] =
TreeList[T](isLeaf: true, data: data)
proc flatten[T](n: TreeList[T]): seq[T] =
if n.isLeaf: result = @[n.data]
else:
for x in n.list:
result.add flatten x
var x = L(L(N 1), N 2, L(L(N 3, N 4), N 5), L(L(L[int]())), L(L(L(N 6))), N 7, N 8, L[int]())
echo flatten(x)
- Output:
@[1, 2, 3, 4, 5, 6, 7, 8]
Objective-C
#import <Foundation/Foundation.h>
@interface NSArray (FlattenExt)
@property (nonatomic, readonly) NSArray *flattened;
@end
@implementation NSArray (FlattenExt)
-(NSArray *) flattened {
NSMutableArray *flattened = [[NSMutableArray alloc] initWithCapacity:self.count];
for (id object in self) {
if ([object isKindOfClass:[NSArray class]])
[flattened addObjectsFromArray:((NSArray *)object).flattened];
else
[flattened addObject:object];
}
return [flattened autorelease];
}
@end
int main() {
@autoreleasepool {
NSArray *p = @[
@[ @1 ],
@2,
@[ @[@3, @4], @5],
@[ @[ @[ ] ] ],
@[ @[ @[ @6 ] ] ],
@7,
@8,
@[ ] ];
for (id object in unflattened.flattened)
NSLog(@"%@", object);
}
return 0;
}
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]
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:
# 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]
Oforth
[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] expand println
- Output:
[1, 2, 3, 4, 5, 6, 7, 8]
Ol
(define (flatten x)
(cond
((null? x)
'())
((not (pair? x))
(list x))
(else
(append (flatten (car x))
(flatten (cdr x))))))
(print
(flatten '((1) 2 ((3 4) 5) ((())) (((6))) 7 8 ())))
- Output:
(1 2 3 4 5 6 7 8)
ooRexx
sub1 = .array~of(1)
sub2 = .array~of(3, 4)
sub3 = .array~of(sub2, 5)
sub4 = .array~of(.array~of(.array~new))
sub5 = .array~of(.array~of(.array~of(6)))
sub6 = .array~new
-- final list construction
list = .array~of(sub1, 2, sub3, sub4, sub5, 7, 8, sub6)
-- flatten
flatlist = flattenList(list)
say "["flatlist~toString("line", ", ")"]"
::routine flattenList
use arg list
-- we could use a list or queue, but let's just use an array
accumulator = .array~new
-- now go to the recursive processing version
call flattenSublist list, accumulator
return accumulator
::routine flattenSublist
use arg list, accumulator
-- ask for the items explicitly, since this will allow
-- us to flatten indexed collections as well
do item over list~allItems
-- if the object is some sort of collection, flatten this out rather
-- than add to the accumulator
if item~isA(.collection) then call flattenSublist item, accumulator
else accumulator~append(item)
end
Oz
Oz has a standard library function "Flatten":
{Show {Flatten [[1] 2 [[3 4] 5] [[nil]] [[[6]]] 7 8 nil]}}
A simple, non-optimized implementation could look like this:
fun {Flatten2 Xs}
case Xs of nil then nil
[] X|Xr then
{Append {Flatten2 X} {Flatten2 Xr}}
else [Xs]
end
end
PARI/GP
flatten(v)={
my(u=[]);
for(i=1,#v,
u=concat(u,if(type(v[i])=="t_VEC",flatten(v[i]),v[i]))
);
u
};
PascalABC.NET
function Flatten(lst: List<object>): List<object>;
begin
Result := new List<object>;
foreach var x in lst do
if x is List<object> then
Result.Addrange(Flatten(x as List<object>))
else Result.Add(x)
end;
function LstObj(params a: array of object): List<Object> := new List<Object>(a);
begin
var lst := LstObj(1,LstObj(2, LstObj(3,4), LstObj(5,6)), LstObj(LstObj(7,8), 9));
Println(lst);
Println(Flatten(lst));
end.
- Output:
[1,[2,[3,4],[5,6]],[[7,8],9]] [1,2,3,4,5,6,7,8,9]
Perl
sub flatten {
map { ref eq 'ARRAY' ? flatten(@$_) : $_ } @_
}
my @lst = ([1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []);
print flatten(@lst), "\n";
Phix
standard builtin
?flatten({{1},2,{{3,4},5},{{{}}},{{{6}}},7,8,{}})
- Output:
{1,2,3,4,5,6,7,8}
Phixmonti
1 2 3 10 20 30 3 tolist 4 5 6 3 tolist 2 tolist 1000 "Hello" 6 tolist
dup print nl flatten print
With syntactic sugar
include ..\Utilitys.pmt
( 1 2 3 ( ( 10 20 30 ) ( 4 5 6 ) ) 1000 "Hola" )
dup ? flatten ?
- Output:
[1, 2, 3, [[10, 20, 30], [4, 5, 6]], 1000, "Hello"] [1, 2, 3, 10, 20, 30, 4, 5, 6, 1000, "Hello"]
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);
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
<?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));
?>
Alternatively:
<?php
function flatten($ary) {
$result = array();
array_walk_recursive($ary, function($x, $k) use (&$result) { $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));
?>
<?php
function flatten_helper($x, $k, $obj) {
$obj->flattened[] = $x;
}
function flatten($ary) {
$obj = (object)array('flattened' => array());
array_walk_recursive($ary, 'flatten_helper', $obj);
return $obj->flattened;
}
$lst = array(array(1), 2, array(array(3, 4), 5), array(array(array())), array(array(array(6))), 7, 8, array());
var_dump(flatten($lst));
?>
Using the standard library (warning: objects will also be flattened by this method):
<?php
$lst = array(array(1), 2, array(array(3, 4), 5), array(array(array())), array(array(array(6))), 7, 8, array());
$result = iterator_to_array(new RecursiveIteratorIterator(new RecursiveArrayIterator($lst)), false);
var_dump($result);
?>
Non-recursive
Function flat is iterative and flattens the array in-place.
<?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);
?>
PicoLisp
(de flatten (X)
(make # Build a list
(recur (X) # recursively over 'X'
(if (atom X)
(link X) # Put atoms into the result
(mapc recurse X) ) ) ) ) # or recurse on sub-lists
or a more succint way using fish:
(de flatten (X)
(fish atom X) )
Pike
There's a built-in function called Array.flatten()
which does this, but here's a custom function:
array flatten(array a) {
array r = ({ });
foreach (a, mixed n) {
if (arrayp(n)) r += flatten(n);
else r += ({ n });
}
return r;
}
PL/I
The Translate(text,that,this) intrinsic function returns text with any character in text that is found in this (say the third) replaced by the corresponding third character in that. Suppose the availability of a function Replace(text,that,this) which returns text with all occurrences of this (a single text, possibly many characters) replaced by that, possibly zero characters. The Translate function does not change the length of its string, simply translate its characters in place.
list = translate (list, ' ', '[]' ); /*Produces " 1 , 2, 3,4 , 5 , , 6 , 7, 8, " */
list = Replace(list,'',' '); /*Converts spaces to nothing. Same parameter order as Translate.*/
do while index(list,',,') > 0; /*Is there a double comma anywhere?
list = Replace(list,',',',,'); /*Yes. Convert double commas to single, nullifying empty lists*/
end; /*And search afresh, in case of multiple commas in a row.*/
list = '[' || list || ']'; /*Repackage the list.*/
This is distinctly crude. A user-written Replace function is confronted by the requirement to specify a maximum size for its returned result, for instance Replace:Procedure(text,that,this) Returns(Character 200 Varying);
which is troublesome for general use. The intrinsic function Translate has no such restriction.
An alternative would be to translate the commas into spaces also (thereby the null entry vanishes) then scan along the result.
PostScript
/flatten {
/.f {{type /arraytype eq} {{.f} map aload pop} ift}.
[exch .f]
}.
[[1] 2 [[3 4] 5] [[[]]] [[[6]]] 7 8 []] flatten
PowerShell
function flatten($a) {
if($a.Count -gt 1) {
$a | foreach{ $(flatten $_)}
} else {$a}
}
$a = @(@(1), 2, @(@(3,4), 5), @(@(@())), @(@(@(6))), 7, 8, @())
"$(flatten $a)"
Output:
1 2 3 4 5 6 7 8
Prolog
flatten(List, FlatList) :-
flatten(List, [], FlatList).
flatten(Var, T, [Var|T]) :-
var(Var), !.
flatten([], T, T) :- !.
flatten([H|T], TailList, List) :- !,
flatten(H, FlatTail, List),
flatten(T, TailList, FlatTail).
flatten(NonList, T, [NonList|T]).
Python
Recursive
>>> def flatten(lst):
return sum( ([x] if not isinstance(x, 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]
Recursive, generative and working with any type of iterable object
>>> def flatten(itr):
>>> for x in itr:
>>> try:
>>> yield from flatten(x)
>>> except:
>>> yield x
>>> lst = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]
>>> list(flatten(lst))
[1, 2, 3, 4, 5, 6, 7, 8]
>>> tuple(flatten(lst))
(1, 2, 3, 4, 5, 6, 7, 8)
>>>for i in flatten(lst):
>>> print(i)
1
2
3
4
5
6
7
8
Non-recursive
Function flat is iterative and flattens the list in-place. It follows the Python idiom of returning None when acting in-place:
>>> 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]
Generative
This method shows a solution using Python generators.
flatten
is a generator that yields the non-list values of its input in order.
In this case, the generator is converted back to a list before printing.
>>> def flatten(lst):
for x in lst:
if isinstance(x, list):
for x in flatten(x):
yield x
else:
yield x
>>> lst = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]
>>> print list(flatten(lst))
[1, 2, 3, 4, 5, 6, 7, 8]
Functional Recursive
And, as the idea of Rosetta Code is to demonstrate how languages are similar as well as different, and to thus to 'aid a person with a grounding in one approach to a problem in learning another', here it is in terms of concatMap, which can be defined in any language, including mathematics, and which can be variously expressed in Python. (The fastest Python implementation of the concat component of the (concat . map) composition seems to be in terms of itertools.chain).
'''Flatten a nested list'''
from itertools import (chain)
# ----------------------- FLATTEN ------------------------
# flatten :: NestedList a -> [a]
def flatten(x):
'''A list of atomic values resulting from fully
flattening an arbitrarily nested list.
'''
return concatMap(flatten)(x) if (
isinstance(x, list)
) else [x]
# ------------------------- TEST -------------------------
def main():
'''Test: flatten an arbitrarily nested list.
'''
print(
fTable(__doc__ + ':')(showList)(showList)(
flatten
)([
[[[]]],
[[1, 2, 3]],
[[1], [[2]], [[[3, 4]]]],
[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]
])
)
# ----------------------- GENERIC ------------------------
# compose (<<<) :: (b -> c) -> (a -> b) -> a -> c
def compose(g):
'''Right to left function composition.'''
return lambda f: lambda x: g(f(x))
# concatMap :: (a -> [b]) -> [a] -> [b]
def concatMap(f):
'''A concatenated list over which a function has been mapped.
The list monad can be derived by using a function f which
wraps its output in a list,
(using an empty list to represent computational failure).
'''
def go(xs):
return chain.from_iterable(map(f, xs))
return go
# fTable :: String -> (a -> String) ->
# (b -> String) ->
# (a -> b) -> [a] -> String
def fTable(s):
'''Heading -> x display function ->
fx display function ->
f -> value list -> tabular string.'''
def go(xShow, fxShow, f, xs):
w = max(map(compose(len)(xShow), xs))
return s + '\n' + '\n'.join([
xShow(x).rjust(w, ' ') + (' -> ') + fxShow(f(x))
for x in xs
])
return lambda xShow: lambda fxShow: lambda f: lambda xs: go(
xShow, fxShow, f, xs
)
# showList :: [a] -> String
def showList(xs):
'''Stringification of a list.'''
return '[' + ','.join(str(x) for x in xs) + ']'
if __name__ == '__main__':
main()
- Output:
Flatten a nested list: [[[]]] -> [] [[1, 2, 3]] -> [1,2,3] [[1],[[2]],[[[3, 4]]]] -> [1,2,3,4] [[1],2,[[3, 4], 5],[[[]]],[[[6]]],7,8,[]] -> [1,2,3,4,5,6,7,8]
Functional Non-recursive
And, in contexts where it may be desirable to avoid not just recursion, but also:
- mutation of the original list, and
- dependence on error-events for evaluation control,
we can again use the universal concat . map composition (see the second recursive example above) by embedding it in a fold / reduction, and using it with a pure, but iteratively-implemented, until function.
( Note that the generic functions in the following example are curried, enabling not only more flexible composition, but also some simplifying reductions – here eliminating the need for two uses of Python's lambda keyword ):
'''Flatten a list'''
from functools import (reduce)
from itertools import (chain)
def flatten(xs):
'''A flat list of atomic values derived
from a nested list.
'''
return reduce(
lambda a, x: a + list(until(every(notList))(
concatMap(pureList)
)([x])),
xs, []
)
# TEST ----------------------------------------------------
def main():
'''From nested list to flattened list'''
print(main.__doc__ + ':\n\n')
xs = [[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]
print(
repr(xs) + ' -> ' + repr(flatten(xs))
)
# GENERIC -------------------------------------------------
# concatMap :: (a -> [b]) -> [a] -> [b]
def concatMap(f):
'''A concatenated list over which a function has been mapped.
The list monad can be derived by using a function f which
wraps its output in a list,
(using an empty list to represent computational failure).
'''
return lambda xs: list(
chain.from_iterable(map(f, xs))
)
# every :: (a -> Bool) -> [a] -> Bool
def every(p):
'''True if p(x) holds for every x in xs'''
def go(p, xs):
return all(map(p, xs))
return lambda xs: go(p, xs)
# notList :: a -> Bool
def notList(x):
'''True if the value x is not a list.'''
return not isinstance(x, list)
# pureList :: a -> [b]
def pureList(x):
'''x if x is a list, othewise [x]'''
return x if isinstance(x, list) else [x]
# until :: (a -> Bool) -> (a -> a) -> a -> a
def until(p):
'''The result of repeatedly applying f until p holds.
The initial seed value is x.'''
def go(f, x):
v = x
while not p(v):
v = f(v)
return v
return lambda f: lambda x: go(f, x)
if __name__ == '__main__':
main()
- Output:
From nested list to flattened list: [[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] -> [1, 2, 3, 4, 5, 6, 7, 8]
Q
We repeatedly apply raze until the return value converges to a fixed value.
(raze/) ((1); 2; ((3;4); 5); ((())); (((6))); 7; 8; ())
Quackery
forward is flatten
[ [] swap
witheach
[ dup nest?
if flatten
join ] ] resolves flatten ( [ --> [ )
Output:
/O> ' [ [ 1 ] 2 [ [ 3 4 ] 5 ] [ [ [ ] ] ] [ [ [ 6 ] ] ] 7 8 [ ] ] flatten
...
Stack: [ 1 2 3 4 5 6 7 8 ]
R
x <- list(list(1), 2, list(list(3, 4), 5), list(list(list())), list(list(list(6))), 7, 8, list())
unlist(x)
Racket
Racket has a built-in flatten function:
#lang racket
(flatten '(1 (2 (3 4 5) (6 7)) 8 9))
- Output:
'(1 2 3 4 5 6 7 8 9)
or, writing it explicitly with the same result:
#lang racket
(define (flatten l)
(cond [(empty? l) null]
[(not (list? l)) (list l)]
[else (append (flatten (first l)) (flatten (rest l)))]))
(flatten '(1 (2 (3 4 5) (6 7)) 8 9))
Raku
(formerly Perl 6)
my @l = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []];
say .perl given gather @l.deepmap(*.take); # lazy recursive version
# Another way to do it is with a recursive function (here actually a Block calling itself with the &?BLOCK dynamic variable):
say { |(@$_ > 1 ?? map(&?BLOCK, @$_) !! $_) }(@l)
REBOL
flatten: func [
"Flatten the block in place."
block [any-block!]
][
parse block [
any [block: any-block! (change/part block first block 1) :block | skip]
]
head block
]
Sample:
>> flatten [[1] 2 [[3 4] 5] [[[]]] [[[6]]] 7 8 []] == [1 2 3 4 5 6 7 8]
Red
flatten: function [
"Flatten the block"
block [any-block!]
][
load form block
]
red>> flatten [[1] 2 [[3 4] 5] [[[]]] [[[6]]] 7 8 []]
== [1 2 3 4 5 6 7 8]
;flatten a list to a string
>> blk: [1 2 ["test"] "a" [["bb"]] 3 4 [[[99]]]]
>> form blk
== "1 2 test a bb 3 4 99"
Refal
$ENTRY Go {
, ((1) 2 ((3 4) 5) ((())) (((6))) 7 8 ()): e.List
= <Prout e.List ' -> ' <Flatten e.List>>
};
Flatten {
= ;
s.I e.X = s.I <Flatten e.X>;
(e.X) e.Y = <Flatten e.X> <Flatten e.Y>;
};
- Output:
((1 )2 ((3 4 )5 )((()))(((6 )))7 8 ()) -> 1 2 3 4 5 6 7 8
REXX
/*REXX program (translated from PL/I) flattens a list (the data need not be numeric).*/
list= '[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]' /*the list to be flattened. */
say list /*display the original list. */
c= ',' /*define a literal (1 comma). */
cc= ',,' /* " " " (2 commas).*/
list= translate(list, , "[]") /*translate brackets to blanks.*/
list= space(list, 0) /*Converts spaces to nulls. */
do while index(list, cc) > 0 /*any double commas ? */
list= changestr(cc, list, c) /*convert ,, to single comma.*/
end /*while*/
list= strip(list, 'T', c) /*strip the last trailing comma*/
list = '['list"]" /*repackage the list. */
say list /*display the flattened list. */
- output:
[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []] [1,2,3,4,5,6,7,8]
Ring
aString = "[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]"
bString = ""
cString = ""
for n=1 to len(aString)
if ascii(aString[n]) >= 48 and ascii(aString[n]) <= 57
bString = bString + ", " + aString[n]
ok
next
cString = substr(bString,3,Len(bString)-2)
cString = '"' + cString + '"'
see cString + nl
"1, 2, 3, 4, 5, 6, 7, 8"
RPL
Soberly recursive.
≪ IF DUP SIZE THEN { } 1 LAST FOR j OVER j GET IF DUP TYPE 5 == THEN FLATL END + NEXT SWAP DROP END ≫ ‘FLATL’ STO {{1} 2 {{3 4} 5} {{{}}} {{{6}}} 7 8 {}} FLATL
- Output:
1: { 1 2 3 4 5 6 7 8 }
Ruby
flatten
is a built-in method of Arrays
flat = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []].flatten
p flat # => [1, 2, 3, 4, 5, 6, 7, 8]
The flatten
method takes an optional argument, which dedicates the amount of levels to be flattened.
p flatten_once = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []].flatten(1)
# => [1, 2, [3, 4], 5, [[]], [[6]], 7, 8]
Rust
First we have to create a type that supports arbitrary nesting:
use std::{vec, mem, iter};
enum List<T> {
Node(Vec<List<T>>),
Leaf(T),
}
impl<T> IntoIterator for List<T> {
type Item = List<T>;
type IntoIter = ListIter<T>;
fn into_iter(self) -> Self::IntoIter {
match self {
List::Node(vec) => ListIter::NodeIter(vec.into_iter()),
leaf @ List::Leaf(_) => ListIter::LeafIter(iter::once(leaf)),
}
}
}
enum ListIter<T> {
NodeIter(vec::IntoIter<List<T>>),
LeafIter(iter::Once<List<T>>),
}
impl<T> ListIter<T> {
fn flatten(self) -> Flatten<T> {
Flatten {
stack: Vec::new(),
curr: self,
}
}
}
impl<T> Iterator for ListIter<T> {
type Item = List<T>;
fn next(&mut self) -> Option<Self::Item> {
match *self {
ListIter::NodeIter(ref mut v_iter) => v_iter.next(),
ListIter::LeafIter(ref mut o_iter) => o_iter.next(),
}
}
}
struct Flatten<T> {
stack: Vec<ListIter<T>>,
curr: ListIter<T>,
}
// Flatten code is a little messy since we are shoehorning recursion into an Iterator
impl<T> Iterator for Flatten<T> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
loop {
match self.curr.next() {
Some(list) => {
match list {
node @ List::Node(_) => {
self.stack.push(node.into_iter());
let len = self.stack.len();
mem::swap(&mut self.stack[len - 1], &mut self.curr);
}
List::Leaf(item) => return Some(item),
}
}
None => {
if let Some(next) = self.stack.pop() {
self.curr = next;
} else {
return None;
}
}
}
}
}
}
use List::*;
fn main() {
let list = Node(vec![Node(vec![Leaf(1)]),
Leaf(2),
Node(vec![Node(vec![Leaf(3), Leaf(4)]), Leaf(5)]),
Node(vec![Node(vec![Node(vec![])])]),
Node(vec![Node(vec![Node(vec![Leaf(6)])])]),
Leaf(7),
Leaf(8),
Node(vec![])]);
for elem in list.into_iter().flatten() {
print!("{} ", elem);
}
println!();
}
- Output:
1 2 3 4 5 6 7 8
S-lang
define flatten ();
define flatten (list) {
variable item,
retval,
val;
if (typeof(list) != List_Type) {
retval = list;
} else {
retval = {};
foreach item (list) {
foreach val (flatten(item)) {
list_append(retval, val);
}
}
}
return retval;
}
Sample:
slsh> variable data = {{1}, 2, {{3,4}, 5}, {{{}}}, {{{6}}}, 7, 8, {}}, result = flatten(data); slsh> print(result); { 1 2 3 4 5 6 7 8 }
Scala
def flatList(l: List[_]): List[Any] = l match {
case Nil => Nil
case (head: List[_]) :: tail => flatList(head) ::: flatList(tail)
case head :: tail => head :: flatList(tail)
}
Sample:
scala> List(List(1), 2, List(List(3, 4), 5), List(List(List())), List(List(List(6))), 7, 8, List()) res10: List[Any] = List(List(1), 2, List(List(3, 4), 5), List(List(List())), List(List(List(6))), 7, 8, List()) scala> flatList(res10) res12: List[Any] = List(1, 2, 3, 4, 5, 6, 7, 8)
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)
Shen
(define flatten
[] -> []
[X|Y] -> (append (flatten X) (flatten Y))
X -> [X])
(flatten [[1] 2 [[3 4] 5] [[[]]] [[[6]]] 7 8 []])
- Output:
[1 2 3 4 5 6 7 8]
Sidef
func flatten(a) {
var flat = []
a.each { |item|
flat += (item.kind_of(Array) ? flatten(item) : [item])
}
return flat
}
var arr = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]
say flatten(arr) # used-defined function
say arr.flatten # built-in Array method
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]].
].
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.
Here is a non-OOP (but functional) version, which uses a block-closure as function (showing higher order features of Smalltalk):
flatDo :=
[:element :action |
element isCollection ifTrue:[
element do:[:el | flatDo value:el value:action]
] ifFalse:[
action value:element
].
].
collection := {
{1} . 2 . { {3 . 4} . 5 } .
{{{}}} . {{{6}}} . 7 . 8 . {}
}.
newColl := OrderedCollection new.
flatDo
value:collection
value:[:el | newColl add: el]
of course, many Smalltalk libraries already provide such functionality.
collection flatDo:[:el | newColl add:el]
Standard ML
In Standard ML, list must be homogeneous, but nested lists can be implemented as a tree-like data structure using a datatype
statement:
datatype 'a nestedList =
L of 'a (* leaf *)
| N of 'a nestedList list (* node *)
Flattening of this structure is similar to flatten trees:
fun flatten (L x) = [x]
| flatten (N xs) = List.concat (map flatten xs)
- Output:
- flatten (N [ L 1, N [L 2, N []], L 3]); val it = [1,2,3] : int list
Suneido
ob = [[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]
ob.Flatten()
- Output:
#(1, 2, 3, 4, 5, 6, 7, 8)
SuperCollider
SuperCollider has the method "flat", which completely flattens nested lists, and the method "flatten(n)" to flatten a certain number of levels.
a = [[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []];
a.flatten(1); // answers [ 1, 2, [ 3, 4 ], 5, [ [ ] ], [ [ 6 ] ], 7, 8 ]
a.flat; // answers [ 1, 2, 3, 4, 5, 6, 7, 8 ]
Written as a function:
(
f = { |x|
var res = res ?? List.new;
if(x.isSequenceableCollection) {
x.do { |each|
res.addAll(f.(each))
}
} {
res.add(x);
};
res
};
f.([[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]);
)
Swift
Recursive
func list(s: Any...) -> [Any] {
return s
}
func flatten<T>(s: [Any]) -> [T] {
var r = [T]()
for e in s {
switch e {
case let a as [Any]:
r += flatten(a)
case let x as T:
r.append(x)
default:
assert(false, "value of wrong type")
}
}
return r
}
let s = list(list(1),
2,
list(list(3, 4), 5),
list(list(list())),
list(list(list(6))),
7,
8,
list()
)
println(s)
let result : [Int] = flatten(s)
println(result)
- Output:
[[1] 2 [[3 4] 5] [[[]]] [[[6]]] 7 8 []] [1 2 3 4 5 6 7 8]
More functionally:
func list(s: Any...) -> [Any] {
return s
}
func flatten<T>(s: [Any]) -> [T] {
return s.flatMap {
switch $0 {
case let a as [Any]:
return flatten(a)
case let x as T:
return [x]
default:
assert(false, "value of wrong type")
}
}
}
let s = list(list(1),
2,
list(list(3, 4), 5),
list(list(list())),
list(list(list(6))),
7,
8,
list()
)
println(s)
let result : [Int] = flatten(s)
println(result)
- Output:
[[1] 2 [[3 4] 5] [[[]]] [[[6]]] 7 8 []] [1 2 3 4 5 6 7 8]
Non-recursive
func list(s: Any...) -> [Any]
{
return s
}
func flatten<T>(array: [Any]) -> [T]
{
var result: [T] = []
var workstack: [(array: [Any], lastIndex: Int)] = [(array, 0)]
workstackLoop: while !workstack.isEmpty
{
for element in workstack.last!.array.suffixFrom(workstack.last!.lastIndex)
{
workstack[workstack.endIndex - 1].lastIndex++
if let element = element as? [Any]
{
workstack.append((element, 0))
continue workstackLoop
}
result.append(element as! T)
}
workstack.removeLast()
}
return result
}
let input = list(list(1),
2,
list(list(3, 4), 5),
list(list(list())),
list(list(list(6))),
7,
8,
list()
)
print(input)
let result: [Int] = flatten(input)
print(result)
- Output:
[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] [1, 2, 3, 4, 5, 6, 7, 8]
Tailspin
templates flatten
[ $ -> # ] !
when <[]> do
$... -> #
otherwise
$ !
end flatten
[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] -> flatten -> !OUT::write
- Output:
[1, 2, 3, 4, 5, 6, 7, 8]
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
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.)
Another implementation that's slightly more terse:
proc flatten {data} {
while { $data != [set data [join $data]] } { }
return $data
}
puts [flatten {{1} 2 {{3 4} 5} {{{}}} {{{6}}} 7 8 {}}]
# ===> 1 2 3 4 5 6 7 8
Trith
[[1] 2 [[3 4] 5] [[[]]] [[[6]]] 7 8 []] flatten
TXR
An important builtin.
@(bind foo ((1) 2 ((3 4) 5) ((())) (((6))) 7 8 ()))
@(bind bar foo)
@(flatten bar)
Run:
$ txr -a 5 flatten.txr # show variable bindings in array notation to depth 5 foo[0][0]="1" foo[1]="2" foo[2][0][0]="3" foo[2][0][1]="4" foo[2][1]="5" foo[4][0][0][0]="6" foo[5]="7" foo[6]="8" bar[0]="1" bar[1]="2" bar[2]="3" bar[3]="4" bar[4]="5" bar[5]="6" bar[6]="7" bar[7]="8"
Uiua
Keep joining elements until we're done.
⍥/◇⊂∞{{1} 2 {{3 4} 5} {{{}}} {{{6}}} 7 8 {}}
VBScript
Working on embedded arrays as that's about the closest we get to lists.
Implementation
class flattener
dim separator
sub class_initialize
separator = ","
end sub
private function makeflat( a )
dim i
dim res
for i = lbound( a ) to ubound( a )
if isarray( a( i ) ) then
res = res & makeflat( a( i ) )
else
res = res & a( i ) & separator
end if
next
makeflat = res
end function
public function flatten( a )
dim res
res = makeflat( a )
res = left( res, len( res ) - len(separator))
res = split( res, separator )
flatten = res
end function
public property let itemSeparator( c )
separator = c
end property
end class
Invocation
dim flat
set flat = new flattener
flat.itemSeparator = "~"
wscript.echo join( flat.flatten( array( array( 1 ),2,array(array(3,4),5),array(array(array())),array(array(array(6))),7,8,array())), "!")
- Output:
1!2!3!4!5!6!7!8
Alternative (classless) Version
' Flatten the example array...
a = FlattenArray(Array(Array(1), 2, Array(Array(3,4), 5), Array(Array(Array())), Array(Array(Array(6))), 7, 8, Array()))
' Print the list, comma-separated...
WScript.Echo Join(a, ",")
Function FlattenArray(a)
If IsArray(a) Then DoFlatten a, FlattenArray: FlattenArray = Split(Trim(FlattenArray))
End Function
Sub DoFlatten(a, s)
For i = 0 To UBound(a)
If IsArray(a(i)) Then DoFlatten a(i), s Else s = s & a(i) & " "
Next
End Sub
V (Vlang)
fn main() {
arr := "[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]"
println(convert(arr))
}
fn convert(arr string) []int {
mut new_arr := []int{}
for value in arr.replace_each(["[","","]",""]).split_any(", ") {if value !="" {new_arr << value.int()}}
return new_arr
}
- Output:
[1, 2, 3, 4, 5, 6, 7, 8]
Wart
Here's how Wart implements flatten
:
def (flatten seq acc)
if no.seq
acc
~list?.seq
(cons seq acc)
:else
(flatten car.seq (flatten cdr.seq acc))
- Output:
(flatten '((1) 2 ((3 4) 5) ((())) (((6))) 7 8 ())) => (1 2 3 4 5 6 7 8)
WDTE
let a => import 'arrays';
let s => import 'stream';
let flatten array =>
a.stream array
-> s.flatMap (@ f v => v {
reflect 'Array' => a.stream v -> s.flatMap f;
})
-> s.collect
;
Usage:
flatten [[1]; 2; [[3; 4]; 5]; [[[]]]; [[[6]]]; 7; 8; []] -- io.writeln io.stdout;
- Output:
[1; 2; 3; 4; 5; 6; 7; 8]
Wren
A method already exists for this operation in the above module.
import "./seq" for Lst
var a = [[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []]
System.print(Lst.flatten(a))
- Output:
[1, 2, 3, 4, 5, 6, 7, 8]
zkl
fcn flatten(list){ list.pump(List,
fcn(i){ if(List.isType(i)) return(Void.Recurse,i,self.fcn); i}) }
flatten(L(L(1), L(2), L(L(3,4), 5), L(L(L())), L(L(L(6))), 7, 8, L()))
//-->L(1,2,3,4,5,6,7,8)
This works by recursively writing the contents of lists to a new list. If a list is recursive or cyclic, it will blow the stack and throw an exception.
- Programming Tasks
- Solutions by Programming Task
- 8th
- ACL2
- ActionScript
- Ada
- Aikido
- Aime
- ALGOL 68
- APL
- AppleScript
- Arturo
- AutoHotkey
- BASIC
- BaCon
- BASIC256
- Chipmunk Basic
- FreeBASIC
- Gambas
- GW-BASIC
- MSX Basic
- PureBasic
- QBasic
- Run BASIC
- Run BASIC examples needing attention
- Examples needing attention
- TI-89 BASIC
- True BASIC
- XBasic
- Yabasic
- ZX Spectrum Basic
- ZX Spectrum Basic examples needing attention
- BQN
- Bracmat
- Brat
- Burlesque
- C
- C sharp
- C++
- Ceylon
- Clojure
- CoffeeScript
- Common Lisp
- Crystal
- D
- Déjà Vu
- E
- EchoLisp
- Ela
- Elixir
- Elm
- Emacs Lisp
- Erlang
- Euphoria
- F Sharp
- Factor
- Fantom
- Forth
- Fortran
- Frink
- FutureBasic
- GAP
- GNU APL
- Go
- Groovy
- Haskell
- Hy
- Icon
- Unicon
- Icon Programming Library
- Insitux
- Ioke
- Isabelle
- J
- Java
- JavaScript
- Joy
- Jq
- Jsish
- Julia
- K
- Kotlin
- Lambdatalk
- Lasso
- LFE
- Logo
- Logtalk
- Lua
- Maple
- Mathematica
- Wolfram Language
- Maxima
- Mercury
- Min
- Mirah
- NewLISP
- NGS
- Nim
- Objective-C
- OCaml
- Oforth
- Ol
- OoRexx
- Oz
- PARI/GP
- PascalABC.NET
- Perl
- Phix
- Phixmonti
- PHP
- PicoLisp
- Pike
- PL/I
- PostScript
- Initlib
- PowerShell
- Prolog
- Python
- Q
- Quackery
- R
- Racket
- Raku
- REBOL
- Red
- Refal
- REXX
- Ring
- RPL
- Ruby
- Rust
- S-lang
- Scala
- Scheme
- Shen
- Sidef
- Slate
- Smalltalk
- Standard ML
- Suneido
- SuperCollider
- Swift
- Tailspin
- Tcl
- Trith
- UNIX Shell/Omit
- TXR
- Uiua
- VBScript
- V (Vlang)
- Wart
- WDTE
- Wren
- Wren-seq
- Zkl
- Pages with too many expensive parser function calls