public
Created

A macro that expands to a fully inlined merge sort

  • Download Gist
inline-merge-sort.rkt
Racket
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
#lang racket
 
(require (for-syntax racket/list)) ; for list functions
 
(define-syntax (inline-sort stx)
(syntax-case stx ()
[(_ lst ...)
(with-syntax ([(vs ...) (generate-temporaries #'(lst ...))])
#`(let ([vs lst] ...)
#,(inline-sort/k #'(vs ...) (λ (vs) #`(values #,@vs)))))]))
 
(define-for-syntax (inline-merge/k as bs k)
(syntax-case (list as bs) ()
[(() bs) (k #'bs)]
[(as ()) (k #'as)]
[((a as ...) (b bs ...))
#`(if (< a b)
#,(inline-merge/k #'(as ...) #'(b bs ...)
(λ (vs) (k (cons #'a vs))))
#,(inline-merge/k #'(a as ...) #'(bs ...)
(λ (vs) (k (cons #'b vs)))))]))
 
(define-for-syntax (inline-sort/k vs k)
(syntax-case vs ()
[() (k vs)]
[(a) (k vs)]
[_ (let ([vs (if (list? vs) vs (syntax->list vs))])
(define-values (lvs rvs) (split-at vs (quotient (length vs) 2)))
(inline-sort/k
lvs (λ (lvs)
(inline-sort/k
rvs (λ (rvs)
(inline-merge/k lvs rvs k))))))]))
 
(inline-sort 5 2 3)

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.