epicmonkey (epicmonkey) wrote,
epicmonkey
epicmonkey

Quicksort and lambda calculus

Quicksort and lambda calculus.

(define quicksort
  (lambda (l)
    ((Z (lambda (rec)
          (lambda (l)
            (((if (null l))
              nil)
             ((lambda (p)
                ((lambda (xs)
                   ((append
                     ((append
                       (rec ((filter (lambda (x) ((lte x) p))) xs)))
                      ((cons p) nil)))
                    (rec ((filter (lambda (x) ((gt x) p))) xs)))) (cdr l))) (car l)))))) l)))

(quicksort
 ((cons three) ((cons one) ((cons two) nil)))) ; => 1 2 3

; and its pure form. one of.

((L (l) (((L (f) ((L (g) (f (L (x) ((g g) x)))) (L (g) (f (L (x) ((g g) x)))))) 
(L (r) (L (l) ((((L (p) (L (x) (L (y) ((p x) y)))) ((L (p) (p (L (x) (L (y) (L 
(x) (L (y) y)))))) l)) (L (x) (L (x) (L (y) x)))) ((L (p) ((L (s) (((L (x) (L 
(y) ((((L (f) ((L (g) (f (L (x) ((g g) x)))) (L (g) (f (L (x) ((g g) x)))))) (L 
(r) (L (x) (L (y) ((((L (p) (L (x) (L (y) ((p x) y)))) ((L (p) (p (L (x) (L (y) 
(L (x) (L (y) y)))))) x)) y) (((L (p) (L (q) (L (h) ((h p) q)))) ((L (p) (p (L 
(x) (L (y) x)))) x)) ((r ((L (p) (p (L (x) (L (y) y)))) x)) y))))))) x) y))) 
(((L (x) (L (y) ((((L (f) ((L (g) (f (L (x) ((g g) x)))) (L (g) (f (L (x) ((g g) 
x)))))) (L (r) (L (x) (L (y) ((((L (p) (L (x) (L (y) ((p x) y)))) ((L (p) (p (L 
(x) (L (y) (L (x) (L (y) y)))))) x)) y) (((L (p) (L (q) (L (h) ((h p) q)))) ((L 
(p) (p (L (x) (L (y) x)))) x)) ((r ((L (p) (p (L (x) (L (y) y)))) x)) y))))))) 
x) y))) (r (((L (p) (L (l) ((((L (f) ((L (g) (f (L (x) ((g g) x)))) (L (g) (f (L 
(x) ((g g) x)))))) (L (r) (L (p) (L (l) ((((L (p) (L (x) (L (y) ((p x) y)))) ((L 
(p) (p (L (x) (L (y) (L (x) (L (y) y)))))) l)) (L (x) (L (x) (L (y) x)))) ((((L 
(p) (L (x) (L (y) ((p x) y)))) (p ((L (p) (p (L (x) (L (y) x)))) l))) (((L (p) 
(L (q) (L (h) ((h p) q)))) ((L (p) (p (L (x) (L (y) x)))) l)) ((r p) ((L (p) (p 
(L (x) (L (y) y)))) l)))) ((r p) ((L (p) (p (L (x) (L (y) y)))) l)))))))) p) 
l))) (L (x) (((L (x) (L (y) ((L (n) ((n (L (x) (L (x) (L (y) y)))) (L (x) (L (y) 
x)))) (((L (m) (L (n) ((n (L (n) (L (f) (L (x) (((n (L (g) (L (h) (h (g f))))) 
(L (u) x)) (L (u) u)))))) m))) x) y)))) x) p))) s))) (((L (p) (L (q) (L (h) ((h 
p) q)))) p) (L (x) (L (x) (L (y) x)))))) (r (((L (p) (L (l) ((((L (f) ((L (g) (f 
(L (x) ((g g) x)))) (L (g) (f (L (x) ((g g) x)))))) (L (r) (L (p) (L (l) ((((L 
(p) (L (x) (L (y) ((p x) y)))) ((L (p) (p (L (x) (L (y) (L (x) (L (y) y)))))) 
l)) (L (x) (L (x) (L (y) x)))) ((((L (p) (L (x) (L (y) ((p x) y)))) (p ((L (p) 
(p (L (x) (L (y) x)))) l))) (((L (p) (L (q) (L (h) ((h p) q)))) ((L (p) (p (L 
(x) (L (y) x)))) l)) ((r p) ((L (p) (p (L (x) (L (y) y)))) l)))) ((r p) ((L (p) 
(p (L (x) (L (y) y)))) l)))))))) p) l))) (L (x) (((L (x) (L (y) ((L (p) ((p (L 
(x) (L (y) y))) (L (x) (L (y) x)))) (((L (x) (L (y) ((L (n) ((n (L (x) (L (x) (L 
(y) y)))) (L (x) (L (y) x)))) (((L (m) (L (n) ((n (L (n) (L (f) (L (x) (((n (L 
(g) (L (h) (h (g f))))) (L (u) x)) (L (u) u)))))) m))) x) y)))) x) y)))) x) p))) 
s)))) ((L (p) (p (L (x) (L (y) y)))) l))) ((L (p) (p (L (x) (L (y) x)))) l)))))) 
l))
(((L (p) (L (q) (L (h) ((h p) q)))) (L (f) (L (x) (f (f (f x)))))) (((L (p) (L 
(q) (L (h) ((h p) q)))) (L (f) (L (x) (f x)))) (((L (p) (L (q) (L (h) ((h p) 
q)))) (L (f) (L (x) (f (f x))))) (L (x) (L (x) (L (y) x)))))))
Tags: lambda, playground, theneverendingstory
Subscribe

  • Beta reduction

    Внезапно, оказалось, что 500Мб недостаточно, чтобы записать всю последовательность вычислений для наибольшего общего делителя четырёх и шести. Так…

  • Basic lambda calculus

    Functions are "first class citizens" (Cristopher Strachey, mid-1960s). ; DISCLAIMER: THE DRAFT BELOW IS NOT INTENDED TO BE THE PURE LAMBDA…

  • Ultimate Guide Bricking a Karotz

    Ultimate guide bricking a Karotz WARNING: DON’T TRY THIS AT HOME UNLESS YOU UNDERSTAND EXACTLY WHAT YOU ARE DOING. SHUT UP AND…

  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 4 comments