Quicksort

aline.py

lambda i: (lambda f, *a: f(f, *a))(lambda r, l: r(r, [x for x in l[1:] if x <= l[0]]) + l[0:1] + r(r, [x for x in l[1:] if x > l[0]]) if len(l) else l, i)

bookmark.md

Quicksort

Learning a popular Haskell's quicksort, I try to reproduce it in Python. With a recursive style on lambda function. There also exists the recursive-by-name style, which is much easier to learn from it.

q = lambda l: q([x for x in l[1:] if x <= l[0]]) + l[0:1] + q([x for x in l[1:] if x > l[0]]) if len(l) else l

Tweet Size

lambda i:(lambda f,*a:f(f,*a))(lambda r,l:r(r,[x for x in l[1:] if x<=l[0]])+l[0:1]+r(r,[x for x in l[1:] if x>l[0]]) if len(l) else l,i)

code.py

lambda i: (
    lambda f, *a: f(f, *a))(      # this will made recursive on lambda function possible!
        lambda r, l:              # define recursive function here, with itself as 1st arg.
                r(r, [x for x in l[1:] if x <= l[0]]) +    # list of smaller values
                l[0:1] +                                   # a comparison value
                r(r, [x for x in l[1:] if x > l[0]])       # list of bigger values
            if len(l) else         # check if list is not empty (return above).
                l,                 # return empty list if it is empty.
        i)                         # argument for the recursive-wrapper function.

LICENSE.txt

            DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
                    Version 2, December 2004

 Copyright (C) 2012 Nattawut Phetmak <http://about.me/neizod>

 Everyone is permitted to copy and distribute verbatim or modified
 copies of this license document, and changing it is allowed as long
 as the name is changed.

            DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
   TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION

  0. You just DO WHAT THE FUCK YOU WANT TO.

package.json

{
  "name": "quicksort",

  "description": "quicksort on list with recursion on lambda function.",

  "keywords": [
    "quicksort",
    "sorting",
    "lambda",
    "recursion"
  ]
}

test.py

quick = lambda l: (lambda f, *a: f(f, *a))(lambda r, l: r(r, [x for x in l[1:] if x <= l[0]]) + l[0:1] + r(r, [x for x in l[1:] if x > l[0]]) if len(l) else l, l)

########## test ##########

output = quick([5,3,8,7,9,4,6,2,0,9,3,3,1,6])

expected = [0,1,2,3,3,3,4,5,6,6,7,8,9,9]
print("expected value: " + str(expected))

print("actual output: " + str(output))