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

  • 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…

  • When I was 5 years old I was maimed by a giant rabbit

    When I was 5 years old I was maimed by a giant rabbit. But. I knew. Revenge is a sweet thing. I knew. I will plant seeds of revenge and let them…

  • Beta reduction

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

  • 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