# Understanding bind
This post is the second in a series. In the [previous post](https://swlaschin.gitbook.io/fsharpforfunandprofit/functional-patterns/map-and-bind-and-apply-oh-my/elevated-world), I described some of the core functions for lifting a value from a normal world to an elevated world.
In this post, we'll look at "world-crossing" functions, and how they can be tamed with the `bind` function.
## Series contents
Here's a list of shortcuts to the various functions mentioned in this series:
* **Part 1: Lifting to the elevated world**
* [The `map` function](https://swlaschin.gitbook.io/fsharpforfunandprofit/functional-patterns/elevated-world#map)
* [The `return` function](https://swlaschin.gitbook.io/fsharpforfunandprofit/functional-patterns/elevated-world#return)
* [The `apply` function](https://swlaschin.gitbook.io/fsharpforfunandprofit/functional-patterns/elevated-world#apply)
* [The `liftN` family of functions](https://swlaschin.gitbook.io/fsharpforfunandprofit/functional-patterns/elevated-world#lift)
* [The `zip` function and ZipList world](https://swlaschin.gitbook.io/fsharpforfunandprofit/functional-patterns/elevated-world#zip)
* **Part 2: How to compose world-crossing functions**
* [The `bind` function](#bind)
* [List is not a monad. Option is not a monad.](#not-a-monad)
* **Part 3: Using the core functions in practice**
* [Independent and dependent data](https://swlaschin.gitbook.io/fsharpforfunandprofit/functional-patterns/elevated-world-3#dependent)
* [Example: Validation using applicative style and monadic style](https://swlaschin.gitbook.io/fsharpforfunandprofit/functional-patterns/elevated-world-3#validation)
* [Lifting to a consistent world](https://swlaschin.gitbook.io/fsharpforfunandprofit/functional-patterns/elevated-world-3#consistent)
* [Kleisli world](https://swlaschin.gitbook.io/fsharpforfunandprofit/functional-patterns/elevated-world-3#kleisli)
* **Part 4: Mixing lists and elevated values**
* [Mixing lists and elevated values](https://swlaschin.gitbook.io/fsharpforfunandprofit/functional-patterns/elevated-world-4#mixing)
* [The `traverse`/`MapM` function](https://swlaschin.gitbook.io/fsharpforfunandprofit/functional-patterns/elevated-world-4#traverse)
* [The `sequence` function](https://swlaschin.gitbook.io/fsharpforfunandprofit/functional-patterns/elevated-world-4#sequence)
* ["Sequence" as a recipe for ad-hoc implementations](https://swlaschin.gitbook.io/fsharpforfunandprofit/functional-patterns/elevated-world-4#adhoc)
* [Readability vs. performance](https://swlaschin.gitbook.io/fsharpforfunandprofit/functional-patterns/elevated-world-4#readability)
* [Dude, where's my `filter`?](https://swlaschin.gitbook.io/fsharpforfunandprofit/functional-patterns/elevated-world-4#filter)
* **Part 5: A real-world example that uses all the techniques**
* [Example: Downloading and processing a list of websites](https://swlaschin.gitbook.io/fsharpforfunandprofit/functional-patterns/elevated-world-5#asynclist)
* [Treating two worlds as one](https://swlaschin.gitbook.io/fsharpforfunandprofit/functional-patterns/elevated-world-5#asyncresult)
* **Part 6: Designing your own elevated world**
* [Designing your own elevated world](https://swlaschin.gitbook.io/fsharpforfunandprofit/functional-patterns/elevated-world-6#part6)
* [Filtering out failures](https://swlaschin.gitbook.io/fsharpforfunandprofit/functional-patterns/elevated-world-6#filtering)
* [The Reader monad](https://swlaschin.gitbook.io/fsharpforfunandprofit/functional-patterns/elevated-world-6#readermonad)
* **Part 7: Summary**
* [List of operators mentioned](https://swlaschin.gitbook.io/fsharpforfunandprofit/functional-patterns/elevated-world-7#operators)
* [Further reading](https://swlaschin.gitbook.io/fsharpforfunandprofit/functional-patterns/elevated-world-7#further-reading)
## Part 2: How to compose world-crossing functions
## The `bind` function
**Common Names**: `bind`, `flatMap`, `andThen`, `collect`, `SelectMany`
**Common Operators**: `>>=` (left to right), `=<<` (right to left )
**What it does**: Allows you to compose world-crossing ("monadic") functions
**Signature**: `(a->E) -> E -> E`. Alternatively with the parameters reversed: `E -> (a->E) -> E`
### Description
We frequently have to deal with functions that cross between the normal world and the elevated world.
For example: a function that parses a `string` to an `int` might return an `Option` rather than a normal `int`, a function that reads lines from a file might return `IEnumerable`, a function that fetches a web page might return `Async`, and so on.
These kinds of "world-crossing" functions are recognizable by their signature `a -> E`; their input is in the normal world but their output is in the elevated world. Unfortunately, this means that these kinds of functions cannot be linked together using standard composition.
What "bind" does is transform a world-crossing function (commonly known as a "monadic function") into a lifted function `E -> E`.
The benefit of doing this is that the resulting lifted functions live purely in the elevated world, and so can be combined easily by composition.
For example, a function of type `a -> E` cannot be directly composed with a function of type `b -> E`, but after `bind` is used, the second function becomes of type `E -> E`, which *can* be composed.
In this way, `bind` lets us chain together any number of monadic functions.
### Alternative interpretation
An alternative interpretation of `bind` is that it is a *two* parameter function that takes a elevated value (`E`) and a "monadic function" (`a -> E`), and returns a new elevated value (`E`) generated by "unwrapping" the value inside the input, and running the function `a -> E` against it. Of course, the "unwrapping" metaphor does not work for every elevated world, but still it can often be useful to think of it this way.
### Implementation examples
Here are some examples of defining `bind` for two different types in F#:
```fsharp
module Option =
// The bind function for Options
let bind f xOpt =
match xOpt with
| Some x -> f x
| _ -> None
// has type : ('a -> 'b option) -> 'a option -> 'b option
module List =
// The bind function for lists
let bindList (f: 'a->'b list) (xList: 'a list) =
[ for x in xList do
for y in f x do
yield y ]
// has type : ('a -> 'b list) -> 'a list -> 'b list
```
Notes:
* Of course, in these two particular cases, the functions already exist in F#, called `Option.bind` and `List.collect`.
* For `List.bind` I'm cheating again and using `for..in..do`, but I think that this particular implementation shows clearly how bind works with lists.
There is a purer recursive implementation, but I won't show that here.
### Usage example
As explained at the beginning of this section, `bind` can be used to compose cross-world functions. Let's see how this works in practice with a simple example.
First let's say we have a function that parses certain `string`s into `int`s. Here's a very simple implementation:
```fsharp
let parseInt str =
match str with
| "-1" -> Some -1
| "0" -> Some 0
| "1" -> Some 1
| "2" -> Some 2
// etc
| _ -> None
// signature is string -> int option
```
Sometimes it returns a int, sometimes not. So the signature is `string -> int option` -- a cross-world function.
And let's say we have another function that takes an `int` as input and returns a `OrderQty` type:
```fsharp
type OrderQty = OrderQty of int
let toOrderQty qty =
if qty >= 1 then
Some (OrderQty qty)
else
// only positive numbers allowed
None
// signature is int -> OrderQty option
```
Again, it might not return an `OrderQty` if the input is not positive. The signature is therefore `int -> OrderQty option` -- another cross-world function.
Now, how can we create a function that starts with an string and returns an `OrderQty` in one step?
The output of `parseInt` cannot be fed directly into `toOrderQty`, so this is where `bind` comes to the rescue!
Doing `Option.bind toOrderQty` lifts it to a `int option -> OrderQty option` function and so the output of `parseInt` can be used as input, just as we need.
```fsharp
let parseOrderQty str =
parseInt str
|> Option.bind toOrderQty
// signature is string -> OrderQty option
```
The signature of our new `parseOrderQty` is `string -> OrderQty option`, yet another cross-world function. So if we want to do something with the `OrderQty` that is output we may well have to use `bind` again on the next function in the chain.
### Infix version of bind
As with `apply`, using the named `bind` function can be awkward, so it is common to create an infix version, typically called `>>=` (for left to right data flow) or `=<<` (for right to left data flow) .
With this in place you can write an alternative version of `parseOrderQty` like this:
```fsharp
let parseOrderQty_alt str =
str |> parseInt >>= toOrderQty
```
You can see that `>>=` performs the same kind of role as pipe (`|>`) does, except that it works to pipe "elevated" values into cross-world functions.
### Bind as a "programmable semicolon"
Bind can be used to chain any number of functions or expressions together, so you often see code looking something like this:
```fsharp
expression1 >>=
expression2 >>=
expression3 >>=
expression4
```
This is not too different from how an imperative program might look if you replace the `>>=` with a `;`:
```fsharp
statement1;
statement2;
statement3;
statement4;
```
Because of this, `bind` is sometimes called a "programmable semicolon".
### Language support for bind/return
Most functional programming languages have some kind of syntax support for `bind` that lets you avoid having to write a series of continuations or use explicit binds.
In F# it is (one component) of computation expressions, so the following explicit chaining of `bind`:
```fsharp
initialExpression >>= (fun x ->
expressionUsingX >>= (fun y ->
expressionUsingY >>= (fun z ->
x+y+z ))) // return
```
becomes implicit, using `let!` syntax:
```fsharp
elevated {
let! x = initialExpression
let! y = expressionUsingX x
let! z = expressionUsingY y
return x+y+z }
```
In Haskell, the equivalent is the "do notation":
```fsharp
do
x <- initialExpression
y <- expressionUsingX x
z <- expressionUsingY y
return x+y+z
```
And in Scala, the equivalent is the "for comprehension":
```fsharp
for {
x <- initialExpression
y <- expressionUsingX(x)
z <- expressionUsingY(y)
} yield {
x+y+z
}
```
It's important to emphasize that you do not *have* to use the special syntax when using bind/return. You can always use `bind` or `>>=` in the same way as any other function.
### Bind vs. Apply vs. Map
The combination of `bind` and `return` are considered even more powerful than `apply` and `return`, because if you have `bind` and `return`, you can construct `map` and `apply` from them, but not vice versa.
Here's how bind can be used to emulate `map`, for example:
* First, you construct a world-crossing function from a normal function by applying `return` to the output.
* Next, convert this world-crossing function into a lifted function using `bind`. This gives you the same result as if you had simply done `map` in the first place.
Similarly, `bind` can emulate `apply`. Here is how `map` and `apply` can be defined using `bind` and `return` for Options in F#:
```fsharp
// map defined in terms of bind and return (Some)
let map f =
Option.bind (f >> Some)
// apply defined in terms of bind and return (Some)
let apply fOpt xOpt =
fOpt |> Option.bind (fun f ->
let map = Option.bind (f >> Some)
map xOpt)
```
At this point, people often ask "why should I use `apply` instead of `bind` when `bind` is more powerful?"
The answer is that just because `apply` *can* be emulated by `bind`, doesn't mean it *should* be. For example, it is possible to implement `apply` in a way that cannot be emulated by a `bind` implementation.
In fact, using `apply` ("applicative style") or `bind` ("monadic style") can have a profound effect on how your program works! We'll discuss these two approaches in more detail in [part 3 of this post](https://swlaschin.gitbook.io/fsharpforfunandprofit/functional-patterns/elevated-world-3#dependent).
### The properties of a correct bind/return implementation
As with `map`, and as with `apply`/`return`, a correct implementation of the `bind`/`return` pair should have some properties that are true no matter what elevated world we are working with.
There are three so-called ["Monad Laws"](https://en.wikibooks.org/wiki/Haskell/Understanding_monads#Monad_Laws), and one way of defining a **Monad** (in the programming sense) is to say that it consists of three things: a generic type constructor `E` plus a pair of functions (`bind` and `return`) that obey the monad laws. This is not the only way to define a monad, and mathematicians typically use a slightly different definition, but this one is most useful to programmers.
Just as with the the Functor and Applicative laws we saw earlier, these laws are quite sensible.
First, note that `return` function is itself a cross-world function:
That means that we can use `bind` to lift it into a function in the elevated world. And what does this lifted function do? Hopefully, nothing! It should just return its input.
So that is exactly the first monad law: it says that this lifted function must be the same as the `id` function in the elevated world.
The second law is similar but with `bind` and `return` reversed. Say that we have a normal value `a` and cross-world function `f` that turns an `a` into a `E`.
Let's lift both of them to the elevated world, using `bind` on `f` and `return` on `a`.
Now if we apply the elevated version of `f` to the elevated verson of `a` we get some value `E`.
On the other hand if we apply the normal version of `f` to the normal verson of `a` we *also* get some value `E`.
The second monad law says that these two elevated values (`E`) should be the same. In other words, all this binding and returning should not distort the data.
The third monad law is about associativity.
In the normal world, function composition is associative. For example, we could pipe a value into a function `f` and then take that result and pipe it into another function `g`. Alternatively, we can compose `f` and `g` first into a single function and then pipe `a` into it.
```fsharp
let groupFromTheLeft = (a |> f) |> g
let groupFromTheRight = a |> (f >> g)
```
In the normal world, we expect both of these alternatives to give the same answer.
The third monad law says that, after using `bind` and `return`, the grouping doesn't matter either. The two examples below correspond to the examples above:
```fsharp
let groupFromTheLeft = (a >>= f) >>= g
let groupFromTheRight = a >>= (fun x -> f x >>= g)
```
And again, we expect both of these to give the same answer.
## List is not a monad. Option is not a monad.
If you look at the definition above, a monad has a type constructor (a.k.a "generic type") *and* two functions *and* a set of properties that must be satisfied.
The `List` data type is therefore just one component of a monad, as is the `Option` data type. `List` and `Option`, by themselves, are not monads.
It might be better to think of a monad as a *transformation*, so that the "List monad" is the transformation that converts the normal world to the elevated "List world", and the "Option monad" is the transformation that converts the normal world to the elevated "Option world".
I think this is where a lot of the confusion comes in. The word "List" can mean many different things:
1. A concrete type or data structure such as `List`.
2. A type constructor (generic type): `List`.
3. A type constructor and some operations, such as a `List` class or module.
4. A type constructor and some operations and the operations satisfy the monad laws.
Only the last one is a monad! The other meanings are valid but contribute to the confusion.
Also the last two cases are hard to tell apart by looking at the code. Unfortunately, there have been cases where implementations did not satisfy the monad laws. Just because it's a "Monad" doesn't mean that it's a monad.
Personally, I try to avoid using the word "monad" on this site and focus on the `bind` function instead, as part of a toolkit of functions for solving problems rather than an abstract concept.
So don't ask: Do I have a monad?
Do ask: Do I have useful bind and return functions? And are they implemented correctly?
## Summary
We now have a set of four core functions: `map`, `return`, `apply`, and `bind`, and I hope that you are clear on what each one does.
But there are some questions that have not been addressed yet, such as "why should I choose `apply` instead of `bind`?", or "how can I deal with multiple elevated worlds at the same time?"
In the [next post](https://swlaschin.gitbook.io/fsharpforfunandprofit/functional-patterns/map-and-bind-and-apply-oh-my/elevated-world-3) we'll address these questions and demonstrate how to use the toolset with a series of practical examples.
*UPDATE: Fixed error in monad laws pointed out by @joseanpg. Thanks!*