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?

1 Answer 1

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]
6
  • @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, 2011 at 16:23
  • @GregC, perhaps you would like to add an example of what you consider a linked list to be.
    – user1249
    Apr 23, 2011 at 16:36
  • Edited the question with an example.
    – GregC
    Apr 23, 2011 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. Apr 24, 2011 at 13:56
  • 1
    @BarisDemiray Yes. That would be the result of first level flattening, and the other would be after two rounds… Aug 20, 2019 at 18:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.