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

Next Copyright © 1999 M-J. Dominus