How to create a function in ML using a Recursive Datatype

Question

Given the datatypes:

datatype bunch = One of int
               | Group of bunch list;
datatype 'ex bunch = NIL
                   | One of 'ex
                   | Group of 'ex * 'ex bunch;

How can I design a function to, for example, return the sum of this recursive function. I understand how to define a recursive function and slightly how to use it, but I cannot find an indication of how the 'ex changes the datatype bunch online, or any of my other references.

Answer 1

Your second definition makes the bunch data structure polymorphic, i.e., it can contain data of any type. For example Group (3, One 2) is an int bunch, and Group ("three", One "two") is a string bunch. The value NIL has the type 'a bunch where 'a stands for any type (i.e. NIL has the type int bunch and the type string bunch and ...).

Your goal to ”return the sum of this recursive function” doesn't make sense: you don't have a recursive function. If you meant ”return the sum of this recursive data structure”, it's still not clear what you want, you need to be more precise about what you mean by sum for a data structure that is not a collection of numbers.

The following function computes the sum of the integers in an int bunch. As you can see by typing it into an ML interpreter, its type is int bunch -> int, that is, it can only act on bunches of integer (otherwise the + operator wouldn't make sense).

fun bunch_sum NIL = 0
  | bunch_sum (One x) = x
  | bunch_sum (Group (x, b)) = x + bunch_sum b;

The following function computes the number of elements in a bunch with any element type (as shown by its type 'a bunch -> int). The reason you can define such a polymorphic function is that it doesn't need to look inside the elements of the bunch to operate: it is parametrically polymorphic.

fun bunch_count NIL = 0
  | bunch_count (One x) = 1
  | bunch_count (Group (x, b)) = 1 + bunch_count b;

(In a production program, such functions should be written in a less clear but less resource-hungry way, using a tail recursive algorithm.)

Since the bunch type is almost isomorphic to lists, you can look at the source of your implementation's standard list library for inspiration.