From: jim Date: Mon, 6 Apr 2015 21:49:20 +0000 (-0400) Subject: revsions X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=cd0b6c43520edfc5da22117846b7ac108ed8de1e;ds=sidebyside revsions --- diff --git a/topics/_week9_state_monad_tutorial.mdwn b/topics/_week9_state_monad_tutorial.mdwn index b15ac297..e586ae06 100644 --- a/topics/_week9_state_monad_tutorial.mdwn +++ b/topics/_week9_state_monad_tutorial.mdwn @@ -1,118 +1,118 @@ -This walks through most of [A State Monad Tutorial](http://strabismicgobbledygook.wordpress.com/2010/03/06/a-state-monad-tutorial/), which is addressed to a Haskell-using audience. But we convert it to OCaml. See our page on -[[Translating between OCaml Scheme and Haskell]]. +This walks through most of [A State Monad Tutorial](http://strabismicgobbledygook.wordpress.com/2010/03/06/a-state-monad-tutorial/), which is addressed to a Haskell-using audience. But we convert it to OCaml. See our page on [[comparing OCaml and Haskell|/rosetta2]]. -Some of what we do here will make use of our [[monad library]] for OCaml. +Some of what we do here will make use of our monad library for OCaml. See: -As we discussed in [[week9]], a State monad is implemented with the type: +* [[Installing and Using the Juli8 Libraries|/juli8]] +* [[Using the OCaml Monad library|/topics/week9_using_the_monad_library]] - store -> ('a * store) +As we discussed in [[week9]] TODO LINK, a State monad is implemented with the type: + + store -> ('a * store) It's common practice to encapsulate this in some way, so that the interpreter knows the difference between arbitrary functions from a `blah` to a pair of something and a `blah` and the values that you've specially designated as being State monadic values. The most lightweight way encapsulate it would be just to add a data constructor to the type. In the same way that the `'a option` type has the `None` and `Some` data constructors, we give our `'a state` type a `State` data constructor: - (* we assume that the store type has already been declared *) - type 'a state = State of (store -> ('a * store)) + (* we assume that the store type has already been declared *) + type 'a state = State of (store -> ('a * store)) -Then a function expecting an `'a store` will look for a value with the structure `State ...` rather than just one with the structure `...`. +Then a function expecting an `'a state` will look for a value with the structure `State ...` rather than just one with the structure `...`. To take a `State (s -> (a,s))` and get at the `s -> (a,s)` it wraps, you use the same techniques you use to take an `Some int` and get at the `int` it wraps: - let u = State (fun s -> (1, s)) - in let State unwrapped_state = u - in ... + let xx = State (fun s -> (1, s)) in + let State unwrapped_xx = xx in + ... or: - let u = State (fun s -> (1, s)) - in match u with - | State unwrapped_state -> ... - -There are two heavierweight ways to encapsulate the type of the State monad. One is used by our [[monad library]]---the type is hidden from the outside user, and only gets exposed by the `run` function. But the result of `run u` is not itself recognized as a monadic value any longer. You can't replace `u` in: + let xx = State (fun s -> (1, s)) in + match xx with + | State unwrapped_xx -> ... + +There are two heavierweight ways to encapsulate the type of the State monad. One is used by our [[monad library]] TODO LINK --- the type is hidden from the outside user, and only gets exposed by the `run` function. But the result of `run xx` is not itself recognized as a monadic value any longer. You can't replace `xx` in: - Monad.(u >>= ...) + SomeMonad.(xx >>= ...) -with `run u`. So you should only apply `run` when you've finished building up a monadic value. (That's why it's called `run`.) +with `run xx`. So you should only apply `run` when you've finished building up a monadic value. (That's why it's called `run`.) Of course you can do this: - let u = Monad.(...) - in let intermediate_result = Monad.run u 0 - in let v = Monad.(u >>= ...) - in let final_result = Monad.run v 0 - in ... + let xx = SomeMonad.(...) in + let intermediate_result = SomeMonad.run xx 0 in + let yy = SomeMonad.(xx >>= ...) in + let final_result = SomeMonad.run yy 0 in + ... -The other heavyweight way to encapsulate the type of a monad is to use records. See [here](/translating_between_OCaml_Scheme_and_Haskell) and [here](/coroutines_and_aborts/) for some introduction to these. We don't use this design in our OCaml monad library, but the Haskell monad libraries do, and it would be good for you to get acquainted with it so that you can see how to ignore it when you come across it in Haskell-based literature. (Or you might want to learn Haskell, who knows?) +The other heavyweight way to encapsulate the type of a monad is to use records. See [here](/translating_between_OCaml_Scheme_and_Haskell) and [here](/coroutines_and_aborts/) for some introduction to these. TODO LINKS We don't use this design in our OCaml monad library, but the Haskell monad libraries do, and it would be good for you to get acquainted with it so that you can see how to ignore it when you come across it in Haskell-based literature. (Or you might want to learn Haskell, who knows?) -We'll illustrate this technique in OCaml code, for uniformity. See the [translation page](/translating_between_OCaml_Scheme_and_Haskell) about how this looks in Haskell. +We'll briefly illustrate this technique in OCaml code, for uniformity. See the [translation page](/translating_between_OCaml_Scheme_and_Haskell) TODO LINKS about how this looks in Haskell. To use the record technique, instead of saying; - type 'a state = State of (store -> ('a * store)) + type 'a state = State of (store -> ('a * store)) you'd say: - type 'a state = { state : store -> ('a * store) } + type 'a state = { state : store -> ('a * store) } and instead of saying: - let u = State (fun s -> (1, s)) - in let State unwrapped_state = u - in ... + let xx = State (fun s -> (1, s)) in + let State unwrapped_xx = xx in + ... you'd say: - let u = { state = fun s -> (1, s) } - in let unwrapped_state = u.state - in ... + let xx = { state = fun s -> (1, s) } in + let unwrapped_xx = xx.state in + ... -That's basically it. As with the other two techniques, the type of `u` is not the same as `store -> ('a * store)`, but the relevant code will know how to convert between them. +That's basically it. As with the other two techniques, the type of `xx` is not the same as `store -> ('a * store)`, but the relevant code will know how to convert between them. The main benefit of these techniques is that it gives you better type-checking: it makes sure that you're only using your monadic values in the hygenic ways you're supposed to. Perhaps you don't care about that. Well, then, if you want to write all your own monadic code, you can proceed as you like. If you ever want to use other people's code, though, or read papers or web posts about monads, you will encounter one or more of these techniques, and so you need to get comfortable enough with them not to let them confuse you. OK, back to our walk-through of "A State Monad Tutorial". What shall we use for a store? Instead of a plain `int`, let's suppose our store is a structure of two values: a running total, and a count of how many times the store has been modified. We'll implement this with a record. Hence: - type store' = { total : int; modifications: int };; + type store' = { total : int; modifications: int };; -State monads employing this store will then have *three* salient values at any point in the computation: the `total` and `modifications` field in the store, and also the `'a` value that is then wrapped in the monadic box. +State monads employing this store will then have *three* salient values at any point in the computation: the `total` and `modifications` field in the store, and also the `'a` payload that is currently wrapped in the monadic box. -Here's a monadic box that encodes the operation of incrementing the store's `total` and wrapping the value that was the former `total`: +Here's a monadic value that encodes the operation of incrementing the store's `total` and wrapping the value that was the former `total`: - let increment_store : store' -> (int * store') = - fun s -> - let value = s.total - in let s' = { total = succ s.total; modifications = succ s.modifications } - in (value, s') + let increment_store : store' -> (int * store') = fun s -> + let value = s.total in + let s' = { total = succ s.total; modifications = succ s.modifications } in + (value, s') If we wanted to work with one of the encapsulation techniques described above, we'd have to proceed a bit differently. Here is how to do it with the first, lightweight technique: - let increment_store' : 'a state = - State (fun s -> - let value = s.total - in let s' = { total = succ s.total; modifications = succ s.modifications } - in (value, s')) + let increment_store' : 'a state = State (fun s -> + let value = s.total in + let s' = { total = succ s.total; modifications = succ s.modifications } in + (value, s')) -Here is how you'd have to do it using our OCaml monad library: +Here is how you'd have to do it using our OCaml/Juli8 monad library: - # #use "path/to/monads.ml";; - # module S = State_monad(struct type store = store' end);; - # let increment_store'' : ('x,'a) S.m = - S.(get >>= fun cur -> - let value = cur.total - in let s' = { total = succ cur.total; modifications = succ cur.modifications } - in put s' >> unit value);; + # (* have Juli8 loaded, as explained elsewhere *) + # module S = Monad.State(struct type store = store' end);; + # let increment_store'' : 'a S.t = + S.(get >>= fun cur -> + let value = cur.total + in let s' = { total = succ cur.total; modifications = succ cur.modifications } + in put s' >> mid value);; Let's try it out: - # let s0 = { total = 42; modifications = 3 };; - # increment_store s0;; - - : int * store' = (42, {total = 43; modifications = 4}) + # let s0 = { total = 42; modifications = 3 };; + # increment_store s0;; + - : int * store' = (42, {total = 43; modifications = 4}) -Or if you used the OCaml monad library: +Or if you used the OCaml/Juli8 monad library: - # S.(run(increment_store'')) s0;; - - : int * S.store = (42, {total = 43; modifications = 4}) + # S.(run increment_store'') s0;; + - : int * S.store = (42, {total = 43; modifications = 4}) Great! @@ -120,76 +120,77 @@ Can you write a monadic value that instead of incrementing each of the `total` a What about a value that increments each of `total` and `modifications` twice? Well, you could custom-write that, as with the previous question. But we already have the tools to express it easily, using our existing `increment_store` value: - increment_store >>= fun value -> increment_store >> unit value + increment_store >>= fun value -> increment_store >> unit value That ensures that the value we get at the end is the value returned by the first application of `increment_store`, that is, the contents of the `total` field in the store before we started modifying the store at all. You should start to see here how chaining monadic values together gives us a kind of programming language. Of course, it's a cumbersome programming language. It'd be much easier to write, directly in OCaml: - let value = s0.total - in (value, { total = s0.total + 2; modifications = s0.modifications + 2};; + let value = s0.total + in (value, { total = s0.total + 2; modifications = s0.modifications + 2};; or, using pattern-matching on the record (you don't have to specify every field in the record): - let { total = value; _ } = s0 - in (value, { total = s0.total + 2; modifications = s0.modifications + 2};; + let { total = value; _ } = s0 + in (value, { total = s0.total + 2; modifications = s0.modifications + 2};; But **the point of learning how to do this monadically** is that (1) monads show us how to embed more sophisticated programming techniques, such as imperative state and continuations, into frameworks that don't natively possess them (such as the set-theoretic metalanguage of Groenendijk, Stokhof and Veltman's paper); (2) becoming familiar with monads will enable you to see patterns you'd otherwise miss, and implement some seemingly complex computations using the same simple patterns (same-fringe is an example); and finally, of course (3) monads are delicious. Keep in mind that the final result of a bind chain doesn't have to be the same type as the starting value: - increment_store >>= fun value -> increment_store >> unit (string_of_int value) + increment_store >>= fun value -> increment_store >> unit (string_of_int value) Or: - unit 1 >> unit "blah" + unit 1 >> unit "blah" The store keeps the same type throughout the computation, but the type of the wrapped value can change. What are the special-purpose operations that the `State_monad` module defines for us? -* `get` is a monadic value that passes through the existing store unchanged, and also wraps that same store as its boxed value. You use it like this: - - ... >>= fun _ -> get >>= fun cur -> ... here we can use cur ... +* `get` is a monadic value that passes through the existing store unchanged, and also wraps that same store as its boxed payload. You use it like this: - As we've said, that's equivalent to: + ... >>= fun _ -> get >>= fun cur -> ... here we can use cur ... - ... >> get >>= fun cur -> ... + As we've said, that's equivalent to: - You can also get the current store at the start of the computation: + ... >> get >>= fun cur -> ... - get >> = fun cur -> ... + You can also get the current store at the start of the computation: -* `gets selector` is like `get`, but it additionally applies the `selector` function to the store before depositing it in the box. If your store is structured, you can use this to only extract a piece of the structure: + get >> = fun cur -> ... - ... >> gets (fun cur -> cur.total) >>= fun total -> ... +* `gets selector` is like `get`, but it additionally applies the `selector` function to the store before depositing it in the box. If your store is structured, you can use this to only extract a piece of the structure: - For more complex structured stores, consider using the `Ref_monad` version of the State monad in the OCaml library. + ... >> gets (fun cur -> cur.total) >>= fun total -> ... -* `put new_store` replaces the existing store with `new_store`. Use it like this: + For more complex structured stores, consider using the `Ref_monad` version of the State monad in the OCaml library. - ... >> put new_store >> fun () -> ... +* `put new_store` replaces the existing store with `new_store`. Use it like this: - As that code snippet suggests, the boxed value after the application of `puts new_store` is just `()`. If you want to preserve the existing boxed value but replace the store, do this: + ... >> put new_store >> fun () -> ... - ... >>= fun value -> put new_store >> unit value >>= ... + As that code snippet suggests, the boxed payload after the application of `modify new_store` is just `()`. If you want to preserve the existing payload but replace the store, do this: -* Finally, `puts modifier` applies `modifier` to whatever the existing store is, and substitutes that as the new store. As with `put`, the boxed value afterwards is `()`. + ... >>= fun value -> put new_store >> unit value >>= ... - Haskell calls this operation `modify`. We've called it `puts` because it seems to fit naturally with the convention of `get` vs `gets`. (See also `ask` vs `asks` in `Reader_monad`, which are also the names used in Haskell.) +* Finally, `modify modifier` applies `modifier` to whatever the existing store is, and substitutes that as the new store. As with `put`, the boxed payload afterwards is `()`. + Here's an example from "A State Monad Tutorial": - increment_store >> get >>= fun cur -> - State (fun s -> ((), { total = s.total / 2; modifications = succ s.modifications })) >> - increment_store >> unit cur.total + increment_store >> get >>= fun cur -> + State (fun s -> ((), { total = s.total / 2; modifications = succ s.modifications })) >> + increment_store >> unit cur.total Or, as you'd have to write it using our OCaml monad library: - increment_store'' >> get >>= fun cur -> - put { total = cur.total / 2; modifications = succ cur.modifications } >> - increment_store'' >> unit cur.total + increment_store'' >> get >>= fun cur -> + put { total = cur.total / 2; modifications = succ cur.modifications } >> + increment_store'' >> unit cur.total The last topic covered in "A State Monad Tutorial" is the use of do-notation to work with monads in Haskell. We discuss that on our [translation page](/translating_between_OCaml_Scheme_and_Haskell).