CODEWITHSUNDEEP
treesml
Humber
Humber

Reputation: 5

SML using reduce and map to traverse an n-ary tree

I'm new to SML.

Say I have the following datatype:

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

and the function val leaves = fn : 'a tree -> 'a list:

fun leaves (leaf x) = [x]
  | leaves (node []) = []
  | leaves (node [x]) = leaves x
  | leaves (node (x::xs)) = (leaves x) @ (leaves (node xs))

If I have

val t = node [node [leaf 1,
              node [leaf 2, leaf 3],
              leaf 4]];

Then, leaves t will return [1, 2, 3, 4] for me.

What I want to ask is that, does this is possible to be rewritten by using reduce and map?

Given reduce:

fun reduce g [x] = x
  | reduce g (x::xs) = (g x (reduce g xs))

Thank you very much.

Upvotes: 0

Views: 507

Answers (2)

molbdnilo
molbdnilo

Reputation: 66371

You seem to have a recurring pattern of starting with too many clauses.

Start with the two necessary ones:

fun leaves (leaf x) = [x]
  | leaves (node xs) = ???

Now, xs is a list.
map transforms a list into a different list.
reduce reduces a list to a single value.

This suggests that you want something of the form

| leaves (node xs) = reduce f (map g xs)

Determining f and g left as an exercise.

Upvotes: 1

sshine
sshine

Reputation: 16105

In ML there is a convention, not enforced by syntax in SML, to have data constructors begin with uppercase and values (including functions) begin with lowercase. In pattern matching this makes them more easily distinguishable, since syntactically, node could be either a data constructor or a variable, it's not possible to tell without inspecting the whole code.

StackOverflow tends to agree with us, since its syntax highlighter isn't very context-aware and can't paint the data constructors a special color unless we follow this convention.

So:

datatype 'a tree = Leaf of 'a | Node of 'a tree list

molbdnilo already showed how you can simplify the patterns in leaves down two:

fun leaves (Leaf x) = [x]
  | leaves (Node ts) = ???

(Note that I changed the casing of the constructors and renamed xs into ts because it's a list of trees.)

To complete this function using recursion, I would say that you could go in two ways here. As you will see, there are trade-offs in both directions, which I'll mention:

  • Stick with two patterns and handle recursion on xs in a separate, mutually recursive function:

    fun leaves (Leaf x) = [x]
  | leaves (Node ts) = nodes ts

and nodes [] = []
  | nodes (t::ts) = leaves n @ nodes ts

    Having two functions that may call one another is just a bit mind-bending. You have to keep reminding yourself that t is a tree, so leaves should be called on that, but ts is a list of trees, so nodes should be called on that. But besides using and instead of fun on subsequent, mutually recursive functions, the syntax is not that bad.

  • Go to three patterns and handle recursion of both the tree and its inner lists by matching two levels deep:

    fun leaves (Leaf x) = [x]
  | leaves (Node []) = []
  | leaves (Node (t::ts)) = leaves t @ leaves (Node ts)

    Having just one function seems simpler, but the downside is that pattern matching gets a bit more tricky: You don't just match that the input is a Node, but specifically that it's a Node with either no children (Node []) or a node with at least one child (Node (t::ts)). The complexity here is that while you pattern matched successfully to deconstruct a single t that can be passed recursively to leaves (leaves t), handling the rest of ts (an 'a tree list), you don't have a function that handles such a list. But you almost do: If you put back the Node on ts (Node ts), you get an 'a tree with that list of child nodes. And you do have a function for handling one tree.

You can decide for yourself over time which idea is harder to work with.

Maybe it turns out you like both for different occasions.

What I want to ask is that, does this is possible to be rewritten by using reduce and map?

Yes.

Upvotes: 0

Related Questions