gistfile1.rkt

#lang typed/racket

(: mergesort : (All (X) ([Listof X] [X X -> Boolean] -> [Listof X])))
(define (mergesort ls <=)
  (: mergesort/length : (All (X) ([Listof X] Integer -> [Listof X])))
  (define (mergesort/length ls n)
    (let* ([n/2 (exact-floor (/ n 2))])
      (cond [(= n 0) ls]
            [(= n 1) ls]
            [else (merge (mergesort/length (take ls n/2) n/2)
                         (mergesort/length (drop ls n/2) (- n n/2))
                         <=)])))
  (mergesort/length ls (length ls)))

(: merge : (All (X) ([Listof X] [Listof X] [X X -> Boolean] -> [Listof X])))
(define (merge a b <=)
  (cond [(empty? a) b]
        [(empty? b) a]
        [(<= (first a) (first b))
         (cons (first a) (merge (rest a) b <=))]
        [else
         (cons (first b) (merge a (rest b) <=))]))

(module+ test
  (require rackunit)
  (define (test-mergesort ls)
    (mergesort ls <=))

  (check-equal? (test-mergesort '()) '())
  (check-equal? (test-mergesort '(1)) '(1))
  (check-equal? (test-mergesort '(1 2 3)) '(1 2 3))
  (check-equal? (test-mergesort '(2 3 1)) '(1 2 3))
  (check-equal? (test-mergesort '(2 1 3)) '(1 2 3))
  (check-equal? (test-mergesort '(3 2 1)) '(1 2 3))
  (check-equal? (test-mergesort '(-3 2 1)) '(-3 1 2))
  (check-equal? (test-mergesort '(10 100 42 -5 5)) '(-5 5 10 100 42))
  (check-equal? (test-mergesort '(2 5 10 1 5)) '(1 2 5 5 10)))

1 danking@spock # raco test mergesort.rkt
mergesort.rkt:11:18: Type Checker: Polymorphic function merge could not be applied to arguments:
Argument 1:
Expected: (Listof X)
Given: (Listof X)
Argument 2:
Expected: (Listof X)
Given: (Listof X)
Argument 3:
Expected: (X X -> Boolean)
Given: (X X -> Boolean)

Result type: (Listof X)
Expected result: (Listof X)

in: (merge (mergesort/length (take ls n/2) n/2) (mergesort/length (drop ls n/2) (- n n/2)) <=)
context...:
/Applications/Racket v5.90.0.10/share/pkgs/typed-racket-lib/typed-racket/typecheck/tc-toplevel.rkt:288:0: type-check
/Applications/Racket v5.90.0.10/share/pkgs/typed-racket-lib/typed-racket/tc-setup.rkt:43:0: tc-setup/proc
/Applications/Racket v5.90.0.10/share/pkgs/typed-racket-lib/typed-racket/typed-racket.rkt:53:4
standard-module-name-resolver
/Applications/Racket v5.90.0.10/share/pkgs/compiler-lib/compiler/commands/test.rkt:107:11: for-loop
f88
/Applications/Racket v5.90.0.10/share/pkgs/compiler-lib/compiler/commands/test.rkt: [running body]
/Applications/Racket v5.90.0.10/collects/raco/raco.rkt: [running body]
/Applications/Racket v5.90.0.10/collects/raco/main.rkt: [running body]