17

If I had a tree, would "flatten" intuitively imply

get a list of all items in the tree, traversing from left to right?

If i have a linked list, would "flatten" intuitively imply

get a list of all items, starting with this one

For example, a linked list would be made up of an exception that aggregates its inner exception. Would it be fair to name a method on exception "flattenInnerExceptions" with expectation that it would return a sequence of exceptions, outermost exception first, and inner-most exception -- last?

Walter
  • 16,146
GregC
  • 311
  • 1
  • 2
  • 9

1 Answers1

28

If I had a list of lists, “flatten” would be the operation that returns a list of all the leaf elements in order, i.e., something that changes:

[[a, b, c], [d, e, f], [g, h i]]

Into

[a, b, c, d, e, f, g, h, i]

For trees, flatting is generating a list of all leaves in natural traversal order (NB: since only leaves are in the result, it doesn't matter whether you think of this as pre-, in- or post-order traversal.)

As a consequence, for a simple list the “flatten” operation is by definition an identity transformation.

Flattening can be performed in stages, or degrees. For instance:

[[[a, b], [c, d]], [[e, f], [g, h]]]

can be flattened to:

[[a, b, c, d], [e, f, g, h]]

and then to:

 [a, b, c, d, e, f, g, h]
Donal Fellows
  • 6,407
  • @Donal Fellows: This addresses the half of the question about trees. What about linked lists? Is it intuitive to talk about them with the term "Flatten?" – GregC Apr 23 '11 at 16:23
  • @GregC, perhaps you would like to add an example of what you consider a linked list to be. –  Apr 23 '11 at 16:36
  • Edited the question with an example. – GregC Apr 23 '11 at 16:43
  • 3
    @GregC: A linked list is just an implementation of a sequence abstract type. (An array is also an implementation of that abstract type on at least one level, and yes there are significant differences; abstract types aren't the whole story.) Most memory allocation systems make linked lists fairly expensive due to the fact that you're paying the memory allocation overhead per list cell (that overhead's often about 8 bytes on a 32-bit system) so I wouldn't recommend using them unless you've got a need for constant-time inserts and deletes. – Donal Fellows Apr 24 '11 at 13:56
  • @Donal Wouldn't [[[a, b], [c, d]], [[e, f], [g, h]]] flatten to [[a, b], [c, d], [e, f], [g, h]] and not to [[a, b, c, d], [e, f, g, h]]? – Baris Demiray Jan 16 '19 at 09:30
  • 1
    @BarisDemiray Yes. That would be the result of first level flattening, and the other would be after two rounds… – Donal Fellows Aug 20 '19 at 18:20