Currying Recall that in lambda calculus, a function can have more than one input, each preceded by a λ symbol. Another way of thinking about more than one input is currying. Currying a function of two inputs turns that function into a function with one input by passing one of the…
Encoding Recursion with the Y Combinator
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…
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…
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…
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…
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…
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. …
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…
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…
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,…