Many have written about why functional programming matters. There's a great pdf on why functional programming matters by John Hughes that I highly recommend reading. It talks about the many benefits of code written in a functional style, that it's incredibly more composable, testable, and in short, higher in quality.
But functional programming is also important for another reason. It's more awesome.
Factorial
fac n = foldl (*) 1 [1..n]
Computing factorials is the classic recursive example.
Fibonacci
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
This corecursive example generates a lazy list of the fibonacci numbers in linear time. The cool part here is the self-referential data structure. I like to call this the reverse ouroboros definition: the tail eating the head.
Quicksort
qsort [] = []
qsort (p:xs) = qsort lesser ++ [p] ++ qsort greater
where
lesser = filter (< p) xs
greater = filter (>= p) xs
This is beautiful.
Find all numbers which have only 2, 3, & 5 as non-trivial factors.
from itertools import tee, chain, islice, groupby
from heapq import merge
def hamming_numbers():
# Generate "5-smooth" numbers, also called "Hamming numbers"
# or "Regular numbers".
# See: http://en.wikipedia.org/wiki/Regular_number
# Finds solutions to 2**i * 3**j * 5**k for some integers i, j, k.
def deferred_output():
'Works like a forward reference to the "output" variable'
for i in output:
yield i
result, p2, p3, p5 = tee(deferred_output(), 4) # split streams
m2 = (2*x for x in p2) # multiples of 2
m3 = (3*x for x in p3) # multiples of 3
m5 = (5*x for x in p5) # multiples of 5
merged = merge(m2, m3, m5)
combined = chain([1], merged) # prepend start
output = (k for k, v in groupby(combined)) # eliminate dupes
return result
This cyclical iteration technique in python is the same kind of idea as the haskell fibonacci example above. The output streams are fed back in to generate the final result.
List flattening
(defun flatten (x)
(labels ((rec (x acc)
(cond ((null x) acc)
((atom x) (cons x acc))
(t (rec (car x) (rec (cdr x) acc))))))
(rec x nil)))
An example of a doubly recursive utility.
Function intersection
(defun fint (fn &rest fns)
(if (null fns)
fn
(let ((chain (apply #'fint fns)))
#'(lambda (x)
(and (funcall fn x) (funcall chain x))))))
Example of a function builder, with a recursive definition. The result here is and'ing the functions together. This allows us to say things like:
(find-if (fint #'signed #'sealed #'delivered) docs)Recursive function generators
(defun lrec (rec &optional base)
(labels ((self (lst)
(if (null lst)
(if (functionp base)
(funcall base)
base)
(funcall rec (car lst)
#'(lambda ()
(self (cdr lst)))))))
#'self))
; copy-list
(lrec #'(lambda (x f) (cons x (funcall f))))
; remove-duplicates
(lrec #'(lambda (x f) (adjoin x (funcall f))))
; find-if, for some function fn
(lrec #'(lambda (x f) (if (fn x) x (funcall f))))
; some, for some function fn
(lrec #'(lambda (x f) (or (fn x) (funcall f))))
If we find ourselves constantly building recursive functions ourselves to traverse through a list, why not abstract out that pattern? Here we see a technique for doing just that. We just need to define a function whose first argument represents the first element of the list, and the second is a function to call to continue the recursion. We can also define traversers on subtrees, which the reference link explores.
Note that we can make this even more concise, but we need lisp macros for that. But that's a topic for another discussion :)
Find the maximum profit buying and selling a stock one day
(defn max-profit [prices]
(reduce max (map - prices (reductions min prices))))
I just had to mention this one because of its brevity. It's almost like the problem was created to fit the solution.
20 questions
(defvar *nodes* (make-hash-table))
(defun defnode (name conts &optional yes no)
(setf (gethash name *nodes*)
(if yes
#'(lambda ()
(format t "~A~%>> " conts)
(case (read)
(yes (funcall (gethash yes *nodes*)))
(t
(funcall (gethash no *nodes*)))))
#'(lambda () conts))))
20 questions in a dozen lines. Not too shabby.
Here we see a technique for representing structure through closures themselves. Traditionally this is modelled using a tree to represent the yes/no decisions. In this case we're able to use the functions themselves to represent the decision trees, with the state captured through closures.
If the network will not change at run time, an optimization can be made to find the references to the yes/no functions at compile time instead of looking them up through a hash table. The reference link above explores this strategy.