Thursday, January 5, 2012

What does flattening list of items into tree means

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]

0 comments:

Post a Comment