In this post I’ll go through some exercises and encode some recursive functions with the Y combinator. Encoding with rec Continuing on from my last post, Professor Hutton gave us two exercises in the Y combinator video: Encode loop (the function that just calls itself) with rec. I.e., loop = rec (?) Encode the factorial function…
Recursion in Lambda Calculus: The Y Combinator
In the last post I talked about how powerful lambda calculus is. In this post I further proves the point by encoding recursion in it. This enables you to do recursion in any languages! If you haven’t read my last post already, please do so! It’d be easier for you to follow this post, especially…
Simple Yet Powerful: Lambda Calculus
I’ve long since heard of “Lambda Calculus” but I didn’t really know what it is about until I saw this video. It got me super excited! What I love about it is that it’s built on almost nothing! Only the concept of functions. It’s so simple and elegant! Professor Graham Hutton also listed good reasons to…
Setting Up an OCaml Development Environment in Debian
In this post I share how I switched to Debian and set up a development environment for OCaml. As mentioned in this post, I was running NixOS on my machine, but getting it set up comfortably for OCaml seems challenging. Instead of fighting with the OS, I decided to switch to Debian because I love…
More on Imperative Merge Sort
I talked about how I wrote imperative merge sort in OCaml earlier. I have been thinking about improving it because it was not as tidy as I’d like. I learnt a few things in the process: Gain as much information as you can to debug. E.g., it can help to print out intermediate results. I…
Imperative and Functional Merge Sort in OCaml
So happy to be back! The last two week I was running around seeing doctors, lab technicians, etc because I had a mysterious lump on my neck. It’s still there, but they figured out that it’s nothing worrisome. I’m so grateful! I’ve always been healthy so this was really shocking. I realized that when I’m…
Merge Sort and the Divide and Conquer Approach
Algorithm Design Techniques In earlier posts, I went through the insertion sort and the selection sort algorithms. They both use the incremental approach. Each step of the algorithms sorts one element, and thus the algorithms solve the problem incrementally. The divide-and-conquer is another approach. It includes 3 steps that are executed recursively until the problem…
Functional Style Selection Sort in OCaml
In this post I talk about what I have tried and learnt in the process of writing the functional correspondence of the imperative selection sort I wrote earlier in OCaml. I learnt a lot in this practice because functional selection sort is not straight forward! The First Attempt At the beginning, I thought functional selection…
Imperative Style Selection Sort in OCaml
Exercise 2.2-2 of the book Introduction to Algorithms introduced the selection sort algorithm. I decided to write it in OCaml in imperative style. The selection sort algorithm sorts a list first by switching places of the smallest element of a given list with the first element of the list. Then, it selects the smallest element…
The Efficiency of an Algorithm
We need to analyze algorithms to choose the most efficient algorithm to implement. One important aspect we look at is the running time of an algorithm, which often depends on the size of input. (See Chapter 2-2 of Introduction to Algorithms.) Size of Input Examples in measuring the input size of a problem: The number…