As an extension to the previous blog, we finally reach the highest level of abstraction yet – the Monad. Let’s see how we can implement our custom `List` type as an instance of the `Monad` typeclass. Here is the definition of the `Monad` typeclass as given in the book:

```class Applicative m => Monad m where
return :: a -> m a

(>>=) :: m a -> (a -> m b) -> m b

return = pure
```

This means that in order to make our `List` type an instance of `Monad`, we will have to make it an instance of `Functor` as well as Applicative.

Here is a simple but comprehensive implementation:

```data List a = Nil | Cons a (List a) deriving Show

append :: List a -> List a -> List a
append Nil ys = ys
append (Cons x xs) ys = Cons x (append xs ys)

instance Functor List where
-- fmap :: (a -> b) -> List a -> List b
fmap _ Nil = Nil
fmap f (Cons x xs) = Cons (f x) (fmap f xs)

instance Applicative List where
-- pure :: a -> List a
pure x = Cons x Nil

-- (<*>) :: List (a -> b) -> List a -> List b
Nil <*> _ = Nil
(Cons g gs) <*> xs = fmap g xs `append` (gs <*> xs)

-- (>>=) :: List a -> (a -> List b) -> List b
Nil >>= _ = Nil
(Cons x xs) >>= f = (f x) `append` (xs >>= f)
```

We also define some test data to work with, and a function called `pairs` that simply returns the cross-product of the two input lists.

```
-- test data
l1 :: List Int
l1 = Cons 1 (Cons 2 (Cons 3 (Cons 4 (Cons 5 Nil))))

l2 :: List String
l2 = Cons "Hello" (Cons "World" (Cons "we" (Cons "meet" (Cons "again" Nil))))

pairs :: Monad m => m a -> m b -> m (a, b)
pairs xs ys = xs >>= \x ->
ys >>= \y ->
return (x, y)
```

Note that the `pairs` function could also have been written using the `do` notation as follows:

```pairs :: Monad m => m a -> m b -> m (a, b)
pairs xs ys = do x <- xs
y <- ys
return (x, y)
```

This is identical to the previous version since the `do` notation is simply syntactic sugar for the bind operator.

Sample test run:

```*Main> :t l1
l1 :: List Int
*Main> l2
Cons "Hello" (Cons "World" (Cons "we" (Cons "meet" (Cons "again" Nil))))
*Main> pairs l1 l2
Cons (1,"Hello") (Cons (1,"World") (Cons (1,"we") (Cons (1,"meet") (Cons (1,"again") (Cons (2,"Hello") (Cons (2,"World") (Cons (2,"we") (Cons (2,"meet") (Cons (2,"again") (Cons (3,"Hello") (Cons (3,"World") (Cons (3,"we") (Cons (3,"meet") (Cons (3,"again") (Cons (4,"Hello") (Cons (4,"World") (Cons (4,"we") (Cons (4,"meet") (Cons (4,"again") (Cons (5,"Hello") (Cons (5,"World") (Cons (5,"we") (Cons (5,"meet") (Cons (5,"again") Nil))))))))))))))))))))))))
```

# Implementing Applicative for a custom List type in Haskell

Continuing with the Haskell theme, this is a small implementation of `Applicative` for a custom `List` type in Haskell.

Here is the general definition of `Applicative` as given in Professor Graham Hutton’s exemplary book, “Programming in Haskell” (2nd Edition) – one of the best books on Haskell:

```class Functor f => Applicative f where
pure :: a -> f a

(<*>) :: f (a -> b) -> f a -> fb
```

This means that we have to make our custom `List` type into an instance of `Functor` before we can make it an instance of `Applicative`. Here is the definition of `Functor` from the same book:

```class Functor f where
fmap :: (a -> b) -> f a -> f b
```

Okay, enough preamble, let’s get started with it. First, we define our custom `List` type:

```data List a = Nil | Cons a (List a) deriving (Eq, Ord, Show, Read)
```

Now we define a function called `append`. This is our analogue of the built-in `++` generic append operator in Haskell. This will be required when implementing the `Applicative` code:

```-- append function for our custom List type
append :: List a -> List a -> List a
append Nil ys = ys
append (Cons x xs) ys = Cons x (append xs ys)
```

Almost there! Let’s make our `List` type a `Functor` type:

```-- make it an instance of the Functor typeclass
instance Functor List where
-- fmap :: (a -> b) -> List a -> List b
fmap _ Nil = Nil
fmap g (Cons x xs) = Cons (g x) (fmap g xs)
```

Simple enough – we simply implement the `fmap` function using Pattern Matching. Now, finally, let’s make our type an `Applicative Functor`!

