A bifunctor is a functor whose source is a product category. In Haskell,
bifunctors have the `bimap`

operation:

## Efficient Concatenation and Inspection

Functional programmers know all too well that left-associated concatenation of cons-lists can
be a source of inefficiency. For example, if we perform a left-associated concatenation of *n*
singleton cons-lists, it would take *O(n ^{2})* to force the entire result list, and

*O(n)*just to force the first element. To illustrate the problem, recall that

`head`

and `++`

are defined as## A Quick-and-Dirty Explanation of MonadFix

This post aims to give a quick-and-dirty explanation of `MonadFix`

. It is quick and
dirty because `MonadFix`

is complex and weird stuff (or at least it seems so), and I do not
think I am able to present a comprehensive discussion. Instead, this post mainly consists of a simple example
that hopefully can give one a rough idea of what `MonadFix`

does and where it might
be useful.

## Defunctionalization for Haskell Type Families

The first language I used to do purely functional programming is Scala, which I learned when I was at Facebook, and I absolutely loved it. Not long afterwards I started to learn Haskell, and sure enough, Scala quickly became the second favorite. Haskell is simply too beautiful. This motivated me to join Formation in April last year. Being paid to write Haskell on a daily basis feels like a dream, in the sense that my work is now my hobby. As a result, I’ll start to write more Haskell posts here than Scala ones. I still like Scala but I haven’t touched it in a while and I’m fairly rusty at this point.

## Free Monoids and Free Monads, Free of Category Theory

Free monoids and free monads are important concepts to understand in functional programming. A free monoid on type `A`

is just `List[A]`

. List is the single most widely used data structure in functional programming and everyone knows what a list is. But not everyone knows why lists are called free monoids, and what is so “free” about it. And it pays to do so, because understanding what free monoids are about will make the concept of free monads much more comprehensible.

## Recursion Schemes in Scala - An Absolutely Elementary Introduction

When writing any non-trivial amount of code, we usually factor out the common logic or patterns to improve modularity, facilitate code reuse and avoid repeating ourselves. Recursion schemes is just about that. With recursion schemes you can factor out the recursion patterns in your code, so that you don’t need to write the same types of recursion over and over again. This may sound a little magical to those who aren’t familiar with recursion schemes, but it really isn’t.

## Stream, Laziness and Stack Safety

This post contains some notes on chapter 5 (Strictness and laziness) of the Functional Programming in Scala book (a.k.a The Red Book). The chapter covers the basics of non-strict and lazy evaluation in Scala, as well as an implementation of `Stream`

, a lazy version of `List`

.

## The fix Combinator in Scalaz

Fixed-point combinator is a really cool thing. It allows us to encode recursion in lambda calculus, which doesn’t have built-in support for recursion. Computerphile recently made a video featuring professor Graham Hutton, author of the book “Programming in Haskell”, giving a brief introduction to the Y combinator.

## How Trampoline Works in Scala

Trampoline is a way to make non-tail recursive functions stack-safe. Its Scala implementation is explained by Rúnar Bjarnason in his paper, Stackless Scala With Free Monads, and his book, Functional Programming in Scala. Rúnar’s (old) blog also has a post illustrating the idea. In this post I’d like to apply this technique on a few simple, concrete examples, and show step-by-step how it works on these examples and why it is able to make them stack-safe.

## Arrow Hangman in Scala

`Arrow`

is a useful typeclass for modeling something that behave like functions, e.g,. `Function1`

: `A => B`

, `Kleisli`

: `A => M[B]`

(also known as `ReaderT`

), `Cokleisli`

: `F[A] => B`

, etc. So useful, that Haskell provides a `proc`

notation for composing and combining `Arrow`

s, similar as the `do`

notation for sequencing monadic operations. The `proc`

notation comes in really handy, since without it, `Arrow`

s have to be used point-free, which impairs readability.