Flattening a list of nested sublists

I recently posted a technique for flattening a list of nested sublists. It appeared at the end of a long Code Exchange article that had begun as a discussion of list flattening but then devoted a large amount of its discussion to an alternative topic. I thought that the newly posted technique was useful enough that it should perhaps be “flattened” and posted at the “top level” of Code Exchange.

In the prior post, I reviewed a few previously described list-flattening solutions. One consists of a text-item-delimiters technique that is applicable to the case where all list and sublist items are text strings. Another technique uses recursive handler calls that is broadly applicable but runs the risk of a stack overflow error if a deeply nested list requires too many recursive handler calls. A third method uses ASObjC’s NSArray and its unionOfArrays operator that is applicable to the very specific case where all list items are themselves lists, and nesting is only one level deep.

The current technique will flatten a list of nested sublists of items of any class and nesting depth, and it does not entail the risk of a stack overflow error. It leverages the fact that AppleScript’s list concatenation operator effectively raises a sublist by one nesting depth. For example, when the sublist {1, 2, {3, 4, {5, 6}}} is concatenated to another list with the command: set newList to newList & {1, 2, {3, 4, {5, 6}}}, the new list becomes {…, 1, 2, {3, 4, {5, 6}}, …}, with the sublist’s top-level items now flattened, and lower-level items raised by one nesting depth. By repeatedly applying list concatenation to the list’s items, the list becomes progressively flattened until it reaches the point where all of its items are at the top level, and no nested sublists remain. As mentioned before, lists are processed as script properties in the repeat loops to enhance execution speed.

Handler:


on flattenList(theList)
	script util
		property flattenedList : theList
		property interimFlattenedList : missing value
	end script
	repeat while util's flattenedList's lists's length > 0
		set util's interimFlattenedList to {}
		repeat with currItem in util's flattenedList
			tell currItem's contents
				if its class = list then
					set util's interimFlattenedList to util's interimFlattenedList & it
				else
					set end of util's interimFlattenedList to it
				end if
			end tell
		end repeat
		set util's flattenedList to util's interimFlattenedList
	end repeat
	return util's flattenedList as list -- "as list" assures that the return value is dereferenced
end flattenList

Examples:


set theList to {1, 2, {{3, {4, 5}, 6}, 7}, 8}

flattenList(theList)
--> {1, 2, 3, 4, 5, 6, 7, 8}

