Search code examples
treesml

SML Traverse an N-ary tree

I'm a newbie to SML.

After a couple of searches, I still can't find any resource related to traversing an n-ary tree. Many examples are just traversing a simple binary tree.

Say, I have

datatype 'a tree = leaf of 'a list | node of 'a tree list

I want to traverse this n-ary tree and have the exactly same tree returned (val traverse = fn : 'a tree -> 'a tree)

How can I do?

Here's my code:

fun traverse (leaf x) = (leaf x)
  | traverse (node []) = node []
  | traverse (node [x]) = node [x]

I'm struggling to add the last pattern, i.e., (this is wrong)

  | traverse (node (x::xs)) = traverse (node x) :: traverse (xs)

Thanks for your helping.

Solution

  • Since traverse is a function from trees to trees, you can traverse all the subtrees in the list with map (and you don't need special cases):

    fun traverse (leaf x) = leaf x
  | traverse (node xs) = node (map traverse xs)