-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.
+*First posted Thursday 2 April; updated Sunday 5 April.*
+## Some major monads; comparing Reader to State ##
-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 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 discussed in the seminar on Thursday, 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:
type ('bad,'good) error = Error of 'bad | OK of 'good
If your tree type has a parameter for inner node labels:
- type ('leaf,'inner) = Leaf of 'leaf | Brancing of ('leaf,'inner) tree * 'inner * ('leaf,'inner) tree
+ type ('leaf,'inner) = Leaf of 'leaf | Branching of ('leaf,'inner) tree * 'inner * ('leaf,'inner) tree
you could also use that as a monadic box type by specifying `unit` for the `'inner` parameter. I believe it's not impossible to use trees with more informative inner node labels as monads, but it requires complex design choices that we're not going to explore. The trees with labels only on their leaves are simpler to think about, to code, and to work with, so they will suit our purposes. It's often helpful to think of Option/Maybe, List, and Tree together, as comparing them helps you to see what the common patterns are, in a way that abstracts from the specifics of those different structures.
type ('env,'a) reader = 'env -> 'a
-because when working with a specific Reader monad, the choice of the `env` type will be fixed once and for all (for that Monad). Whereas that single Monad can be used as a box around `int`s or `bool`s or `int -> bool`, or any type as a instantiation for its type parameter `'a`. (Even the box types of other monads can be used for `'a`---or even the box type for *other Reader monads*, which may have, but needn't have, made different choices for the `env` type. It will emerge (though don't expect it to emerge fully in these notes) why it might be useful to have two different Reader monads that are using the same `env` type, rather than just using one.)
+because when working with a specific Reader monad, the choice of the `env` type will be fixed once and for all (for that Monad). Whereas that single Monad can be used as a box around `int`s or `bool`s or `int -> bool`, or any type as a instantiation for its type parameter `'a`. (Even the box types of other monads can be used for `'a` --- or even the box type for *other Reader monads*, which may have, but needn't have, made different choices for the `env` type. It will emerge (though don't expect it to emerge fully in these notes) why it might be useful to have two different Reader monads that are using the same `env` type, rather than just using one.)
Some example choices for the `env` type are: when using the Reader monad to implement the binding of multiple variables, the `env` will be some kind of association between variables and their denotations. Perhaps it will be a list of pairs of variables and denotations. Or it might (itself) be a function from variables to denotations. For a homework exercise, we'll work with the simple idea that the environment is just a triple of denotations, where variable `x` is associated with the first member of the triple, variable `y` with the second, and variable `z` with the third. (This simple model only permits three variables.) In (the monadic construal of) Jacobson's semantics, the environments are just the denotations themselves for a single pronouns---that is, it's like the homework idea but with only a single variable. If you want to have two pronouns, her system would require you to have two different Reader monads, somehow coordinating so as to not step on each other's toes. Exploring how to do that is another homework assignment. If you want to use the Reader monad to implement intensionality, the `env`s will be possible worlds, something like this:
type env = world
type 'a reader = env -> 'a
-As we'll see when discussing the State monad, this makes a different choice about the box type. Essentially the State monad's box type is this:
+As we saw when discussing the State monad, it makes a different choice about the box type. Essentially the State monad's box type is this:
type 'a state = env -> 'a * env
type 'a reader = env -> 'a
type 'a state = store -> ('a * store)
-OK, now going back to the top, one of the themes I mentioned and has been illustrated in this discussion (though that was not its primary aim) is that the same symbols --- `mid` and `>>` for example --- can be used ambiguously. This not just an example of the polymorphism we discussed before, as when `[]` could be an `int list` or `bool list`, and where `head` can be a function that works for either of those types. In that kind of polymorphism, there is one underlying implementation, that just (may) give us different result types depending on the types of the inputs. But the compuational machinery is constant. In what we're seeing now, though, we have (possibly, and usually) different computational implementations for the different instances of `>>=`.
+
+## How to handle name-clashes? ##
+
+OK, now going back to the top, one of the themes I mentioned and has been illustrated in this discussion (though that was not its primary aim) is that the same symbols --- `mid` and `>>=` for example --- can be used ambiguously. This not just an example of the polymorphism we discussed before, as when `[]` could be an `int list` or `bool list`, and where `head` can be a function that works for either of those types. In that kind of polymorphism, there is one underlying implementation, that just (may) give us different result types depending on the types of the inputs. But the compuational machinery is constant. In what we're seeing now, though, we have (possibly, and usually) different computational implementations for the different instances of `>>=`.
We need to talk about how different languages sort this out. These are design choices. They aren't as fundamental to the programming languages as things like its type system and its evaluation order are. But they do affect your day-to-day interaction with the language in pervasive and noticeable ways.
That works fine for a while, and it's what we've been using in the course so far in an ad hoc way. But it soon becomes unwieldy. And for better or worse, the languages we're working with have chosen more systematic alternatives, which we need to become acquainted with.
+
+## Handling name-clashes with dotted names ##
+
The second method is to have different *namespaces* or *libraries* or *modules*. (The latter two of these terms are used interchangeably. The first may arguably differ from them in some ways, but not in ways relevant to our present discussion.) A common notational convention for these is to use "dotted" names. Thus, in both Haskell and in OCaml, you'd refer to the `map` function from the `List` module or library as `List.map`. In fact, though, Haskell doesn't have any module named `List`; its name instead is `Data.List`, so you'd really say `Data.List.map`. The initial `Data.List` is the name of the module, and the `map` is the value (in this case a function value) that we're referring to that's defined in, and "exported by" (more on this in a moment) that module.
-Another detail is that Haskell *also* uses the `.` to represent functional composition. Thus the expression `f . g` (or you could also write just `f.g`) is equivalent to `\x -> f (g x)`. Some of the potential ambiguity between this and the other use of `.` as in `Data.List.map` is resolved by the fact that modules in Haskell always have to start with capital letters. That also happens to be true in OCaml.
+Another detail is that Haskell *also* uses the `.` to represent function composition. Thus the expression `f . g` (or you could also write just `f.g`) is equivalent to `\x -> f (g x)`. Some of the potential ambiguity between this and the other use of `.` as in `Data.List.map` is resolved by the fact that modules in Haskell always have to start with capital letters. That also happens to be true in OCaml.
+
+In the Juli8 libraries we're supplying for OCaml, you instead express function composition with `%`.
TODO Capitalization / type declaration syntaxes comparison
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, 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.
+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 directories 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:
module L = List
-supplying a *name* for, or module variable bound to, the module we were taking about. At some point, though, you can't just keep using names for modules, you have to provide the module itself. The way you do that in OCaml is with the syntax `struct ... end`. In the middle you can have any of the ordinary top-level declarations you can make in an OCaml file, or at the interactive OCaml session prompt. By "top-level" declaration, we mean things you are allowed to say unembedded in other expressions. So for example you can write things like `let x = 5 in x*x` embedded in larger expressions: `let y = (let x = 5 in x*x) in ...`. But at the top-level, you can *also* say simply `let x = 5` with no further `in ...`. That defines `x` to be the value `5` for the rest of the session (if it's an interactive session) or module (if it's a module or source code file). OCaml also uses the term "toplevel" to refer to their interactive program, that starts up when you just type `ocaml` (rather than `ocaml file.ml`); this is the analogue to Haskell's `ghci`. It's confusing that "toplevel" is used in these two ways. I won't use "toplevel" to denote the OCaml interactive program.
+supplying a *name* for, or module variable bound to, the module we were taking about. At some point, though, you can't just keep using names for modules, you have to provide the module itself. The way you do that in OCaml is with the syntax `struct ... end`. In the middle you can have any of the ordinary top-level declarations you can make in an OCaml file, or at the interactive OCaml session prompt. By "top-level" declaration, we mean things you are allowed to say unembedded in other expressions. So for example you can write things like `let x = 5 in x*x` embedded in larger expressions: `let y = (let x = 5 in x*x) in ...`. But at the top-level, you can *also* say simply `let x = 5` with no further `in ...`. That defines `x` to be the value `5` for the rest of the session (if it's an interactive session) or module (if it's a module or source code file).
+
+<a id=toplevel></a>
+Side note: OCaml also uses the term "Toplevel" to refer to their interactive program, that starts up when you just type `ocaml` (rather than `ocaml file.ml`); this is the analogue to Haskell's `ghci`. It's confusing that "toplevel" is used in these two ways. I won't use "toplevel" to denote the OCaml interactive program.
Thus you can write:
*Inside* the `sig ... end`, you can see the same `type color = ...` declaration you used when supplying the module, and also the type declarations for the values `x` and `foo` that you declared/defined when supplying the module. They appear with the same `val x :` and `val foo :` prefixes we just talked about getting from the interactive interpreter. So now you know what some more of this stuff means.
-Okay, all those specifics aside the general point here is that modules themselves look like this `struct ... end`, they have types, which are expressed by `sig ... end` and the way to bind a module variable (which must begin with a capital letter) to a module (specified either with another variable, or supplied literally with `struct ... end`) is to say `module M = ...`. You can omit the type and OCaml will infer it, just as it does with values. Or you can explicitly specify the type, by saying, for example:
+Okay, all those specifics aside the general point here is that modules themselves look like `struct ... end`; they have types, which are expressed by `sig ... end`; and the way to bind a module variable (which must begin with a capital letter) to a module (specified either with another variable, or supplied literally with `struct ... end`) is to say `module M = ...`. You can omit the type and OCaml will infer it, just as it does with values. Or you can explicitly specify the type, by saying, for example:
module M : sig ... end = struct ... end
module M : sig ... end = List
-Okay, now the key new idea here is that you don't have to supply the *most general type* of the module. You can restrict the type in some ways. Just as when you say:
+Okay, now the key new idea I want now to introduce is that you don't have to supply the *full* type of the module. You can restrict the type in some ways. Just as when you say:
let id = fun x -> x
let id (x : int) : int = x
-Analogously, with the modules, you can restrict the type you assign to `M`. You do this by leaving out some details. Thus for example if we said:
+Somewhat analogously, with the modules, you can restrict the type signature you assign to `M`. With modules, you do this by leaving out some details. Thus for example if we said:
module M : sig
val foo : int -> int
All of these techniques are the OCaml analogue of a Haskell module only exporting some of the symbols (whether for values or for types) that it defines. I've got into this at this much length because you need some familiarity with it to use the monad libraries we're supplying for OCaml, which strongly (but not exactly) parallel those for Haskell. More on those later.
-If you remember, we were talking about different ways languages handle conflicts in names. And we were on Option 2, namely different namespaces or modules/libraries. And we were discussing the Haskell and OCaml ways of doing this, and we had a long side discussion about the different ways they have of only importing or exporting *some restricted subset* of the symbols defined in a module implementation. There are more options for how to handle the name conflicts, really they might be and often are just extensions of Options 2, rather than competitors with it. We will get to them soon. That will flesh out the background we've started to provide for OCaml and Haskell.
+Side note: If you think about it, you may notice a disanalogy between what's happening in OCaml when we restrict the type of a *value* --- there we make the type more specific, that is, less general. And what's happening when we restrict the type signature of a *module* --- there we expose less information about the module, and so in a way make the type *more* general.
+
+If you remember, we were talking about different ways languages handle conflicts in names. And we were on Option 2, namely different namespaces or modules/libraries. And we were discussing the Haskell and OCaml ways of doing this, and we had a long side discussion about the different ways they have of only importing or exporting *some restricted subset* of the symbols defined in a module implementation. There are more options for how to handle the name conflicts. Really they might be and often are just extensions of Options 2, rather than competitors with it. We will get to them soon. That will flesh out the background we've started to provide for OCaml and Haskell.
But before we proceed to the other options, there are two more topics connected to what we've been saying so far that I'll address first. First, special commands to the interactive session, and second, abstraction barriers. Then we'll go back to discussing handling name conflicts.
-Topic 1
+
+## Special interpreter commands ##
Okay, special commands to the interactive programs `ghci` or `ocaml`. These are different from top-level declarations. You can't include them in ordinary source code files. But you can type them to the interactive prompt. In Haskell the interactive prompt looks like this:
and the OCaml special commands begin with `#`. One example of such commands was the `#trace foo` command Chris showed in a previous week, that makes OCaml announce to you every input that the function `foo` ever gets, and what results it outputs. If you want to turn that off, you can type `#untrace f`.
-Supposedly, OCaml has a special command <code>#show <i>symbol</i></code> that works like Haskell's <code>:info <i>symbol</i></code>. But it doesn't work on my system. Maybe this is just in the very latest version of OCaml? which most of us aren't using.
+If you're using a version of OCaml >= 4.02 (you can see the version as `Sys.ocaml_version`), there's also a special command <code>#show <i>symbol</i></code> that works like Haskell's <code>:info <i>symbol</i></code>.
The other useful OCaml special commands are:
* `#load "path/to/file.cmo"` is the way to load a pre-compiled OCaml module. For most (but not all) system-supplied modules, this is unnecessary. For modules you compile yourself (you might not end up doing that, though for the full-featured version of the interpreter from last week's homework, we were guiding you towards doing that) it will be necessary. It looks for `path/to/file.cmo` underneath the various directories it knows about or you have told it about. Pathnames that begin with `/` are from the top of your disk. `.cmo` is one of the suffixes for binary files that OCaml knows about; there are others.
* `#use "path/to/file.ml"` is something like an analogue to the previous command, except that in this case the files loaded are uncompiled source-code files. Also, OCaml reads these files more-or-less as though you had just typed them directly into the interactive session yourself. One interesting difference this involves is that `#load`ed files are *always* modules, that you still need to explictly `open`. (`open` is a part of the ordinary OCaml language, so it has no `#` prefix.) Whereas with `#use`d files, you may not need to do any `open`ing. That depends on whether the `#use`d file defines a symbol directly at its top level, or defines it inside a `module M = struct ... end`.
-Topic 2
-Okay, next abstraction barriers.
+## Abstraction barriers ##
Say that you have to write some implementation of sets (where the elements are of some specified type `elem`). There are various ways you could do this. One way is to just use simple `elem list`s. When you get a new `elem`, you just `cons` it to the front of the list without any special checking. That has some advantages: it's simple and fast to add new elements to the list. But also some disadvantages: it can make it slower to check whether other `elem`s are members of the list, and can make it more complex to define operations like `difference`. A second way is to use lists, but to curate them so as to ensure that the lists never contain duplicates. A third way is to curate the lists so as to ensure that they're additionally always sorted. A fourth implementation might just to be to implement a list as an `int`. If there are only a small finite number of `elem`s, then bit 0 of your `int` could be on if that `elem` belongs to the set, else off; bit 1 could be for the next `elem`; and so on. Another way that sets are often implemented are with trees. Here there is the possibility that different concrete trees, for example `Branching (Leaf 2, Branching (Leaf 3, Leaf 5))` and `Branching (Branching (Leaf 2, Leaf 3), Leaf 5)`, might represent the same set.
The Monad library we provide for OCaml, and some of the Monad facilities in Haskell, have these kinds of abstraction barriers. Thus to use the List Monad functions in our OCaml Monad library, you'd have to say:
- List.M.mid
+ Monad.List.mid
You can shorten this by saying:
- module L = List.M
+ module L = Monad.List
L.mid
and so on. For the Reader Monad it's more complex. We'll explain the details later, but just to give a quick example, you'd need to say:
module R = Monad.Reader(struct type env = ... end)
- module R = R.M (* it doesn't seem possible to combine these two lines into a single step *)
R.mid
and so on.
let xx = L.(mid 1)
L.(xx >>= fun x -> mid x ++ mid x)
-You can nest these, thus you can have `L.( ... Option.M.( ... ) ...)`. In any case, after evaluating those commands, then behind the scenes what you'll have ended up with is the list `[1, 1]`. But that's not what OCaml will show you. It will show you instead:
+You can nest these, thus you can have `L.( ... Monad.Option.( ... ) ...)`. In any case, after evaluating those commands, then behind the scenes what you'll have ended up with is the list `[1, 1]`. But that's not what OCaml will show you. It will show you instead:
- : int L.t = <abstr>
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.
-Okay, that completes the discursion on abstraction barriers. We are back to our main organizing thread, how to handle name conflicts.
+Okay, that completes the discursion on abstraction barriers. Let's return to our main organizing thread, how to handle name conflicts.
+
+
+## Handling name-clashes with overloaded symbols ##
We said Option 2 for handling name conflicts was namespaces or modules, and looked at some of the twists and design choices made by Haskell and OCaml about this.
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.
+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 typeclass so-and-so, 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.
As an example, we could define a typeclass:
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 `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:
+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 to 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
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 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.")
+
+## OCaml's parameterized modules ##
+
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.
Recall the example from before:
module R = Monad.Reader(struct type env = ... end)
- module R = R.M
R.mid
-Here `Monad.Reader` is a module maker, and `struct type env = ... end` is the parameter (you have to fill in the `...` with an actual type, perhaps `int list` or `string -> int`, where `string`s are how you represent variables). First we bind the module variable `R` to the module made by supplying that parameter to the module maker. Next we rebind the variable `R` to just the `M` component of that generated module, which is all we care about for now. Later we'll consider the other components. Then `R` is a monad library, just like `List.M` and `Option.M` are. (For `List` and `Option`, you don't have to but you can use the prefatory `Monad.`.)
+Here `Monad.Reader` is a module maker, and `struct type env = ... end` is the parameter (you have to fill in the `...` with an actual type, perhaps `int list` or `string -> int`, where `string`s are how you represent variables). First we bind the module variable `R` to the module made by supplying that parameter to the module maker. Then `R` is a monad library, just like `Monad.List` and `Monad.Option` are.
-Here is some code showing how to generate the common monad modules, and also some additional values defined in each module, beyond the core monad operations.
+Here is some code showing how to generate the common monad modules, and also some additional values defined in each module, beyond the core monad operations. This code assumes you have [[installed the Juli8 libraries for OCaml|/juli8]].
- #use "juli8.ml"
- #use "monad.ml"
- module O = Option.M
+ module O = Monad.Option
O.(test, mzero, guard)
- module L = List.M
+ module L = Monad.List
L.((++), pick, test, mzero, guard)
- module T = Monad.LTree.M (* LTree for "leaf-labeled tree" *)
+ module T = Monad.LTree (* LTree for "leaf-labeled tree" *)
T.((++))
- module I = Monad.Identity.M
+ module I = Monad.Identity
module R = Monad.Reader(struct type env = int list end) (* or any other implementation of envs *)
- module R = R.M
R.(ask, asks, shift) (* same additional interface as Haskell has; we'll explain them later *)
module S = Monad.State(struct type store = int end) (* or any other implementation of stores *)
- module S = S.M
S.(get,gets,put,modify) (* same additional interface as Haskell has; we'll explain them later *)
module Ref = Monad.Ref(struct type value = string end) (* this is essentially a State monad, but with a different interface *)
- module Ref = Ref.M
Ref.(newref,deref,change)
module W = Monad.Writer(struct type log = string let empty = "" let append = (^) end) (* or any other implementation of logs *)
- module W = W.M
W.(listen,listens,tell,censor)
module E = Monad.Error(struct type err = string exception Exc = Failure end) (* or other specifications of type err and exception Exc of err *)
- module E = E.M
E.(throw, catch)
These mostly have to be entered as individual lines in the interactive interpreter, separated by `;;` and <code><i>return</i></code>s.
There remains a final major Monad, the Continuation monad, that we'll discuss and add to the library later.
-We'll discuss the different `ask, shift, pick`, and so on functions later. But just to give some examples, in the List monad, `mzero` corresponds to `[]` and `++` as we mentioned before corresponds to `List.append`, which OCaml also writes as the infix operator `@`. For some reason I don't like that operator, so I mostly avoid it. Maybe I don't like it because Haskell uses it with a different meaning. In Haskell, <code><i>var</i> @ <i>pat</i></code> is what OCaml writes as <code><i>pat</i> as <i>var</i></code>. (Discussed in Rosetta1.) So I tend to write instead just `List.append`. But when working with Lists as abstract monadic values, in OCaml, you need to use `++` instead of `List.append`. OCaml will act like it doesn't know that abstract monadic Lists are really `list`s. `pick` takes an abstract monadic list like `[1;2;3]` and returns the list `[(1,[2;3]); (2,[1;3]); (3,[1;2])]` (only as an abstract list). `test` takes a predicate of plain (non-monadic) lists, and if the monadic list that is its second argument satisfies it, returns that list unchanged, else returns mzero (the abstract list version of `[]`). `guard` takes a boolean argument, and if it's true returns `[()]` (as an abstract list) else returns `mzero`. These last two operations correspond to the Haskell operations of the same name.
+We'll discuss the different `ask, shift, pick`, and so on functions [[on another page|/topics/week9_using_the_monad_library/]]. But just to give some examples, in the List monad, `mzero` corresponds to `[]` and `++` as we mentioned before corresponds to `List.append`, which OCaml also writes as the infix operator `@`. For some reason I don't like that operator, so I mostly avoid it. Maybe I don't like it because Haskell uses it with a different meaning. In Haskell, <code><i>var</i> @ <i>pat</i></code> is what OCaml writes as <code><i>pat</i> as <i>var</i></code>. (Discussed in Rosetta1. TODO LINK) So I tend to write instead just `List.append`. But when working with Lists as abstract monadic values, in OCaml, you need to use `++` instead of `List.append`. OCaml will act like it doesn't know that abstract monadic Lists are really `list`s. `test` takes a predicate of plain (non-monadic) lists, and if the monadic list that is its second argument satisfies it, returns that list unchanged, else returns `mzero` (the abstract list version of `[]`). `guard` takes a boolean argument, and if it's true returns `[()]` (as an abstract list) else returns `mzero`. These correspond to the Haskell operations of the same name.
Here is an example of using the List monad.
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 opaque monadic 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]
Haskell has this convenient "do-notation" for working with monads. You could write the above example like this in Haskell:
- let { xx = pure 1 ++ pure 2 ++ pure 3; yy = (if (\xs -> 3 `elem` xs) xx then xx else mzero) >>= \x -> return (x+1) } in yy
+ let { xx = pure 1 ++ pure 2 ++ pure 3;
+ yy = (if (\xs -> 3 `elem` xs) xx then xx else mzero) >>= \x -> return (x+1) } in yy
(With the List monad, Haskell doesn't require or even have any `run` operation; and what we have as `test` they have to write longhand.) But you could also write it like this in Haskell:
- do { let { xx = pure 1 ++ pure 2 ++ pure 3}; x <- if (\xs -> 3 `elem` xs) xx then xx else mzero; return (x+1) }
+ do { let { xx = pure 1 ++ pure 2 ++ pure 3};
+ x <- if (\xs -> 3 `elem` xs) xx then xx else mzero;
+ return (x+1) }
The key point here is that `zz >>= \x -> blah` can be written in Haskell as `do { x <- zz; blah }`. In this case it doesn't help much, but often it makes things much shorter and easier to read. OCaml doesn't have this natively, though I've seen third-party extensions that offer some analogue of it.