What does “flatten” mean

naming

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?

Best Answer

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]