CODEWITHSUNDEEP
listsml
user2016445
user2016445

Reputation: 113

Check whether a list of pairs is unsorted

I have a problem with the following code:

fun unsorted cmp ((x, y)::[]) = false
  | unsorted cmp ((x, y)::xx::xs) =
    if cmp(y, xx) = GREATER then true else unsorted cmp (xx::xs)

I just want that this function returns true if the list is unsorted and false otherwise. This should work for a list of pairs compared by the second component.

Here is my correct code for a plain list:

fun unsorted' cmp [] = false
  | unsorted' cmp (x::[]) = false
  | unsorted' cmp (x::xx::xs) =
    if cmp(x, xx) = GREATER then true else unsorted' cmp (xx::xs)

but where is my mistake with the list of pairs?

Upvotes: 0

Views: 244

Answers (1)

okonomichiyaki
okonomichiyaki

Reputation: 8485

The problem is in your call to cmp. Here's the inferred type for your working version of unsorted: ('a * 'a -> order) -> 'a list -> bool

It takes a comparison function (with type 'a * 'a -> order) and a list containing elements whose type is 'a. You then pattern match the list using the following pattern: (x::xx::xs) so both x and xx are bound to values of type 'a, and xs is bound to a list of 'a. Then you call cmp with a 2-tuple, which has the type 'a * 'a: cmp(x,xx).

In your other version, you want to work on a list of pairs (ie a value of type 'a * 'a list) and so you're using a different pattern: ((x,y)::xx::xs). In this case, x and y are both bound to values of type 'a but xx is bound to a pair, with type 'a * 'a. So in your call to cmp, this is the type of the parameter: 'a * ('a * 'a). Remember that in ML all functions take a single argument, and multiple arguments are achieved by passing tuples or currying, both of which you are using in this example. (cmp takes a tuple, and unsorted is curried)

Try using the following patterns in your new version:

fun unsorted cmp ((x,y)::[]) = ...
  | unsorted cmp ((x,y)::(xx,yy)::xs) = ...

... and see how far you get as you try to complete the function.

Upvotes: 1

Related Questions