Looking at the design recipes for 2 common sorting algorithms in Scheme
Structural and Generative Recursion
Recursion is a central component in functional programming, and one of my favourity programming concepts. In this post, we are going to look at two distinct ways in which recursive functions can be designed.
We’ll using the examples of 2 very common sorting algorithms for numbers, ie, insertion sort and the quick sort. The code snippets used below have been adapted the free e-book How to Design Programs (HtDP) and translated to MIT Scheme (from a teaching language created in Racket).
Insertion Sort and Structural Recursion
This is the most common type of recursive functions that we see in functional programming languages. It follows a common template which is very similar to wishful thinking! It really intrigued me when I learnt about it back in high school and still intrigues me to this day.
“Structural” recursion uses the underlying data “structures” naturally. Here, we only ever solve a very trivial case of the problem, and then, as if by magic, recursion solves the complete problem without us telling the computer how to do it!
Let’s look at the
insertion-sort function that takes a list of numbers as its argument.
; sorts a list l in increasing order ; List-of-numbers -> List-of-numbers (define (insertion-sort l) (cond ((null? l) '()) (else (insert (car l) (insertion-sort (cdr l))))))
We have not yet defined the
insert function so far. This is “wishful thinking” !!
If a function
insert existed that would insert a given no into a sorted list at the right position, that would solve our problem! And so we just used in our recursive definition of
insertion-sort. Notice that all we have really just solved the trivial case of sorting an empty list. And then, we are relying on recursion to sort the entire list by just naturally traversing the data structure, ie, the list.
; We now define the 'insert' function from our wish list, after which our problem is solved. ; Helper function that inserts a number n into a sorted list of numbers l at its correct position ; Number List-of-numbers -> List-of-numbers (define (insert n l) (cond ((null? l) (cons n '())) (else (if (<= n (first l)) (cons n l) (cons (car l) (insert n (cdr l))))))) ; testing the insert sort function with an example (insertion-sort '(72 45 43 29 34))
(29 34 43 45 72)
Quick Sort and Generative Recursion
We see how structural recursion has a very natural design template. In generative recursion though, instead of following a simple template like we did with Insertion Sort, we need some kind of mathematical insight into the problem itself to come up with the algorithm design. For quick sort, it’s ofcourse the “divide and conquer” strategy.
; [List-of Number] -> [List-of Number] ; produces a sorted version of list l, assume the numbers are all distinct (define (quick-sort l) (cond ((null? l) '()) (else (let ((pivot (car l))) (append (quick-sort (smallers l pivot)) (list pivot) (quick-sort (largers l pivot)))))))
Here, again we used 2 functions
largers that haven’t been defined yet, using wishful thinking once again!
; returns the sub list of numbers from a given list of numbers that are greater than the given number n ; [List-of Number] Number -> [List-of Number] (define (largers alon n) (cond ((null? alon) '()) (else (if (> (car alon) n) (cons (car alon) (largers (cdr alon) n)) (largers (cdr alon) n))))) ; returns the sub list of numbers from a given list of numbers that are smaller than the given number n ; [List-of Number] Number -> [List-of Number] (define (smallers alon n) (cond ((null? alon) '()) (else (if (< (car alon) n) (cons (car alon) (smallers (cdr alon) n)) (smallers (cdr alon) n)))))
Now, our function
quick-sort is complete, and we can test it similarly as above. Notice that the helper functions
smallers still follow the simple template of structural recursion only.
; testing the insert sort function with an example (quick-sort '(72 45 43 29 34))
(29 34 43 45 72)
It’s generally always easier to frame a recursive function as structural recursion, rather than to wait for an “AHA” moment to design a generative recursive function. However, sometimes the extra ingenuity can be worth it. For eg., the time completexity of quick sort is
O(n * log n) (appending the list of
largers, which is
n times). This is much better than our simple insertion sort function,
O(n * n) (the
O(n) is called
If you find the field of functional programming interesting, I would encourage you to check out the excellent books Structure & Interpretation of Computer Programs or SICP or HtDP. The Youtube lectures from MIT by the authors of the SICP are also a great learning resource. I’ve written a couple other blog posts on functional programming in Lisp dialects, which you might wanna check out here.
Don’t teach yourself data science in 10 days, but in 10 years
Some valuable lessons I learnt in my recent job search experience
And why you don’t need another ‘How to become a data scientist in 2021’ listicle
An intuitive way to look at matrix vector multiplication, with applications in image processing
Most tech firm interviews include SQL problems for DS roles, so how should you prepare for them?
Implementing basic matrix algebra operations in Scheme using a Jupyter notebook
Building a gender classifier model based on the dialogues of characters in Hollywood movies
Simple EDA of my reading activity using tidyverse on R Markdown
My experience using productivity tools for personal projects
Comparing Tree Recursion & Tail Recursion in Scheme & Python
My notes halfway through the book Learn You A Haskell
My topsy turvy ride to data science
Books, MOOCs and other resources that I would highly recommend
The magic of SICP