Functional Programming

The Most Beautiful Program Ever Written

A Lisp interpreter written in Lisp

6 minute read

It’s my 5th time trying to follow this video and things finally start to click in my head. So I think if I write down what is talked in the video, then I can just read my blog post for another 15 times instead of going through the video, that would be convenient. OK, here is a gist of it. This guy is writing an Scheme interpreter in Scheme.

Tree Vs Iterative Fibbonacci Numbers

Two types of recursion

2 minute read

Being a programmer, you should be very familiar with Fibbonacci numbers. It is often being introduced when teaching recursion. Tree Recursion Most likely the implementation of a function that calculate fib number is as follows: (defn fib-tree n) This is just a direct translation from the Fibonacci number definition. Since it is straightforward and easy to understand, most textbooks use it as an typical example for illustrating recursive function.

2 minute read

In this post, we will define what is a transducer. First, let’s take a closer look at map. (map inc [1 2 3]) A straightforward way to explain what has happened is this: Increment each item by one in a list. At first thought, this sounds like one step operation. Now let’s change the requirement a bit. We want to increment each element by one and then sum them together.

2 minute read

What this recur and tail calls optimization is all about in Clojure? This blog post is trying to give a short yet easy to remember explanation. Before explaining anything, let’s look at how we can implement + using recursion. This is actually an interesting task, implement our +, since most of the time + is a built-in function. So to make things a bit more clear, let’s assume that our computer is drunk and forgets about how to do +, but it still remembers how to increment and decrement by 1.