By bananas, I mean banana brackets as in the famous paper “Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire” by Meijer et al. In this post I only focus on bananas, also called catamorphisms. Recursion is core to functional programming. Meijer et al. show that we can treat recursions…

# Category: Functional Programming

## Lexical Scoping in OCaml

Like many other modern languages, OCaml uses lexical (or static) scoping. That is, in OCaml, when your function includes a name that calls a variable, in the function, that variable has the value when the function is defined. The opposite is dynamic scoping, in which the variable has the value…

## Lambda Calculus in OCaml: “fun” and “function”

Lambda is fun! Lambda is certainly fun, but what I mean here is that the λ in lambda calculus is similar to the expression fun in OCaml. Recall that in lambda calculus, we have function expressions and function applications: λx.λy.x+y (*A function expression*) λx.λy.x+y 3 4 (*A function application*) In OCaml,…

## Lazy or Eager? Order of Evaluation in Lambda Calculus and OCaml

Recall in lambda calculus, two items side by side is an application. One applies the left item (the function) to the right item (the input). E.g.: f x is read as “apply f to x“, in which f and x can be any lambda expressions. Therefore, f and/or x may be…

## Currying in Lambda Calculus and OCaml

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…

## 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 and Functional Insertion Sort in OCaml

I wrote the insertion algorithm in both imperative and functional styles in OCaml! I talk about the fun and challenges of each style below: Imperative Insertion Sort I strictly follow the pseudocode on p.18 of the book Introduction to Algorithms. The pseudocode is in imperative style so all I need…