Skip to content

Instantly share code, notes, and snippets.

@ntoronto
Created August 24, 2012 22:38
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ntoronto/3456604 to your computer and use it in GitHub Desktop.
Save ntoronto/3456604 to your computer and use it in GitHub Desktop.
A macro that expands to a fully inlined merge sort
#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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment