September 22, 1999

Strong Typing

Slide #31

Where's the Bug?

Suppose we're trying to sort a one-element list [x] .

We split it with split into ([x], []).

Then we try to sort these two lists and merge the sorted lists back together.

Sorting [] is OK.

Sorting [x] puts us into an infinite loop.

Solution: Add a clause

          ...
        | sort [x] = [x]
          ...

Type becomes

        val sort = fn : int list -> int list

We could make it a little better:

        val sort = fn : ('a * 'a -> bool) -> 'a list -> 'a list