Quick Sort Error using SML

Question

I learned SML last week so I tried to make Quicksort code to understand it well. My code is:

fun quicksort(l: int list) =
    if length l < 2
    then l
    else let fun split(l:int list, v: int) =
        if null l
        then ([], [])
        else if v > hd l
        then ((hd l)::(#1 split(tl l, v)), #2 split(tl l, v))
        else (#1 split(tl l, v), (hd l)::(#2 split(tl l, v)))
    in
        (#1 split(quicksort(tl l), hd l)) @ ((hd l)::(#2 split(quicksort(tl l), hd l)))
    end

and this is the error message:

Standard ML of New Jersey v110.75 [built: Sat Sep 29 12:51:13 2012]
- stdIn:21.18-21.35 Error: operator and operand don't agree [type mismatch]
  operator domain: {1:'Y; 'Z}
  operand:         int list * int -> 'X
  in expression:
    (fn {1=1,...} => 1) split
stdIn:21.8-21.56 Error: operator and operand don't agree [type mismatch]
  operator domain: {2:'Y; 'Z}
  operand:         int list * int -> 'X
  in expression:
    (fn {2=2,...} => 2) split
stdIn:22.8-22.56 Error: operator and operand don't agree [type mismatch]
  operator domain: {1:'Y; 'Z}
  operand:         int list * int -> 'X
  in expression:
    (fn {1=1,...} => 1) split
stdIn:22.37-22.54 Error: operator and operand don't agree [type mismatch]
  operator domain: {2:'Y; 'Z}
  operand:         int list * int -> 'X
  in expression:
    (fn {2=2,...} => 2) split
stdIn:24.4-24.35 Error: operator and operand don't agree [type mismatch]
  operator domain: {1:'Y; 'Z}
  operand:         int list * int -> int list * _ list
  in expression:
    (fn {1=1,...} => 1) split
stdIn:24.49-24.80 Error: operator and operand don't agree [type mismatch]
  operator domain: {2:'Y; 'Z}
  operand:         int list * int -> int list * _ list
  in expression:
    (fn {2=2,...} => 2) split
-

I set the head of the given list as pivot, and split the list into int list pairs and merge them again.

I think there are no type-matching problem but I don't no why it doesn't works. Plz give some help for me :(

score 1 · Accepted Answer · edited May 23 '17 at 12:17

Running your code in Moscow ML to highlight the problem code:

! Toplevel input:
!         then ((hd l)::(#1 split(tl l, v)), #2 split(tl l, v))
!                           ^^^^^
! Type clash: expression of type
!   int list * int -> int list * 'a list
! cannot have type
!   {1 : 'b, ...}

This type error suggests that an expression of type int list × int -> int list × 'a list is used where another part of the code expected it to be of type {1 : 'b, ...}. The first type is a function and the last type is a record with at least one entry in it.

The problem is that #1 split(tl l, v) is interpreted as (#1 split)(tl l, v) and not, as you intended, #1 (split (tl l, v)). That is, you want the first record entry of the result of the function, not of the function itself; that is nonsensical.. While #1 is in fact a macro and not a function, it behaves syntactically like a function and should be composed as such.

Since you're doing QuickSort in SML, you may be intredasted in the question True QuickSort in Standard ML that contains 1) RosettaCode's version that uses pattern matching rather than those scary partial functions like hd and tl that will crash your program unexpectedly at runtime, and 2) a version of QuickSort by John Coleman that is actually, algorithmically, a QuickSort. :-P

Thanks a lot! I really want to vote your answer up but I can't because of my reputation :( — Seokmin Hong, Apr 11 '17 at 10:53
@Rexion: You're welcome. Since you asked the question, you can mark the answer as "accepted". — sshine, Apr 11 '17 at 11:55

Quick Sort Error using SML

1 Answers1