StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I'm guessing this is homework. On the assumption that it is, then here's some ideas for how to think about the problem that might lead you to an answer:</p> <p>In <code>preorder</code>, first the current item is "reported", then recurse for all this node's tails. In <code>postorder</code> these two steps are done in reverse. In both cases, the recursion is "local", in the sense that it only need deal with one node at a time. Is this true for <code>levelorder</code>? Or to ask it another way, when <code>levelorder</code> recurses, do the results of the recursions interact or no? If so, then, what is the "unit" of recursion, if not a single <code>Tree</code>?</p> <p>Understanding the nature of the recursion (or iteration..?) of <code>levelorder</code> will lead you to a solution that very simple and elegant. My version is only three lines long!</p> <p>By the way, it might be nice to have these utility functions to make the code even clearer in some places:</p> <pre><code>element :: Tree a -> a element (Nd x _) = x subtrees :: Tree a -> [Tree a] subtrees (Nd _ s) = s </code></pre> <p>Or, if you are familiar with record syntax in Haskell, you can achieve exactly this by changing your original <code>Tree</code> definition to:</p> <pre><code>data Tree a = Nd { element :: a, subtrees :: [Tree a] } deriving Show </code></pre> <hr> <p><strong>A full solution:</strong></p> <p>The key is realizing that <code>levelorder</code> requires recursion on a list of <code>Tree</code>. At each step the elements from each <code>Tree</code> is extracted, and the next step is upon the concatenation of the subtrees:</p> <pre><code>levelorder :: Tree a -> [a] levelorder t = step [t] where step [] = [] step ts = map element ts ++ step (concatMap subtrees ts) </code></pre> <p>This produces the elements in a single, flattened list, much like <code>preorder</code> and <code>postorder</code> do, and is the usual definition of a breadth-first traversal.</p> <p>If instead you really want the elements grouped by level, a single change of the <code>++</code> operator to <code>:</code> will yield that version:</p> <pre><code>bylevel :: Tree a -> [[a]] bylevel t = step [t] where step [] = [] step ts = map element ts : step (concatMap subtrees ts) </code></pre> <p>Note: I have given type signatures for all top-level functions. This is a really good habit to get into, and will save you considerable time debugging.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload