Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Intuitively, I think that what the fancy math vocabulary is saying is that:</p> <h1>Monoid</h1> <p>A <strong>monoid</strong> is a set of objects, and a method of combining them. Well known monoids are:</p> <ul> <li>numbers you can add</li> <li>lists you can concatenate</li> <li>sets you can union</li> </ul> <p>There are more complex examples also.</p> <p>Further, <em>every</em> monoid has an <strong>identity</strong>, which is that "no-op" element that has no effect when you combine it with something else:</p> <ul> <li>0 + 7 <strong>==</strong> 7 + 0 <strong>==</strong> 7</li> <li>[] ++ [1,2,3] <strong>==</strong> [1,2,3] ++ [] <strong>==</strong> [1,2,3]</li> <li>{} <em>union</em> {apple} <strong>==</strong> {apple} <em>union</em> {} <strong>==</strong> {apple}</li> </ul> <p>Finally, a monoid must be <strong>associative</strong>. (you can reduce a long string of combinations anyway you want, as long as you don't change the left-to-right-order of objects) Addition is OK ((5+3)+1 == 5+(3+1)), but subtraction isn't ((5-3)-1 != 5-(3-1)).</p> <h1>Monad</h1> <p>Now, let's consider a special kind of set and a special way of combining objects.</p> <h2>Objects</h2> <p>Suppose your set contains objects of a special kind: <strong>functions</strong>. And these functions have an interesting signature: They don't carry numbers to numbers or strings to strings. Instead, each function carries a number to a list of numbers in a two-step process.</p> <ol> <li>Compute 0 or more results</li> <li>Combine those results unto a single answer somehow.</li> </ol> <p>Examples:</p> <ul> <li>1 -> [1] (just wrap the input)</li> <li>1 -> [] (discard the input, wrap the nothingness in a list)</li> <li>1 -> [2] (add 1 to the input, and wrap the result) </li> <li>3 -> [4, 6] (add 1 to input, and multiply input by 2, and wrap the <em>multiple results</em>)</li> </ul> <h2>Combining Objects</h2> <p>Also, our way of combining functions is special. A simple way to combine function is <em>composition</em>: Let's take our examples above, and compose each function with itself:</p> <ul> <li>1 -> [1] -> [[1]] (wrap the input, twice)</li> <li>1 -> [] -> [] (discard the input, wrap the nothingness in a list, twice)</li> <li>1 -> [2] -> [ UH-OH! ] (we can't "add 1" to a list!")</li> <li>3 -> [4, 6] -> [ UH-OH! ] (we can't add 1 a list!)</li> </ul> <p>Without getting too much into type theory, the point is that you can combine two integers to get an integer, but you can't always compose two functions and get a function of the same type. (Functions with type <em>a -> a</em> will compose, but <em>a-> [a]</em> won't.)</p> <p>So, let's define a different way of combining functions. When we combine two of these functions, we don't want to "double-wrap" the results. </p> <p>Here is what we do. When we want to combine two functions F and G, we follow this process (called <em>binding</em>):</p> <ol> <li>Compute the "results" from F but don't combine them.</li> <li>Compute the results from applying G to each of F's results separately, yielding a collection of collection of results.</li> <li>Flatten the 2-level collection and combine all the results.</li> </ol> <p>Back to our examples, let's combine (bind) a function with itself using this new way of "binding" functions:</p> <ul> <li>1 -> [1] -> [1] (wrap the input, twice)</li> <li>1 -> [] -> [] (discard the input, wrap the nothingness in a list, twice)</li> <li>1 -> [2] -> [3] (add 1, then add 1 again, and wrap the result.)</li> <li>3 -> [4,6] -> [5,8,7,12] (add 1 to input, and also multiply input by 2, keeping both results, then do it all again to both results, and then wrap the final results in a list.)</li> </ul> <p>This more sophisticated way of combining functions <em>is</em> associative (following from how function composition is associative when you aren't doing the fancy wrapping stuff).</p> <p>Tying it all together, </p> <ul> <li>a monad is a structure that defines a way to combine (the results of) functions, </li> <li>analogously to how a monoid is a structure that defines a way to combine objects, </li> <li>where the method of combination is associative,</li> <li>and where there is a special 'No-op' that can be combined with any <em>something</em> to result in <em>something</em> unchanged.</li> </ul> <h1>Notes</h1> <p>There are lots of ways to "wrap" results. You can make a list, or a set, or discard all but the first result while noting if there are no results, attach a sidecar of state, print a log message, etc, etc.</p> <p>I've played a bit loose with the definitions in hopes of getting the essential idea across intuitively.</p> <p>I've simplified things a bit by insisting that our monad operates on functions of type <em>a -> [a]</em>. In fact, monads work on functions of type <em>a -> m b</em>, but the generalization is kind of a technical detail that isn't the main insight.</p>
    singulars
    1. This table or related slice is empty.
    1. POA monad is just a monoid in the category of endofunctors, what's the probleⅿ?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USb4hand
    1. USmisterbee
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThis is a nice explanation of how every monad constitutes a _category_ (the [Kleisli category](http://en.wikipedia.org/wiki/Kleisli_category) is what you're demonstrating--there is also the Eilenberg-Moore category). But due to the fact that you can't compose _any_ two Kleisli arrows `a -> [b]` and `c -> [d]` (you can only do this if `b` = `c`), this doesn't quite describe a monoid. It's actually the flattening operation you described, rather than function composition, which is the "monoid operator".
      singulars
      1. PO
      1. USTom Crockett
    2. COGranted, if you limited a monad to only one type, i.e. if you only allowed Kleisli arrows of the form `a -> [a]`, this would be a monoid (because you'd be reducing the Kleisli category to a single object, and any category of only one object is by definition a monoid!), but it would not capture the full generality of the monad.
      singulars
      1. PO
      1. USTom Crockett
    3. COOn the last note, it helps to remember, that a -> [a] is just a -> [] a. ([] is just type constructor too.) And so it can not only be seen as a -> m b, but [] is indeed an instance of the Monad class.
      singulars
      1. PO
      1. USEvi1M4chine
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload