C9 Lectures: Greg Meredith - Monadic Design Patterns for the Web 4 of 4

The Discussion

• 

  Some background information for one of the slides: Difference between List and Set variance?

• 

  Thanks Greg & Charles. Very much enjoyed this latest instalment. Looking forward to the next one and/or the book!

• 

  Hey this was great.  What would this look like in F#?  Thanks.

• 

  @AceHack:

  F# has a DSL for monads called Computation Expressions so monads 'look' different in F#. Also, I think that once you have a monad implementation, the DSL makes it easier to use the implementation in your code.

  So F# provides some extra language support for monads.

  However, unlike Scala, F# does not have higher-kinded types so you cannot compose two monad implementations together (as easily).

  I struggled with monads at first but then I realized that monads are really about function composition. Here is blog post that emphasizes this aspect of monads that may help with the understanding:

  http://fwaris.wordpress.com/2011/07/30/understanding-monads/

• 

  Thank you Greg! Thank you Charles!

  This one was really giving me a blast (and still is). Today I got my copy of D.E.Knuth's "Surreal Numbers", which is an excellent little intro to Conway numbers back from 1974, and I would like to recommend it here. I devoured it in one go and will read it again as soon as possible, then equipped with pencil and paper. The other book, Conway's "On Numbers and Games", appearing in the slides, I have ordered already... and Greg's book is on the list

  Now, having settled the praise, here's something that sparked off quite towards the end of this installment. It's about abstracting over the container representation for 'left' and 'right'. Hmm, possibly there's a good thing even in Scala's oddity of non-variant (immutable!) Sets (see ShiNoNoir's link above).

  Ok, I got two things, the second about transfinite ordinals. I know, that sounds quite scary/impressive - but it ain't really so (much). I have put together a postscript below (admittedly long for a post, but still...) which I hope establishes the relevant point while presuming virtually nothing. Please also leave your comment on that particular attempt alone, if you have some.

  •  Isn't the "second hole", i.e. the abstraction over the containers just including the "first hole" that you poked? That is to say: once we're free to provide any container representation we like, can't we get rid of the A type parameter in GenConWayGame[M[_],A] and the Either[A, ...] in left and right and just "push" that into the M[_]?
  • The M[_] that we pass in to GenConWayGame is free to choose any (internal) representation of collections it prefers, as long as it provides unit and bind (and adheres to some "Set contract", e.g. order-insensitive, duplicate-free etc), right? Well, if so why not represent Sets as the "recipe" how to create them, i.e. as code. I mean code as data, i.e. we're not going to execute that code but rather want to manipulate it. So ω would just be some (finite!) representation of code that, if executed, would give the empty set for right and for left enumerate the naturals, ad infinitum. Adding 1 to that, for example, would give code that, if executed, would give the empty set for right and for left enumerate {ω,2,3,4,....}. And, even better, we could simply return the equivalent ({ω}, {}). Not so hard to imagine how to represent that, is it? You see, it's calculating (=reasoning about) it, not actually writing it out. We'd like to defer as long as we can - at best forever

   ____ 

  p.s., "What's that Conway ω, by the way?" (simplifying quite a bit - as Greg mentioned, "there's a lot of devil (detail) in there"):

  1. To start, let's define a binary relation to compare Conway games, "LTE" ("Less-Than-or-Equal"): x = (X_L, X_R) is LTE  y = (Y_L, Y_R) :IFF every x_L in X_L is LTE y AND x is LTE every y_R in Y_R. Again, this appears crazily circular but look, since it's composed of universal statements ("for every foo in bar: ...") and we're starting from empty sets, it's well-founded (note that "for every foo in the empty set: ..." is always true, regardless of what the "..." say).
  2. Not every Conway game is also a Conway number, i.e. there exist games g and h such that  neither g LTE h nor h LTE g is the case. Odd as this may seem, it rather shows that the data structure is even more powerful than to "just represent numbers". Anyways, let's consider Conway numbers only; these are the games x = (X_L, X_R) where we have: every x_L in X_L is LTE than any (="every") x_R in X_R.  Again, this looks crazily circular but... - we're getting used to it, aren't we?
  3. 1) and 2) (not obviously) imply that every "intuitive" number has a many structurally distinct Conway numbers (or better "numerals") that represent it. However, all those representations of one "intuitive" number have the common property to "behave" identically w.r.t. comparison, addition etc., i.e. they are "practically the same". Even better, from all the representations that are equivalent in the said sense we can easily choose (=construct) a single canonical one to stand for them all - and thus forget about the problem altogether. We'll simply use the canonical one to denote "or any of its equivalents". Oh, and btw, the set of equivalents (the "equivalence class") for any number is infinite...
  4. Uhm... actually there's a catch in 3), in particular the "we can easily choose (=construct)". In fact, that's not entirely true when it comes to the interesting bits. Now what are these? Well,  let's start by sticking with 3) for awhile and have a look at the non-negative integers only. We have 0 = ({},{}), then 1 = ({0}, {}), then 2 = ({1}, {}), then 3 = ({2}, {})... you get it: left is the set containing just the (set containing the) predecessor and right is always empty. These were the canonical representations as proposed in 3), but e.g. the "intuitive" number 2 could also be represented by ({0,1}, {}), that means ({0,1}, {}) "is practically the same as" ({1}, {}). Likewise, the "intuitive" number 3 could be as well represented by ({0,1,2}, {}) or ({0,2}, {}) or ({1,2}, {}). The "trick", of course, is that the "behavior" solely depends on the maximal element (check yourself using the definition of LTE). Hence the choice of the canonical representative is straight-forward: simply use the singleton set with exactly that maximal element for left and the empty set for right. This covers all of the non-negative integers nicely. Now for the fun part
  5. Who said the left and/or right collections of a Conway number (or game, for that matter) need to be finite? Well, nobody, of course. But that means there is this critter: ({0,1,2,3,4,...}, {}), i.e. empty right and in left all the non-negative integers from 4). This actually is a Conway number according to 2), yet any non-negative integer from 4) is LTE it. Check it yourself, you'll see it's trivial. This critter is commonly denoted by ω and it was created on the day after infinitely many days (when the integers [and some more, like the rationals] were created), aka day aleph (1). Anyhow, here come the interesting bits: how to actually represent ω in a program? Obviously we cannot replay the "trick" from 3), as there is no maximal element (although we could agree on a canonical representation that contains just the singleton sets from 4) - but that doesn't help, it's still infinite). However, it's not at all hard to envision ω - or is it?! C'mon, all we're talking about is the pair of a) all the non-negative integers and b) the empty set, that ain't really hard. But wait, what is just that? It's an English sentence, consisting of... uhm... a number of characters - but definitely finite! And it characterizes this infinite critter ω . So...