```-- now make the List type an instance of Applicative
instance Applicative List where
-- pure :: a -> List a
pure x = Cons x Nil

-- (<*>) :: List (a -> b) -> List a -> List b
Nil <*> _ = Nil
(Cons g gs) <*> xs = append (fmap g xs) (gs <*> xs)
```

That’s it! We’re all done. Again, we use Pattern Matching in the implementation of , the applicative operator. As promised earlier, we make use of both `fmap` and `append` in this definition.

Finally, let’s define some test data:

```-- test data
l1 :: List Int
l1 = Cons 1 (Cons 2 (Cons 2 Nil)) -- [1, 2, 3]

l2 :: List Int
l2 = Cons 10 (Cons 20 Nil) -- [10, 20]

l3 :: List Int
l3 = Nil -- []
```

Let’s try out a few tests to make sure that it works correctly!

```*Main> l1
Cons 1 (Cons 2 (Cons 2 Nil))

*Main> l2
Cons 10 (Cons 20 Nil)

*Main> l3
Nil

*Main> pure (+1) <*> l1
Cons 2 (Cons 3 (Cons 3 Nil))

*Main> pure (+) <*> l1 <*> l2
Cons 11 (Cons 21 (Cons 12 (Cons 22 (Cons 12 (Cons 22 Nil)))))

*Main> pure (\x -> \y -> \z -> x * y * z) <*> l1 <*> l2 <*> l1
Cons 10 (Cons 20 (Cons 20 (Cons 20 (Cons 40 (Cons 40 (Cons 20 (Cons 40 (Cons 40 <br/>(Cons 40 (Cons 80 (Cons 80 (Cons 20 (Cons 40 (Cons 40 (Cons 40 (Cons 80 <br/>(Cons 80 Nil)))))))))))))))))

*Main> pure (\x -> \y -> \z -> x * y * z) <*> l1 <*> l2 <*> Nil
Nil

*Main> pure (^200) <*> l3
Nil

*Main> pure (\x y z w -> (x+y) * (z+w)) <*> l1 <*> l2 <*> l1 <*> l2
Cons 121 (Cons 231 (Cons 132 (Cons 242 (Cons 132 (Cons 242 (Cons 231 (Cons 441 <br/>(Cons 252 (Cons 462 (Cons 252 (Cons 462 (Cons 132 (Cons 252 (Cons 144 (Cons <br/>264 (Cons 144 (Cons 264 (Cons 242 (Cons 462 (Cons 264 (Cons 484 (Cons 264 (Cons <br/>484 (Cons 132 (Cons 252 (Cons 144 (Cons 264 (Cons 144 (Cons 264 (Cons <br/>242 (Cons 462 (Cons 264 (Cons 484 (Cons 264 (Cons 484 <br/>Nil)))))))))))))))))))))))))))))))))))

```

Most satisfying indeed!

# Interop mini-series – Callbacks special! (Part 2a)

This post was actually meant to be part of the previous post(Calling C and C++ from Common Lisp).

However, as I began writing the section of “callbacks”, it started growing to such an extent that I decided to give its own post with a slightly more comprehensive treatment than originally planned!

## What exactly is a callback?

A callback, in essence, is simply a function that is executed by another function which has a reference of sorts to the first function. Yes, that’s really it!

### Uses

One major use is to ensure proper separation of concerns.

Suppose we are writing some client code that makes use of a library, and say that our client function wishes to invoke a library function. Now, this library function executes code that might result in some form of platform specific signalling that will need to be handled in disparate ways depending on the specific signal received. The library writer could not possibly have imagined all the scenarios for such signalling when he was writing the library. So how can this work? Callbacks to the rescue!

So what the library writer did was to hold a reference to a callback function in his own function, and then his function invokes this callback function as and when the need arises (say an error condition or an OS interrupt). The callback function then takes care of all the handling and bookkeeping involved.

This callback function is, of course, expected to be supplied by the client code. This makes sense since the client has the best knowledge of its own domain. This then means that the library writer can make his code as generic as possible, leaving the specifics for the client to manage.

Another common use of callbacks is asynchronous programming. For example, suppose we have a function that needs to be activated when some specific conditions have arisen, and those conditions are decided by some other code. This is a good case to use a callback.

The current function can “register” itself with the condition-generating code, and then that code can invoke a callback in the current function’s module, which can then proceed to completion. Node, in particular, makes extensive use of this approach. The general Observer pattern is, in essence, the generalisation of a callback.

### Implementation

Top

Callbacks may be implemented through various means – function pointers, function objects, or lambda abstractions. The important bit is to understand the concept and defer the specifics of the modes of implementation to the language at hand.

Callbacks can be both synchronous or asynchronous (think Node).

