*First posted Thursday 2 April; updated Sunday 5 April.*
+[[!toc]]
+
## 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 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:
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 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.
+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. (For comparison of the type declaration syntax and capitalization rules for Haskell and OCaml, see our [[Rosetta2 page|/rosetta2]].)
In the Juli8 libraries we're supplying for OCaml, you instead express function composition with `%`.
-TODO Capitalization / type declaration syntaxes comparison
-
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.
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.
+**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:
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.
-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.
+**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.
* `#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`.
-
+<a id=abstraction></a>
## 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.
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 [[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.
+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 on our [[Rosetta1 page|/rosetta1#as-patterns]].) 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.