set deeplyNestedList to {1, {2, {3, {4, {5, {6, {7, {8, {9, {10, {11, {12, {13, {14, {15, {16, {17, {18, {19, {20, {21, {22, {23, {24, {25, {26, {27, {28, {29, {30, {31, {32, {33, {34, {35, {36, {37, {38, {39, {40, {41, {42, {43, {44, {45, {46, {47, {48, {49, {50, {51, {52, {53, {54, {55, {56, {57, {58, {59, {60, {61, {62, {63, {64, {65, {66, {67, {68, {69, {70, {71, {72, {73, {74, {75, {76, {77, {78, {79, {80, {81, {82, {83, {84, {85, {86, {87, {88, {89, {90, {91, {92, {93, {94, {95, {96, {97, {98, {99, {100, {101, {102, {103, {104, {105, {106, {107, {108, {109, {110, {111, {112, {113, {114, {115, {116, {117, {118, {119, {120, {121, {122, {123, {124, {125, {126, {127, {128, {129, {130, {131, {132, {133, {134, {135, {136, {137, {138, {139, {140, {141, {142, {143, {144, {145, {146, {147, {148, {149, {150, {151, {152, {153, {154, {155, {156, {157, {158, {159, {160, {161, {162, {163, {164, {165, {166, {167, {168, {169, {170, {171, {172, {173, {174, {175, {176, {177, {178, {179, {180, {181, {182, {183, {184, {185, {186, {187, {188, {189, {190, {191, {192, {193, {194, {195, {196, {197, {198, {199, {200, {201, {202, {203, {204, {205, {206, {207, {208, {209, {210, {211, {212, {213, {214, {215, {216, {217, {218, {219, {220, {221, {222, {223, {224, {225, {226, {227, {228, {229, {230, {231, {232, {233, {234, {235, {236, {237, {238, {239, {240, {241, {242, {243, {244, {245, {246, {247, {248, {249, {250, {251, {252, {253, {254, {255, {256}, 257}}, 258}}, 259}}, 260}}, 261}}, 262}}, 263}}, 264}}, 265}}, 266}}, 267}}, 268}}, 269}}, 270}}, 271}}, 272}}, 273}}, 274}}, 275}}, 276}}, 277}}, 278}}, 279}}, 280}}, 281}}, 282}}, 283}}, 284}}, 285}}, 286}}, 287}}, 288}}, 289}}, 290}}, 291}}, 292}}, 293}}, 294}}, 295}}, 296}}, 297}}, 298}}, 299}}, 300}}, 301}}, 302}}, 303}}, 304}}, 305}}, 306}}, 307}}, 308}}, 309}}, 310}}, 311}}, 312}}, 313}}, 314}}, 315}}, 316}}, 317}}, 318}}, 319}}, 320}}, 321}}, 322}}, 323}}, 324}}, 325}}, 326}}, 327}}, 328}}, 329}}, 330}}, 331}}, 332}}, 333}}, 334}}, 335}}, 336}}, 337}}, 338}}, 339}}, 340}}, 341}}, 342}}, 343}}, 344}}, 345}}, 346}}, 347}}, 348}}, 349}}, 350}}, 351}}, 352}}, 353}}, 354}}, 355}}, 356}}, 357}}, 358}}, 359}}, 360}}, 361}}, 362}}, 363}}, 364}}, 365}}, 366}}, 367}}, 368}}, 369}}, 370}}, 371}}, 372}}, 373}}, 374}}, 375}}, 376}}, 377}}, 378}}, 379}}, 380}}, 381}}, 382}}, 383}}, 384}

flattenList(deeplyNestedList)
--> {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255, 256, 257, 258, 259, 260, 261, 262, 263, 264, 265, 266, 267, 268, 269, 270, 271, 272, 273, 274, 275, 276, 277, 278, 279, 280, 281, 282, 283, 284, 285, 286, 287, 288, 289, 290, 291, 292, 293, 294, 295, 296, 297, 298, 299, 300, 301, 302, 303, 304, 305, 306, 307, 308, 309, 310, 311, 312, 313, 314, 315, 316, 317, 318, 319, 320, 321, 322, 323, 324, 325, 326, 327, 328, 329, 330, 331, 332, 333, 334, 335, 336, 337, 338, 339, 340, 341, 342, 343, 344, 345, 346, 347, 348, 349, 350, 351, 352, 353, 354, 355, 356, 357, 358, 359, 360, 361, 362, 363, 364, 365, 366, 367, 368, 369, 370, 371, 372, 373, 374, 375, 376, 377, 378, 379, 380, 381, 382, 383, 384}

Of note, the second example involving a very deeply nested list caused a stack overflow error with two different recursive-handler-call solutions I tried, but runs without problems with the current handler.

Hi bmose.

Just to point out that the recursive handler to which you’ve linked handles your 256-level list structure with ease. :slight_smile: And you’d have to try pretty hard to get lists nested that deep in the first place!

The key word here is “effectively”, to which should be added “in this context”. Concatenation doesn’t actually raise the level of a list’s items. It creates a new list containing the items from the left hand list and those from the right. It’s an expensive business when carried out repeatedly. Your method’s possibly better suited to long, shallowly-nested list structures.

Hi Nigel,

Yes, you are correct that your handler works with the deeply nested list shown above! My apologies for not testing the list on your handler first. I tried the list on two recursion handler variants I had written, and they both failed with stack overflow errors. Furthermore, while my handler executes fairly briskly, your handler executes even more quickly on that nested list.

Of course, the recursion technique will fail with a stack overflow error if the nesting is pushed deeply enough. For example, the following list, which was constructed by copying the deeply nested list to its own deepest level (!), does cause the recursive handler to fail with a stack overflow error:


