Skip to content

Tail-recursive Quicksort?

December 14, 2011

I’ve been using scheme and racket quite a bit lately, and because I have been playing with functional languages, I have been doing little exercises in solving problems in a more functional approach, which also includes some nice recursion. More specifically, I’ve been trying to think in a more “tail-recursion” approach to take advantage of the scheme systems that are tail-call optimized.

I found this little article, Quicksort: Like You’re 5, which gave a quick implementation- independent demostration of the quicksort algorithm, and being reintroduced to it’s definition, I recongnized it as perfect for recursion! And of course, a good problem for tail-recursion. However, I couldn’t think of how to approach it in a tail recursive manner, so I started by just quickly coding up a quick non-tail recursive version:

(define (quicksort list)
  (if (or (empty? list) (empty? (rest list))) list
      (let ([pivot (first list)]
	    [list (rest list)])
	(append (quicksort (filter ((curry >) pivot) list))
		`(,pivot)
		(quicksort (filter ((curry <=) pivot) list))))))

I got stumped, I couldn’t think of how to accumulate the results for a tail-call. The block I was stuck on was, “Can you tail-call something that branches?” I couldn’t think of a way, and unsure if it was me being naive or it was just not possible. Quick searches on rosettacode and duckduckgo turned up similar approaches to what I did above.

After a good nights sleep, I finally conceded. So you can’t tail-call two separate branches, but you can compute one-branch and tail-call the other, right? After a little bit of fumbling, I came up with this:

(define (quicksort-tail thelist)
  (let quick-acc ([tosort thelist] [acc '()])
    (if (or (empty? tosort) (empty? (rest tosort))) (append tosort acc)
	(let* ([pivot (first tosort)]
	       [tosort (rest tosort)]
	       [acc (append `(,pivot) (quicksort-tail (filter ((curry <=) pivot) tosort)) acc)])
	  (quick-acc (filter ((curry >) pivot) tosort) acc)))))

I haven’t done anything to determine if it’s more time/space efficient, but it works :]

Update: 10-16-2012 I feel pretty dumb about this post. I have been skimming through the newest [unofficial] version of SICP (as I’ve been contemplating making a toy scheme implementation), and while skimming through the section on recursion, I realized why tail-recursion is so important–it’s how you implement iteration. It was a wonderful moment when lots of dangling ends came together to form a strong knot… and then turned around and called me dumb. The final solution is the obvious one as that’s how we iterate through a tree. I essentially arrived at nested iterations in a very convoluted way.

Advertisements

From → Anecdotes, Howto

3 Comments
  1. I believe this product was the actual sweetest point ever.

  2. What’s up, all is going well here and ofcourse every one is sharing information, that’s truly good,
    keep up writing.

  3. I’m extremely pleased to find this page. I wanted to thank you for your time due to this fantastic read!!

    I definitely liked every little bit of it and i also have you
    saved to fav to see new stuff on your website.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s