-This is a long, not-well-organized list of lots of things. We'll clearn it up later. Also, I'm posting this Thursday morning around 9 in case any of you has time and inclination to look at it today. I'll probably extend and update it later today or tomorrow.
+This is a long, not-well-organized list of lots of things. We'll clean it up later. Also, I'm posting this Thursday morning around 9 in case any of you has time and inclination to look at it today. I'll probably extend and update it later today or tomorrow.
In the homework session on Wed Apr 1, we began by discussing the fact that different monads (so far we've considered the super-simple Identity Monad, as well as the Option/Maybe, List, and Reader monads; other commonly-referenced monads include leaf-labeled Trees, State which we'll discuss in the seminar on Thu Apr 2, as well as Writer (State is a kind of unified melding of Reader + Writer), and Error, which is like Option/Maybe except that what corresponds to the None/Nothing variant now has a parameter, so you can attach error messages or the like. A sample type declaration of this sort would be:
in this way. (Conventionally, they understand the `Right` variant to be the successful/good/correct one.) Another major monad is the Continuation monad, but we'll get to this later in the course when we discuss continuations.
-Those are the most famous Major Players in the Monad world. There are lots of other monads, many of them simple little things which are easy to understand once you've grasped these major players. There are some other quite substantial and interesting monads that we won't study---for example, there's a [Probability monad](https://www.google.com/search?q=probability monad). But the ones listed above are the most commonly-used and -referenced.
+Those are the most famous Major Players in the Monad world. There are lots of other monads, many of them simple little things which are easy to understand once you've grasped these major players. There are some other quite substantial and interesting monads that we won't study --- for example, there's a [Probability monad](https://www.google.com/search?q=probability monad). But the ones listed above are the most commonly-used and -referenced.
-When desiging a monad, you have to choose how to implement the box type (in other terms your programming language already understands), and then you have to combine that with definitions for mid/unit/return/pure/eta/whatever-you-call-it, one the one hand---what we're symbolizing as `⇧`---and one of the other key monadic operations, like `>>=` or `<=<` or `join`. Many implementations use `>>=` here. Let's focus on the choice of box type for the moment.
+When desiging a monad, you have to choose how to implement the box type (in other terms your programming language already understands), and then you have to combine that with definitions for mid/unit/return/pure/eta/whatever-you-call-it, one the one hand --- what we're symbolizing as `⇧` --- and one of the other key monadic operations, like `>>=` or `<=<` or `join`. Many implementations use `>>=` here. Let's focus on the choice of box type for the moment.
For the Identity and Option/Maybe and List monads (and also the leaf-labeled Tree monad), these box types are non-functional. Consider:
mid x = fun e -> x
-that is, the constant function that takes an `env` and ignores it, just returning the payload `x`. This is our friend the **K** combinator. The type of this function is <code>'a -> <u>'a</u></code>.
+that is, the constant function that takes an `env` and ignores it, just returning the payload `x`. This is our friend the **K** combinator. The type of function `mid` is <code>'a -> <u>'a</u></code>, where the argument `x` is of type `'a` and the `fun e -> x` result is of type <code><u>'a</u></code>.
The choice for `>>=` for the Reader monad is a bit more complex. I'll write it out longhand first; that will be easier to compare to the State monad when we look at it instead. You will see that the `>>=` for Reader is a kind of simplification of the `>>=` for State. Here is the longhand version of the `>>=` for Reader:
(>>=) xx k = ...
-The type of this operation `>>=` has to be <code><u>'a</u> -> ('a -> <u>'b</u>) -> <u>'b</u></code>. I'll use the variable `xx` for the instance the boxed type <code><u>'a</u></code>, in a way reminiscent of how we used `xs` as a variable for lists or such. (Which are themselves a boxed type, so on this naming scheme we could also call them `xx`.) I'll use the variable `k` for the "Kleisli" function of type <code>('a -> <u>'b</u>)</code>. Ok, so the application of `>==` to `xx` and `k` has to have the result type <code><u>'b</u></code>, which we said is `env -> 'b`. So we should expect our definition to have the form `fun env -> SOMETHING`, where `SOMETHING` has type `'b`:
+The type of this operation `>>=` has to be <code><u>'a</u> -> ('a -> <u>'b</u>) -> <u>'b</u></code>. I'll use the variable `xx` for the instance of the boxed type <code><u>'a</u></code>, in a way reminiscent of how we used `xs` as a variable for lists or such. (Which are themselves a boxed type, so on this naming scheme we could also call them `xx`.) I'll use the variable `k` for the "Kleisli" function of type <code>('a -> <u>'b</u>)</code>. Ok, so the application of `>==` to `xx` and `k` has to have the result type <code><u>'b</u></code>, which we said is `env -> 'b`. So we should expect our definition to have the form `fun env -> SOMETHING`, where `SOMETHING` has type `'b`:
(>>=) xx k = fun e ->
let x = xx e in
(>>=) xx k = fun e -> k (xx e) e
-which is what you'll often see instead in our notes (and elsewhere). It may be helpful to notice some equivalent transformations of `fun e -> k (xx e) e`. That's the same as `fun e -> flip k e (xx e)`. (`flip k` works just like `k` but expects its arguments in "flipped" order. `flip` is defined as `fun f x y -> f y x`.) But then that's of the form `fun e -> (something) e (something_else e)`. Which is just `S something something_else`, using our friend the **S** combinator. So `fun e -> k (xx e) e` is equivalent to: `S (flip k) xx`. This is also what Jacobson's **Z** combinator. Thus for the Reader implementation of `>>=`:
+which is what you'll often see instead in our notes (and elsewhere). It may be helpful to notice some equivalent transformations of `fun e -> k (xx e) e`. That's the same as `fun e -> flip k e (xx e)`. (`flip k` works just like `k` but expects its arguments in "flipped" order. `flip` is defined as `fun f x y -> f y x`.) But then that's of the form `fun e -> (something) e (something_else e)`. Which is just `S something something_else`, using our friend the **S** combinator. So `fun e -> k (xx e) e` is equivalent to: `S (flip k) xx`. This is also what Jacobson's **Z** combinator does. Thus for the Reader implementation of `>>=`:
xx >>= k
<~~> fun e -> k (xx e) e
TODO Capitalization / type declaration syntaxes comparison
-TODO Haskell's $ vs OCaml' @@ and |>; Haskell's @-vs-as, OCaml's @-vs-(++)
-
-
Some programming languages demand, and even when not there is often a custom, of having just one module per source-code file. When you write a stand-alone Haskell or OCaml program, you'll have one source-code file that has your topmost program logic, usually declaring a function called `main`. This is what gets invoked when you tell your operating system to run the program, at the command line or by double-clicking its icon or whatever. That source-code file may and usually will also use functions (and other values) from various other libraries/modules, residing in separate files. In an interactive Haskell or OCaml session, you will also often want to use functions (and other values) already defined in various libraries/modules, rather than ones you input right now at the interactive prompt.
There are several routes to using these other modules (I'll just stick with "modules" henceforth, rather than always saying "libraries or modules"), and they often involve several steps. First, the file that contains the module, either in source code format or pre-compiled into some binary form, has to be located somewhere where your Haskell or OCaml system knows where to find it. Let's call the list of locations they know to look the *module search paths*. It will be a list of one or more directories on your computer.
-Second, the Haskell or OCaml system has to *load* that module into memory, and prepare to use it. They typically don't do this for all the modules that reside in directoties they know about. One reason is that would take up substantial time and memory. This is especially true if that modules exist in source code format and haven't been compiled into binary form; but it's still true even when the pre-compiled binaries do exist. A second reason is that some of the modules may not work perfectly with each other. So typically only a small selection of modules is automatically pre-loaded. In Haskell, this automatically pre-loaded module is called `Prelude`, and in OCaml it's called `Pervasives`.
+Second, the Haskell or OCaml system has to *load* that module into memory, and prepare to use it. They typically don't do this for all the modules that reside in directoties they know about. One reason is that would take up substantial time and memory. This is especially true if that modules exist in source code format and haven't been compiled into binary form; but it's still true even when the pre-compiled binaries do exist. A second reason is that some of the modules may not work perfectly with each other. So typically only a small selection of modules is automatically pre-loaded. In Haskell, among the automatically pre-loaded modules is a special one called `Prelude`, and in OCaml a corresponding one called `Pervasives`. We'll discuss what makes these special shortly.
Third, there is the question of how to specify the functions (and other values) defined in the module. As we said, you can do this in Haskell and OCaml using the "dotted" forms `Data.List.map` and `List.map`. There are also some shortcuts, if you are going to want to often refer to several values from the same library. One shortcut is to rename a long module name like `Data.List` to just `L`. In Haskell you do this with:
type color = Red | Green | Blue | Gray of int
end
-and that defines `M` to be the specified module. Now this module has a type, just like values have types. By default, the type of the module includes all the types declared in the module (here, the type `color`), and the types of all the vsriables bound at the top-level in the module (here, the variables `x` and `foo`). Thus if you typed the above in the interactive OCaml program, it would say:
+and that defines `M` to be the specified module. Now this module has a type, just like values have types. By default, the type of the module includes all the types declared in the module (here, the type `color`), and the types of all the variables bound at the top-level in the module (here, the variables `x` and `foo`). Thus if you typed the above in the interactive OCaml program, it would say:
module M :
sig
Prelude>
-What appears before the `>` may be different. At the prompt you can type special commands that begin with a `:`. You can get a list of some of them by typing `:?` then <code><i>return</i></code>, or `:help` then <code><i>return</i></code>. We will discuss the most important ones of these to learn early, as well as talk about how to define some additional helpful special commands elsewhere. But two of most useful are illustrated below:
+What appears before the `>` may be different. At the prompt you can type special commands that begin with a `:`. You can get a list of some of them by typing `:?` then <code><i>return</i></code>, or `:help` then <code><i>return</i></code>. We will discuss elsewhere the most important ones of these to learn early, as well as how to define some additional helpful special commands. But two of most useful are illustrated below:
Prelude> :type map
map :: (a -> b) -> [a] -> [b]
- : int L.t = <abstr>
-That is, some unnamed value whose type is `int L.t`. `_ L.t` is the monadic box type from module `L`, here it is parameterized on the type `int`. So we know we have an <code><u>int</u></code> using the List monad box type. But OCaml doesn't display this as an `int list`, and won't let you apply the usual list functions like `List.take` to it, and also can't display the
y list's contents, because the type in question is, as OCaml says `<abstr>`.
+That is, some unnamed value whose type is `int L.t`. `_ L.t` is the monadic box type from module `L`, here it is parameterized on the type `int`. So we know we have an <code><u>int</u></code> using the List monad box type. But OCaml doesn't display this as an `int list`, and won't let you apply the usual list functions like `List.take` to it, and also can't display the
list's contents, because the type in question is, as OCaml says, `<abstr>`.
However, the OCaml Monad libraries also supply a function we call `run`, mostly following Haskell, though we might also have called it `expose`. This function takes you from the abstract List monad box type to its real implementation. Thus if we say:
Here the type `L.result` is an alias for the real implementation of the List monad box type, and OCaml can show us the value. Computationally, `run` here is just an identity function, but it takes us from the one type to another type, where the underlying implementation of the types is the same. (In a few of the monads, the `run` function does more than this.)
-Why make thins so hard, Linmin asked. If it's really just an `int list` behind the scenes, why make us jump through these extra hoops to get at it? Four points to consider in response. (I hesitate to call all of them strictly "responses".) First, this parallels what Haskell does with some of its Monadic operations. Thus if I say:
+Why make things so hard, Linmin asked. If it's really just an `int list` behind the scenes, why make us jump through these extra hoops to get at it? Four points to consider in response. (I hesitate to call all of them strictly "responses".) First, this parallels what Haskell does with some of its Monadic operations. Thus if I say:
Prelude Control.Monad.Reader> let x = return 1 :: Reader [Int] Int
Prelude Control.Monad.Reader> :t x
xx >>= k
-works, this won't work: `(run xx) >>= k`. Even though `xx` and `run xx` may be the same underlying data in OCaml's memory. Forcing you to use the monadic machinery to manipulate `xx`, rather than doing it by hand, has pedagogical and conceptual value. That is the second response point. If you want to write your own implementations of the monadic operations, which is pretty straightforward for the simple, atomic monads we've been looking at so far, you don't need to introduce the abstraction barriers we have, and so you can do dirty non-monadic hacking on your boxed values and still use your own monadic operations on them if you like. But this takes us to the third response point. This is that pretty soon we are going to be working with *combinations* of monads, not just the atomic Reader and List and so on, but combinations of two or three monads at once. The types for these can get pretty complex and intertwined. In the general case, the combinaton of a box1 type and a box2 type, parameterized on type `'a`, will *not* just be an `'a box1 box2`. There generally has to be more complex ways for the types to be intertwined. When you look at the concrete implementations of some of these complex monadic types, it can be pretty confusing what's going on, and what type in your mental model the thing you're looking at really belongs too. Whereas if OCaml tells you this is an `int Foo.t`, you can say OK, now I now what this is, even if `Foo.t` is a complex box type that combines the behavior of several monads and has a gnarly concrete implementing type.
+works, this won't work: `(run xx) >>= k`. Even though `xx` and `run xx` may be the same underlying data in OCaml's memory. Forcing you to use the monadic machinery to manipulate `xx`, rather than doing it by hand, has pedagogical and conceptual value. That is the second response point. If you want to write your own implementations of the monadic operations, which is pretty straightforward for the simple, atomic monads we've been looking at so far, you don't need to introduce the abstraction barriers we have, and so you can do dirty non-monadic hacking on your boxed values and still use your own monadic operations on them if you like. But this takes us to the third response point. This is that pretty soon we are going to be working with *combinations* of monads, not just the atomic Reader and List and so on, but combinations of two or three monads at once. The types for these can get pretty complex and intertwined. In the general case, the combinaton of a box1 type and a box2 type, parameterized on type `'a`, will *not* just be an `'a box1 box2`. There generally has to be more complex ways for the types to be intertwined. When you look at the concrete implementations of some of these complex monadic types, it can be pretty confusing what's going on, and what type in your mental model the thing you're looking at really belongs to. Whereas if OCaml tells you this is an `int Foo.t`, you can say OK, now I now what this is, even if `Foo.t` is a complex box type that combines the behavior of several monads and has a gnarly concrete implementing type.
-The fourth response point is that sometimes you might be using the same implementation for different theoretical roles. I'll make this point first using a non-monadic example. Go back to our discussion of different ways to implement sets. Perhaps you choose one of the implementations where `int set`s are just `int list`s. Now you might also have an implementation of `int multiset`s (multisets are similar to sets in ignoring order, but dissimilar in that they care about multiplicity: so the `int multiset` that contains `3` once is not the same as the one that contains it twice). And you might also implement them as `int list`s. But now if you get from one source an `int list`, perhaps that was intended to be a set, but you forgot and went on to use it as though it were a multiset. That could make for conceptual trouble. I don't mean your code will crash; perhaps it won't. But assumptions you were relying on in order for the code to do what you want may be violated because you thought you had an instance of one type satisfying one algebra, and instead you had an instance of a different type (with the same concrete representation in memory) satisfying a somewhat different algebra. You can avoid this kind of problem by introducing abstraction barriers. They prevent you from using `int set`s and `int multiset`s, and vice versa, even when both are implemented behind the scenes as the same same `int list`.
+The fourth response point is that sometimes you might be using the same implementation for different theoretical roles. I'll make this point first using a non-monadic example. Go back to our discussion of different ways to implement sets. Perhaps you choose one of the implementations where `int set`s are just `int list`s. Now you might also have an implementation of `int multiset`s (multisets are similar to sets in ignoring order, but dissimilar in that they care about multiplicity: so the `int multiset` that contains `3` once is not the same as the one that contains it twice). And you might also implement them as `int list`s. But now if you get from one source an `int list`, perhaps that was intended to be a set, but you forgot and went on to use it as though it were a multiset. That could make for conceptual trouble. I don't mean your code will crash; perhaps it won't. But assumptions you were relying on in order for the code to do what you want may be violated because you thought you had an instance of one type satisfying one algebra, and instead you had an instance of a different type (with the same concrete representation in memory) satisfying a somewhat different algebra. You can avoid this kind of problem by introducing abstraction barriers. They prevent you from using `int set`s as `int multiset`s, and vice versa, even when both are implemented behind the scenes as the same same `int list`.
The same point applies in the monadic case too. You might have two Reader monad types, each implemented on an `int` environment type, but in the one case it's playing the role of Jacobson-style variable binding for a single pronoun (of type `int`), and in the other case your `int`s are possible worlds and it's playing the role of modeling intensionality. The same bytes in memory could be used for each purpose, but you won't yourself want to become confused and use the one thing as the other. This is just like `set`s and (perhaps only some) `multiset`s having the same implementation. Abstraction barriers can help you keep these apart.
Haskell and other languages do this much more extensively.
-In what's called *object-oriented programming*, you specify various interfaces, called *classes*. Some of these classes "inherit" from, or in other words *extend*, others. Finally, you can have values that are instances of some of these classes, conventionally these values are called *objects*. As an example, perhaps I have the general class `Animal`, and then one inheriting subclass will be `Dog`. `Dog`s will have the same interface that `Animal`s do, but may have additional interface elements too. And then `fido` may be an object that belongs to (both of) these classes. I might then have some functions that expect an `Animal` as argument, and any `Dog` like `fido` would be acceptable input to these functions; other functions might more specifically demand `Dog` inputs, and not be defined for other types of `Animal`. In some cases the hierarchy of class interfaces we're working with might not have a simple tree structure. Perhaps `fido` is, as well as being an `Animal`, also `HouseholdOccupant`, and this class be partly disjoint from the class of `Animal`s. (Furniture also occupies my household but isn't an animal.) How to deal with the complexities that arise here can become difficult. A famous example discussed in the literature is "the Nixon diamond". Nixon belonged to the class `Quaker` but also to the class `Republican`, and naively we might model `Quakers` as having some interface choices---for example, being pacifists---that we don't model `Republican`s as having. Figuring out how to sort this out gets complicated, and is important both for modeling reasoning, and for designing programming systems that use this general strategy for specifying interfaces.
+In what's called *object-oriented programming*, you specify various interfaces, called *classes*. Some of these classes "inherit" from, or in other words *extend*, others. Finally, you can have values that are instances of some of these classes, conventionally these values are called *objects*. As an example, perhaps I have the general class `Animal`, and then one inheriting subclass will be `Dog`. `Dog`s will have the same interface that `Animal`s do, but may have additional interface elements too. And then `fido` may be an object that belongs to (both of) these classes. I might then have some functions that expect an `Animal` as argument, and any `Dog` like `fido` would be acceptable input to these functions; other functions might more specifically demand `Dog` inputs, and not be defined for other types of `Animal`. In some cases the hierarchy of class interfaces we're working with might not have a simple tree structure. Perhaps `fido` is, as well as being an `Animal`, also a `HouseholdOccupant`, and this class may be partly disjoint from the class of `Animal`s. (Furniture also occupies my household but isn't an animal.) How to deal with the complexities that arise here can become difficult. A famous example discussed in the literature is "the Nixon diamond". Nixon belonged to the class `Quaker` but also to the class `Republican`, and naively we might model `Quakers` as having some interface choices --- for example, being pacifists --- that we don't model `Republican`s as having. Figuring out how to sort this out gets complicated, and is important both for modeling reasoning, and for designing programming systems that use this general strategy for specifying interfaces.
Haskell's design is in this general family. They have what they call "typeclasses", and these are instantiated by specific "types". So typeclasses aren't types but rather properties or families of types. What defines a typeclass are certain constraints --- perhaps to belong to this typeclass, you also have to belong to some others --- and that you provide some implementation or other for certain symbols. But the implementation could be very different from instance to instance. Also, in many cases the typeclass will be associated with some algebraic laws, like the Laws we've seen in our discussions of Monads. These aren't anything that the computer tries to verify; but they are assumptions that the programmers rely on in designing and working with these typeclasses, so if you violate them some things may turn out to be broken.
Prelude> data Sum = Sum Int deriving (Eq, Ord, Show)
Prelude> instance Dot Sum where { (*) (Sum x) (Sum y) = Sum (x+y) }
-The `data ...` is one of the (several) ways Haskell has for declaring a new type. The `deriving (Eq, Ord, Show)` at the end means you want Haskell to figure out automatically how to apply `=` and `<` to values of these types (using the underlying parameter type `Int`), and also how to print such values. The second line says that we *do* satisfy the interface we're calling `Dot`, and in particular here is how we implement the operations that one needs to implement to count as doing so... Note that in the definition of the type I used the same symbol `Dot` to name both the type and the tag/variant label/constructor. You don't have to use the same symbol, but it's common to do so. In OCaml these have different capitalization rules, so the corresponding type declaration looks like this:
+The `data ...` is one of the (several) ways Haskell has for declaring a new type. The `deriving (Eq, Ord, Show)` at the end means you want Haskell to figure out automatically how to apply `=` and `<` to values of these types (using the underlying parameter type `Int`), and also how to print such values. The second line says that we *do* satisfy the interface we're calling `Dot`, and in particular here is how we implement the operations that one needs to implement to count as doing so... Note that in the definition of the type I used the same symbol `Sum` to name both the type and the tag/variant label/constructor. You don't have to use the same symbol, but it's common to do so. In OCaml these have different capitalization rules, so the corresponding type declaration looks like this:
type sum = Sum of int
We can also have such constraints on our original `class` declarations. Whereas we had:
- Prelude> class Dot t where ...
+ class Dot t where ...
Haskell can also have declarations like:
Haskell uses this technique extensively for its Monad interfaces. Monadic box types are specified in terms of the interface they have to supply, analagously to our `Dot` interface and the `Sum` and `Product` types.
Okay, that was all about Option 3 for handling name clashes/ambiguities. Haskell embraces this by letting different types define the symbol differently, and then it figures out what definition to use by figuring out what the argument types are. There are just some common constraints: for example, with the `Dot` interface, the `*`
-function has to take two arguments of the same type and return a result of that type. With other examples, we might also have that if you declare yourself to satisfy the interface, you have to supply several different operations. An loose analogy might be that when I talk to my family, `Mom` might have one meaning, with a corresponding meaning for `Dad`, but then in the AI lab these have different meanings (two different computers) and in MI6 two yet different meanings.
+function has to take two arguments of the same type and return a result of that type. With other examples, we might also have that if you declare yourself to satisfy the interface, you have to supply several different operations. An loose analogy might be that when I talk to my family, `Mom` might have one meaning, with some paired meaning for `Dad`, but then in the AI lab these have different meanings (two different computers) and in MI6 two yet different meanings. (I don't know if there's a "Dad" in MI6, but in the modern Bond movies they called Judi Dench's M character "Mom.")
OK, now let's turn to Option 4, which is OCaml's strategy. We've already discussed OCaml modules and how one might use their type declarations to only expose some part of the module's concrete definitions. A further quirk is that OCaml also permits you to define things that aren't modules but are rather *module makers*, that is things that take certain parameters (these are always other modules, usually small ones), and generate modules as a result. OCaml calls these "functors" which is a shame because Haskell (and category theory) use that term differently. (At least, I assume there is no underlying connection between OCaml's use and the category theory use, though I don't know.) I'll just call them "module makers". The specific syntax for declaring these is not important. What is important is how to use them.
O.(test, mzero, guard)
module L = List.M
L.((++), pick, test, mzero, guard)
- module T = Monad.LTree.M (* LTree for "list-labeled tree" *)
+ module T = Monad.LTree.M (* LTree for "leaf-labeled tree" *)
T.((++))
module I = Monad.Identity.M
module R = Monad.Reader(struct type env = int list end) (* or any other implementation of envs *)
L.(let xx = mid 1 ++ mid 2 ++ mid 3 in let yy = test (fun xs -> List.mem 3 xs) xx >>= fun x -> mid (x+1) in run yy)
-That will construct (an abstract version of) the list `[1; 2; 3]`, bind the variable `xx` to it, and then run `test ... xx >>= fun x -> ...` on that `xx`. The `test` operation checks whether the list we're working with has a `3` as a member; if it didn't we'd get the empty list and the rest of the `... >>= ...` chain would be ignored. (One of the laws for `mzero` is that `mzero >>= ...` is always `mzero`.) In this case we pass the test, and so we extract the "payload" of our monadic value, in this case there are multiple payloads and our definition for `>>=` binds them to the x in `fun x -> ...` in turn, and assembles the results properly. In this case what we do to each payload is increment it by one, and then we have to return `mid` of the result. Since simple `int`s aren't monadic values, but the result of `... >>= fun x -> ...` has to be a monadic value. Then we bind the variable `yy` to the monadic value we've thereby constructed. Finally, we apply `run` to the result to remove the abstraction curtain and see what's there. If you've been following, it will be completely expected that we get:
+That will construct (an abstract version of) the list `[1; 2; 3]`, bind the variable `xx` to it, and then run `test ... xx >>= fun x -> ...` on that `xx`. The `test` operation checks whether the list we're working with has a `3` as a member; if it didn't we'd get the empty list and the rest of the `... >>= ...` chain would be ignored. (One of the laws for `mzero` is that `mzero >>= ...` is always `mzero`.) In this case we pass the test, and so we extract the "payload" of our monadic value, in this case there are multiple payloads and our definition for `>>=` binds them to the `x` in `fun x -> ...` in turn, and assembles the results properly. In this case what we do to each payload is increment it by one, and then we have to return `mid` of the result --- since simple `int`s aren't monadic values, but the result of `... >>= fun x -> ...` has to be a monadic value. Then we bind the variable `yy` to the monadic value we've thereby constructed. Finally, we apply `run` to the result to remove the abstraction curtain and see what's there. If you've been following, it will be completely expected that we get:
- : int L.result = [2; 3; 4]
f (g x)
-The `g x |> f` notation in Haskell is convenient when the `g x` is something monadic and the `f` is `run`. Thus we could write:
+The `g x |> f` notation in OCaml is convenient when the `g x` is something monadic and the `f` is `run`. Thus we could write:
L.(... |> run)