While doing my OCaml MOOC exercise I came across a trie implementation for looking up words. I find that the way OCaml treats strings is very different from the way Haskell does it. It leads to different ways to implement the trie in the two languages. Strings and Tries in Haskell Haskell is a pure…

# Category: Functional Programming

## Eliminating Run Time Errors In OCaml and Haskell

Run Time Versus Compile Time Error Run time errors are those that happen when the program runs, as opposed to compile time errors which happen when the program compiles. In a sense, having compile time errors is no big deal, because the errors guarantee that the ill-defined program won’t be running. The programmer can fix…

## Folding Nonempty Lists in OCaml and Haskell

In the last post, I talked about catamorphisms in Haskell. Specifically, the advantages of the foldr1 or foldl1 option in Haskell. Namely, (1) not needing to specify the base case and (2) preserving polymorphisms in all applicable types. In this post, I will show another way to fold nonempty list without using foldr1 or foldl1…

## Programming with Bananas in Haskell (Versus OCaml)

In the last post I talked about catamorphisms in OCaml. In this post I compare that with Haskell. We’ll see that Haskell gives you more options when implementing catamorphisms. You don’t need to know Haskell to understand this post, I’ll introduce the required Haskell syntax along the way. Catamorphisms in Haskell As mentioned in the…

## Programming with Bananas in OCaml

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 as separate higher order functions…

## 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 when the function is called. …

## 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:

1 2 |
λx.λy.x+y (*A function expression*) λx.λy.x+y 3 4 (*A function application*) |

In OCaml, you can express the same with –fun:

1 2 |
fun x y -> x + y (fun x y -> x + y) 3 4 |

Each term separated by a space…

## 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.:

1 |
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 expressions that can be evaluated first. …

## 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 inputs into it. In other…

## 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.,

1 |
loop = rec (?) |

Encode the factorial function with rec. I.e.,…