Problem 72

Collect the nodes of a multiway tree in depth-first order.

Example

toList tree70 == ['g', 'f', 'c', 'd', 'e', 'b', 'a']

Unit Test

import Html
import List


type MTree a
    = MNode a (List (MTree a))


toList : MTree a -> List a
toList (MNode v list) =
    -- your implementation goes here
    []


main =
    Html.text
        (if (test) then
            "Your implementation passed all tests."
         else
            "Your implementation failed at least one test."
        )


test : Bool
test =
    List.all ((==) True)
        [ toList (MNode 1 []) == [ 1 ]
        , toList mtree70 == [ 'g', 'f', 'c', 'd', 'e', 'b', 'a' ]
        , toList test3 == [ '5', '4', '3', '2', '1' ]
        , toList test4 == [ 'f', 'g', 'h', 'i', 'a' ]
        , toList test5 == [ 'f', 'g', 'h', 'i', 'a', '4', '3', '2', '1' ]
        ]


mtree70 =
    MNode 'a'
        [ MNode 'f' [ MNode 'g' [] ]
        , MNode 'c' []
        , MNode 'b' [ MNode 'd' [], MNode 'e' [] ]
        ]


test3 =
    MNode '1' [ MNode '2' [ MNode '3' [ MNode '4' [ MNode '5' [] ] ] ] ]


test4 =
    MNode 'a' [ MNode 'f' [], MNode 'g' [], MNode 'h' [], MNode 'i' [] ]


test5 =
    MNode '1' [ MNode '2' [ MNode '3' [ MNode '4' [ test4 ] ] ] ]

Hint

1. Depth-first again?
2. List.concatMap could make the solution very concise.

Solution

Solution