set veryDeeplyNestedList to {1, {2, {3, {4, {5, {6, {7, {8, {9, {10, {11, {12, {13, {14, {15, {16, {17, {18, {19, {20, {21, {22, {23, {24, {25, {26, {27, {28, {29, {30, {31, {32, {33, {34, {35, {36, {37, {38, {39, {40, {41, {42, {43, {44, {45, {46, {47, {48, {49, {50, {51, {52, {53, {54, {55, {56, {57, {58, {59, {60, {61, {62, {63, {64, {65, {66, {67, {68, {69, {70, {71, {72, {73, {74, {75, {76, {77, {78, {79, {80, {81, {82, {83, {84, {85, {86, {87, {88, {89, {90, {91, {92, {93, {94, {95, {96, {97, {98, {99, {100, {101, {102, {103, {104, {105, {106, {107, {108, {109, {110, {111, {112, {113, {114, {115, {116, {117, {118, {119, {120, {121, {122, {123, {124, {125, {126, {127, {128, {129, {130, {131, {132, {133, {134, {135, {136, {137, {138, {139, {140, {141, {142, {143, {144, {145, {146, {147, {148, {149, {150, {151, {152, {153, {154, {155, {156, {157, {158, {159, {160, {161, {162, {163, {164, {165, {166, {167, {168, {169, {170, {171, {172, {173, {174, {175, {176, {177, {178, {179, {180, {181, {182, {183, {184, {185, {186, {187, {188, {189, {190, {191, {192, {193, {194, {195, {196, {197, {198, {199, {200, {201, {202, {203, {204, {205, {206, {207, {208, {209, {210, {211, {212, {213, {214, {215, {216, {217, {218, {219, {220, {221, {222, {223, {224, {225, {226, {227, {228, {229, {230, {231, {232, {233, {234, {235, {236, {237, {238, {239, {240, {241, {242, {243, {244, {245, {246, {247, {248, {249, {250, {251, {252, {253, {254, {255, {256, {1, {2, {3, {4, {5, {6, {7, {8, {9, {10, {11, {12, {13, {14, {15, {16, {17, {18, {19, {20, {21, {22, {23, {24, {25, {26, {27, {28, {29, {30, {31, {32, {33, {34, {35, {36, {37, {38, {39, {40, {41, {42, {43, {44, {45, {46, {47, {48, {49, {50, {51, {52, {53, {54, {55, {56, {57, {58, {59, {60, {61, {62, {63, {64, {65, {66, {67, {68, {69, {70, {71, {72, {73, {74, {75, {76, {77, {78, {79, {80, {81, {82, {83, {84, {85, {86, {87, {88, {89, {90, {91, {92, {93, {94, {95, {96, {97, {98, {99, {100, {101, {102, {103, {104, {105, {106, {107, {108, {109, {110, {111, {112, {113, {114, {115, {116, {117, {118, {119, {120, {121, {122, {123, {124, {125, {126, {127, {128, {129, {130, {131, {132, {133, {134, {135, {136, {137, {138, {139, {140, {141, {142, {143, {144, {145, {146, {147, {148, {149, {150, {151, {152, {153, {154, {155, {156, {157, {158, {159, {160, {161, {162, {163, {164, {165, {166, {167, {168, {169, {170, {171, {172, {173, {174, {175, {176, {177, {178, {179, {180, {181, {182, {183, {184, {185, {186, {187, {188, {189, {190, {191, {192, {193, {194, {195, {196, {197, {198, {199, {200, {201, {202, {203, {204, {205, {206, {207, {208, {209, {210, {211, {212, {213, {214, {215, {216, {217, {218, {219, {220, {221, {222, {223, {224, {225, {226, {227, {228, {229, {230, {231, {232, {233, {234, {235, {236, {237, {238, {239, {240, {241, {242, {243, {244, {245, {246, {247, {248, {249, {250, {251, {252, {253, {254, {255, {256}, 257}}, 258}}, 259}}, 260}}, 261}}, 262}}, 263}}, 264}}, 265}}, 266}}, 267}}, 268}}, 269}}, 270}}, 271}}, 272}}, 273}}, 274}}, 275}}, 276}}, 277}}, 278}}, 279}}, 280}}, 281}}, 282}}, 283}}, 284}}, 285}}, 286}}, 287}}, 288}}, 289}}, 290}}, 291}}, 292}}, 293}}, 294}}, 295}}, 296}}, 297}}, 298}}, 299}}, 300}}, 301}}, 302}}, 303}}, 304}}, 305}}, 306}}, 307}}, 308}}, 309}}, 310}}, 311}}, 312}}, 313}}, 314}}, 315}}, 316}}, 317}}, 318}}, 319}}, 320}}, 321}}, 322}}, 323}}, 324}}, 325}}, 326}}, 327}}, 328}}, 329}}, 330}}, 331}}, 332}}, 333}}, 334}}, 335}}, 336}}, 337}}, 338}}, 339}}, 340}}, 341}}, 342}}, 343}}, 344}}, 345}}, 346}}, 347}}, 348}}, 349}}, 350}}, 351}}, 352}}, 353}}, 354}}, 355}}, 356}}, 357}}, 358}}, 359}}, 360}}, 361}}, 362}}, 363}}, 364}}, 365}}, 366}}, 367}}, 368}}, 369}}, 370}}, 371}}, 372}}, 373}}, 374}}, 375}}, 376}}, 377}}, 378}}, 379}}, 380}}, 381}}, 382}}, 383}}, 384}}, 257}}, 258}}, 259}}, 260}}, 261}}, 262}}, 263}}, 264}}, 265}}, 266}}, 267}}, 268}}, 269}}, 270}}, 271}}, 272}}, 273}}, 274}}, 275}}, 276}}, 277}}, 278}}, 279}}, 280}}, 281}}, 282}}, 283}}, 284}}, 285}}, 286}}, 287}}, 288}}, 289}}, 290}}, 291}}, 292}}, 293}}, 294}}, 295}}, 296}}, 297}}, 298}}, 299}}, 300}}, 301}}, 302}}, 303}}, 304}}, 305}}, 306}}, 307}}, 308}}, 309}}, 310}}, 311}}, 312}}, 313}}, 314}}, 315}}, 316}}, 317}}, 318}}, 319}}, 320}}, 321}}, 322}}, 323}}, 324}}, 325}}, 326}}, 327}}, 328}}, 329}}, 330}}, 331}}, 332}}, 333}}, 334}}, 335}}, 336}}, 337}}, 338}}, 339}}, 340}}, 341}}, 342}}, 343}}, 344}}, 345}}, 346}}, 347}}, 348}}, 349}}, 350}}, 351}}, 352}}, 353}}, 354}}, 355}}, 356}}, 357}}, 358}}, 359}}, 360}}, 361}}, 362}}, 363}}, 364}}, 365}}, 366}}, 367}}, 368}}, 369}}, 370}}, 371}}, 372}}, 373}}, 374}}, 375}}, 376}}, 377}}, 378}}, 379}}, 380}}, 381}}, 382}}, 383}}, 384}

Here is my non-recursive script cleaned-up, sped-up, and will have no problems with a deeply nested list.

property maxItems : 1000

set numberList to {}
set anitem to numberList
repeat with i from 1 to maxItems - 1
	set end of anitem to i
	set end of anitem to {}
	set anitem to item 2 of anitem
end repeat
set end of anitem to maxItems
set numberList to flattenList(numberList)
return numberList

-- Function to flatten a nested list
on flattenList(theList) -- non-recursive
	script U
		property flattenedList : theList
		property interimFlattenedList : missing value
	end script
	--=U
	repeat while (count U's flattenedList's lists) > 0
		set U's interimFlattenedList to {}
		repeat with currItem in U's flattenedList
			if (class of currItem) = list then
				set U's interimFlattenedList to U's interimFlattenedList & currItem's contents
			else
				set end of U's interimFlattenedList to currItem's contents
			end if
		end repeat
		set U's flattenedList to U's interimFlattenedList
	end repeat
	return U's flattenedList
end flattenList