So much for the concept. As far as the terminology goes, it is important to remember that the callback itself is the actual function that is invoked by the function that takes the callback as the parameter. A lot of confusion arises precisely for the reason that some people tend to assume that the function taking the function parameter is the callback function. Quite contrary, as we have just surmised. The one mnemonic that always works for me is to remember that both the client function and the callback function are in the same conceptual module.

Finally, a caveat – extensive use of callbacks can lead to what is known as “callback hell” (check the Reference section – there is a whole site dedicated to it!). The rule of thumb is to use a callback only when it is absolutely needed. Otherwise, it can lead to code which is both unreadable and unmaintainable.

## Demos

Top

Let’s now take a brief look at the functionality offered by callbacks is implemented in various languages. Of course, there may be different mechanisms for doing so, but I have chosen what I feel to be the idiomatic form in each language under discussion.

For all these examples, we will consider the same example – we have a function (`squarify`) which takes two parameters – a number and a callback function (`callback`). `squarify` simply squares the parameter, and then invokes `callback` with the squared value.

`callback` simply prints out the received value with a small message. The whole chain is triggered by another function `client`, which invokes `squarify`.

Note that all the examples here are, for the sake of simplicity, synchronous.

### How it’s done in C

Top

In C and C++, we make use of function pointers like so:

```#include <stdio.h>

void squarify(int, void(*)(int));
void callback(int);
void client();

int main()
{
client();

return 0;
}

void client()
{
int n;

printf("Enter a number: ");
scanf("%d", &n);

squarify(n, &callback);
}

void squarify(int n, void (*cb)(int))
{
(*cb)(n*n);
}

void callback(int n)
{
}
```

And the output:

```Timmys-MacBook-Pro:C z0ltan\$ gcc -Wall -o callbackdemo callbackdemo.c

Timmys-MacBook-Pro:C z0ltan\$ ./callbackdemo
Enter a number: 19
```

Notice how we pass the address of `callback` to `squarify` using `&callback` inside the `client` function.

### How it’s done in C++

Top

The technique used in the C example (declaring the callback as a function pointer parameter to `squarify` and then passing it the address of `callback` at runtime will work just the same way in C++ as well.

However, in addition, C++ offers a whole lot more ways of achieving the same result. Let’s explore three of these in the same demo – lambda abstractions, function objects, and functors.

To this end, we use a `std::function` object to hold a reference to the callback in `squarify`. This class type is specified in the header.

The logic remains unchanged from that used in the C demo.

Note that this code only works in C++11 (or above).

```//C++11 or above
#include <iostream>
#include <functional>

// Define the functor class
typedef struct {
public:
void operator()(int n)
{
std::cout << "Received: " << n << std::endl;
}
} backcall;

void squarify(int, std::function<void(int)>);
void callback(int);
void client();

int main()
{
client();

return 0;
}

void client()
{
int n;

std::cout << "Enter a number: ";
std::cin >> n;

// simply pass in a lambda abstraction!
squarify(n, [](int x)
<< x << std::endl;
});

// or specify a function explicitly
squarify(n, callback);

// or pass in a functor!
squarify(n, backcall());
}

void squarify(int n, std::function<void(int)> cb)
{
cb(n*n);
}

void callback(int n)
{
std::cout << "Received: " << n << std::endl;
}
```

And the output:

```Timmys-MacBook-Pro:C++ z0ltan\$ g++ -std=c++11 -Wall -o callbackdemo callbackdemo.cpp

Timmys-MacBook-Pro:C++ z0ltan\$ ./callbackdemo
Enter a number: 19
```

Et voila!

### How it’s done in Java

Top

In Java, the situation is a bit more complicated than usual for many reasons – lack of pure function objects, extreme verboseness, lack of pure generic functions, etc.

However, the code below demonstrates how we would do it pre-Java 8 (and frankly, most code written today still follow this idiomatic approach).

```import java.io.InputStreamReader;
import java.io.IOException;

interface Callback {
void call(int x);
}

public class CallbackDemo {
public static void main(String[] args) {
client();
}

public static void client() {
int n;

Callback cb = new Callback() {
@Override
public void call(int n) {
}
};

System.out.print("Enter a number: ");
squarify(n, cb);
} catch (NumberFormatException |IOException ex) {
ex.printStackTrace();
}
}

public static void squarify(int n, Callback callback) {
callback.call(n*n);
}
}
```
```Timmys-MacBook-Pro:Java z0ltan\$ javac CallbackDemo.java
Timmys-MacBook-Pro:Java z0ltan\$ java -cp . CallbackDemo
Enter a number: 19
```

The code is mostly self-explanatory. To simulate function pointers/function objects, we simply make use of essentially what’s equivalent to the C++ functor (`backcall`) used in the previous demo.

The `Callback` interface declares a single abstract method called `call` which takes a single `int` parameter, and prints out a small message onto the console.

The `squarify` function takes an `int` parameter along with an instance of `Callback`, and then calls that instance’s `call` function. (On a side note, this is precisely why even C++’s functors are superior to Java’s. C++ has operator overloading, Java unfortunately does not).

Now, let’s take a look at how it would be done using Java 8 (and above). The Java 8 version is a marked improvement in terms of readability and conciseness.

Here’s the code:

```import java.io.InputStreamReader;
import java.io.IOException;

import java.util.function.Function;

public class CallbackDemo8 {
public static void main(String[] args) {
client();
}

public static void client() {
System.out.print("Enter a number: ");

squarify(n, (x) -> { System.out.println("Received: " + x); return null; });
} catch (NumberFormatException | IOException ex) {
ex.printStackTrace();
}
}

public static void squarify(int n, Function<Integer,Void> cb) {
cb.apply(n*n);
}
}

And here’s the output:

Timmys-MacBook-Pro:Java z0ltan\$ java -cp . CallbackDemo8
Enter a number: 19
```

We observe a few things that differentiate it from the pre-Java 8 version:

• The `Callback` interface is gone, having been replaced by the built-in `Function` function interface.
• The `callback` function is also gone, and a lambda abstraction replaces it instead.

The lambda expression `(x) -> { System.out.println(“Received: “ + x); return null; }` still looks ugly with that `return null;` call. It is clearly redundant, but because of the way the `Function` functional interface is defined, this statement is mandatory.

We could fix that by creating our own functional interface like so:

```@FunctionalInterface
interface Function<T> {
void apply(T o);
}
```

However, it would reintroduce a custom interface in our code. So, not much gained there!

### How it’s done in Common Lisp

Top

A full post containing a detailed discussion on this topic (along with the relevant demos) is available here in the next part of this series. Make sure to check that out!

### How it’s done in other languages

Top

Let’s implement the same example in a few other languages for our own edification! For the sake of brevity (this post is already quite long!), we will stick to very commonly used languages - JavaScript and Python.

I feel these should be representative of most of the mainstream languages. Haskell is a bit of a different beast, but that is worthy of its own series of posts!

#### JavaScript

Top

Since client-side JavaScript does not provide any means of taking input in from the command line, we will use Node.js for this demo. For I/O from the console, we will use the readline module that now comes bundled with Node.

```const readline = require('readline');

input: process.stdin,
output: process.stdout
});

function callback(n) {
}

function squarify(n, cb) {
cb(n*n);
}

function client() {
stream.question("Enter a number: ", function(n) {
squarify(n, callback);
stream.close();
process.stdin.destroy();
});
}

// run!
client();
```

And the output:

```Timmys-MacBook-Pro:JavaScript z0ltan\$ node callback.js
Enter a number: 19
```

Again, this is equivalent to the C version. We simply pass the function name (which is a reference to the function object) to the `squarify` function as the callback function.

However, we could do it more idiomatically using a lambda abstraction as follows:

```const readline = require('readline');

input: process.stdin,
output: process.stdout
});

function squarify(n, cb) {
cb(n*n);
}

function client() {
stream.question("Enter a number: ", function(n) {
squarify(n, function(x) {
});

stream.close();
process.stdin.destroy();
});
}

// run!
client()
```

Note how the `callback` function has now been replaced by a a lambda abstraction that does the same operation.

And the output:

```Timmys-MacBook-Pro:JavaScript z0ltan\$ node callback_demo_lambda.js
Enter a number: 19
```

Nice!

#### Python

Top

In Python, just like in JavaScript, the function name itself is an intrinsic reference to the function object. Functions are, after all, first-class objects in Python, and we can simply pass it around like so:

```def callback(n):

def squarify(n, cb):
cb(n*n)

def client():
print("Enter a number: ", end='')
n = int(input())

squarify(n, callback)

if __name__ == '__main__':
client()
```

Note that the code was written in Python 3. However, it will easily work with minimal changes with Python 2.x as well.

And the output:

```Timmys-MacBook-Pro:Python z0ltan\$ python3 callback_demo.py
Enter a number: 19
```

However, since Python also supports a crude form of lambda abstractions, we could rewrite the demo like so:

```def squarify(n, cb):
cb(n*n)

def client():
print("Enter a number: ", end='')
n = int(input())

squarify(n, lambda x: print("Received: " + str(x)))

if __name__ == '__main__':
client()
```

So now we have simply passed the callback function as a lambda abstraction to the `squarify` function.

And just to verify, the output:

```Timmys-MacBook-Pro:Python z0ltan\$ python3 callback_demo_lambda.py
Enter a number: 19
```

So that’s all for now! Next up, callbacks in Common Lisp, and how we can write a simple function to perform function composition.

## References

Top

Here are a few references related to the topics discussed in this blog post that you might find useful: