Applicative: Lists
In Understanding apply I primarily
used the Option
type to show how you implement and use an Applicative Functor.
But the concept also works for any other type. This time I want to show
you the idea of an Applicative with a list, what it means, what you can do
with it and how apply
works.
Implementing apply
Currently the List
module don't offer a apply
function. So we must write it on our own.
As we learned in Understanding bind we
could implement apply
with bind
. Because List.collect
is the bind
function (you
can see that by inspecting the functionsignature), we could implement apply
like this.
1: 2: 3: 4: 5: 

Although it is good to know this, this time we implement apply
from scratch. So we can
better understand how apply
works.
The general idea of apply
is easy. We need to implement a function that expects a
function as it's first argument, and a value as the second argument. But both arguments
are boxed in our type. The only thing we must do is somehow call our function with
our value. So we need a function that can handle the following function signature:
1:


If it is unclear why we get a list<'b>
as a result. We should remember
what apply
does as a single argument function. It just takes a A<('a > 'b)>
and
transform it into a new function A<'a> > A<'b>
. Here A
stands for any Applicative
type.
For a list it has the following meaning:
 We get a list of functions as the first value
 We get a list of values as the second argument
 Unboxing a list means we just loop over the list
 Then we just execute every function with every value
We can implement apply
like this:
1: 2: 3: 4: 5: 6: 7: 

Working with apply
We keep it easy, so we just create two to four arguments functions that just adds its inputs together.
1: 2: 3: 

Usually we need a return
function, but we can easily lift any values into a list by just
surrounding it with []
, so we will skip this one. The idea of apply
means every argument
of a function can now be a boxed type. That means, instead of just passing two int
to add2
we can now pass a list<int>
as the first argument and a list<int>
as the second argument, and so on. We now can write something like this.
1: 2: 3: 

Let's see what those function calls produces
1: 2: 3: 

What we get back is the result of every input combination. Our first call with add2
expands to:
1: 2: 3: 4: 5: 6: 7: 8: 

How apply
works
At this point it is interesting to see how apply
actually works to get a better understanding
why we get those results. First we should remember how the operator <*>
works. Our
apply operator is just a infix function. It uses the the thing on the leftside as the
first argument, and the thing on the rightside as the second argument. Instead of
1:


we also could write
1:


When we have a term like [add2] <*> [1;2;3] <*> [10;20]
it means, first [add2] <*> [1;2;3]
is executed and it will return a result! This is exactly how a normal function call work.
Even a normal function call like add2 1 10
basically works by first executing add2 1
returning a new function and then pass 10
to it. That's why we also can write. (add2 1) 10
and it produces the same result. With apply
or <*>
it is the same, our term is
basically interpreted as
1:


At first, our apply
function is called with [add2]
and [1;2;3]
as its arguments.
Our apply
function just just loops over the functions and the values and call every
function with a value. After [add2] <*> [1;2;3]
we get a new list back, containing:
1: 2: 3: 4: 5: 

At this point it probably becomes clear why we can view apply
as some kind of
Partial Application for boxed functions. The only thing that apply
does is take
a boxed function and a boxed value and execute it. But it only does it for the
next argument. The first apply
call returns a new list with three Partial Applied
functions. We get:
1:


In other words, the new list is used as the first argument to the next apply
call.
This time we have a list of functions that contains three functions and two values.
Once again we loop over the functions and call every function with every value. We get:
1: 2: 3: 4: 5: 6: 7: 8: 

And this will result in
1:


To get a hang of it, let's once again go through the add4
example and visualize
every step. We start with
1:


The first apply
call produces:
1: 2: 3: 4: 5: 

We then use this result with apply
and use [10;20]
next.
1: 2: 3: 4: 5: 6: 7: 8: 

Then we use this list of functions with [5]
and we get
1: 2: 3: 4: 5: 6: 7: 8: 

Finally we use [100;200]
on this list, and we get.
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 

The last call executes the functions, so we get the result.
1:


Using apply
In general what we can do with an Applicative for a list is that we can get the result of all possible input combinations for a function, no matter how many arguments that function has.
We also can easily create Cartesian Products for a set of data. For example we could create all possible Playing cards in a game this way.
1: 2: 3: 4: 5: 6: 7: 8: 

We now can generate all possible Cards by using.
1: 2: 3: 4: 

We now get a list of all 52 cards as a result.
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 

The Cartesian Product is also the idea how we view relational data. We could for example
create two lists that refers to each other, with apply
we then can easily create the
Cartesian Product and filter those data.
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 

We now can create the Cartesian Product of those Data. And afterwards filter it.
1: 2: 3: 4: 5: 

This will return: ["David"; "Markus"]
and resembles a SQLStatement like:
1: 2: 3: 4: 

Sure, most stuff is basically ListProcessing at this point, but apply
is just another
functions in a toolset that opens up some possibilities. And at this point you probably
even see the connection between functional list processing and SQL, or in general the
C# LINQ Feature.
Full name: applicativelist.apply
module List
from Microsoft.FSharp.Collections

type List<'T> =
 ( [] )
 ( :: ) of Head: 'T * Tail: 'T list
interface IEnumerable
interface IEnumerable<'T>
member GetSlice : startIndex:int option * endIndex:int option > 'T list
member Head : 'T
member IsEmpty : bool
member Item : index:int > 'T with get
member Length : int
member Tail : 'T list
static member Cons : head:'T * tail:'T list > 'T list
static member Empty : 'T list
Full name: Microsoft.FSharp.Collections.List<_>
Full name: Microsoft.FSharp.Collections.List.collect
Full name: Microsoft.FSharp.Collections.list<_>
Full name: Main.apply
Full name: Main.add2
Full name: Main.add3
Full name: Main.add4
 Club
 Diamond
 Heart
 Spade
Full name: Main.Suit
 Ace
 Two
 Three
 Four
 Five
 Six
 Seven
 Eight
 Nine
 Ten
...
Full name: Main.Rank
union case Card.Card: Suit * Rank > Card

type Card =  Card of Suit * Rank
Full name: Main.Card
Full name: Main.suits
Full name: Main.ranks
Full name: Main.cards
{Id: int;
Name: string;}
static member create : id:int > name:string > Person
Full name: Main.Person
val int : value:'T > int (requires member op_Explicit)
Full name: Microsoft.FSharp.Core.Operators.int

type int = int32
Full name: Microsoft.FSharp.Core.int

type int<'Measure> = int
Full name: Microsoft.FSharp.Core.int<_>
val string : value:'T > string
Full name: Microsoft.FSharp.Core.Operators.string

type string = System.String
Full name: Microsoft.FSharp.Core.string
Full name: Main.Person.create
{PersonId: int;
Name: string;}
static member create : pid:int > name:string > Like
Full name: Main.Like
Full name: Main.Like.create
Full name: Main.persons
Full name: Main.likes
Full name: Main.likesTea
Full name: Microsoft.FSharp.Collections.List.filter
Full name: Microsoft.FSharp.Collections.List.map