Monads semantics are mostly what is created by bind. And bind is an operation that describes how to sequence expressions.
What you may be misunderstanding is that "sequencing expressions" does not mean "execute one expression after the other". It means, take a sequence of expressions and give it some meaning. Yes, that meaning can be "execute one after the other", or "run everything at the same time", or any other ordering. The meaning can ignore any ordering and only care about some context, or apply some order over the result in an ordered structure, or almost anything else.
Nah, it's not really "one of those famous misconceptions".
The crucial detail is that TardisT must wrap a MonadFix, which is used for cyclical data structures. It effectively works not by making time go "backwards", but by making time loop around. It still creates a sequencing relationship.
Let's define an operator `|> = (flip $)`, which has a type signature `a -> (a -> b) -> b`, which, by your reasoning, should force sequencing too. Except it doesn't: Laziness is a bitch to work with, and `a |> f |> g` evaluates to `g(f(a))`, and g is evaluated first, which then evaluates f(a) on demand. If you consider `1 |> (+1) |> const 4`, this will evaluate to 4 without ever performing the addition.
Instead, let's compare this to the monadic equivalent. `(return 1) >>= return . (+ 1) >>= return . (const 4)`. The sequence that's being forced here isn't that (+ 1) is evaluated, it's that the `return` in `return 1` is evaluated (producing a 1) before `return . (+ 1)` is ever touched, and that _that_ return is evaluated (presumably producing an unevaluated thunk for (1 + 1)) before `return . (const 4)` is touched.
In IO world, this corresponds to guaranteeing that the IO operations happen in sequence irrespective of the order in which the pure computations they wrap are evaluated in.
> the `return` in `return 1` is evaluated (producing a 1) before `return . (+ 1)` is ever touched, and that _that_ return is evaluated (presumably producing an unevaluated thunk for (1 + 1)) before `return . (const 4)` is touched.
That's not quite right either. The former returns need never be evaluated.
Right — I should've said "that's the mechanism through which the implementation of `>>=` can force sequencing". `>>=` for Identity doesn't, most of the other common ones do, in some sense or another.
Right! `>>=` can force sequencing. It doesn't for Identity, Writer.Lazy or State.Lazy, but it can. OK, but also Arrow and Monoid can enforce a (different sort of) sequencing relationship.
Neither does monad force a sequencing relationship nor is it the only thing than can force a sequencing relationship so I can only conclude that "What a Monad does is to force sequencing by creating a data dependency" is indeed one of those misconceptions!
Indeed. But bad_user made a claim about monads in general
("What a Monad does is to force sequencing by creating a data dependency.") so all I need to do to refute it is give an example of a particular monad where the claim doesn't hold.
Monads force a denotation of sequencing. Of course you can write a language implementation where the sequencing of operation does not represent the sequencing of denotation (just as you can write a "compiler" that compiles all programs to Hello World), but, well, that's on you.
What about the Identity monad? Does that "force sequencing"? What "sequencing relationship" does it create?
If you are convinced that the Identity monad does "force sequencing" then you are also convinced that lazy evaluation "forces sequencing" (because the Identity monad is just lazy evaluation). That would be a fairly controversion conviction. If you are not convinced that the Identity monad "forces sequencing" then can you explain in more detail the meaning of your claim "What a Monad does is to force sequencing by creating a data dependency.".
It's in the signature. `b` has a causal dependency on `a` because `a` is on the left hand side of the arrow and `b` is on the right hand side of the arrow. That's it. Functional programming 101. There's no way around this.
The operational semantics and details of thunks are not relevant here. Tricks with `undefined` are not relevant here. This is just the meaning of the arrow type.
Because the values have extra "stuff" surrounding them. That's why it's `m a` and not just `a`: the `m` holds the invisible context that enriches the `a`.
Although your example is exactly what's happening in the identity monad, because there is no extra stuff.
Monads have been called "executable semicolons", because you can define a function to be executed each time the program passes from one statement to the next.
Tardis and the ReverseState monad are more examples of people being funny and clever by creating misleading names and mental-models instead of making libraries easy to understand.
There's no "time loop" in a cyclical data structure. There's just a data loop. Moving backward through a circular buffer, or doing arithmetic mod N, isn't "time travel"
But TardisT is sequenced in the monadic value. It is not sequenced in its inner backwards-traveling state, but that is not part of the monadic structure.
Have you used TardisT? In order to use the backwards traveling state, you need to bind the state syntactically before you use it, just as you have to do with the forwards traveling state.
For example, a typical setup for TardisT is fixing up jump offsets for an assembler. To write this, you do something like
assembler (Label l) = do
fixup <- getFuture
(curOps, offset) <- getPast
modifyBackwards (M.insert l offset)
let ops = curOps ++ [ Jump (M.lookup l fixup) ]
sendFuture (ops, offset + 1)
assembler ... = ...
Note that both the forwards and backwards traveling state needed to be bound before they were used. There is an inherent 'forwards-traveling' sequencing due to the monadic structure.
If tardist were not monadically sequenced, you ought to be able to do
assembler (Label l) = do
(curOps, offset) <- getPast
let ops = curOps ++ [ Jump (M.lookup l fixup) ]
sendFuture (ops, offset + 1)
fixup <- getFuture
modifyBackwards (M.insert l offset)
In this sense, the forwards traveling state is privileged (and indeed if you write anything sufficiently complicated, you'll note that you'll need to add a lot of lazy pattern matches on the backwards traveling state, but not the forwards traveling one, again indicating a notion of sequencing, despite what it may seem).
Does it really? Maybe this is another one of those famous misconceptions!
https://hackage.haskell.org/package/tardis-0.4.1.0/docs/Cont...