Tue Sep 21 19:17:15 UTC 2021

```> As noted a few times in this thread List takes multiple paths.  The
> "non-determinism" (something that not always explained well, since
> taking all paths is still rather deterministic) extends the simple
> pipeline model.

In principle you could make the different paths race against each other
and return the one that finishes (first). That would be proper non-
determinism.

List, Sequence, Tree and such are set-like monads, which I would put
into the non-determinism corner. Years ago I was experimenting with
decision-making and sequence alignment in particular. The hypothesis
was that if you have a functional program that makes a decision on
exact data, then lifting the program through a suitable monad M will
give you a decision procedure for M-fuzzy inputs. For example, we
managed to implement string matching for the ListT monad transformer,
so you can match fuzzy strings against fuzzy strings. Here a full-text
index (e.g. suffix tree) is itself a special kind of fuzzy string
takes you simultaneously to every position in the indexed text.

Set-like monads do not fit the pipeline model well, it seems. By the
way, I struggle with the pipeline metaphor. If a monad is a pipeline,
what are the connectors? Is (m a) a piece of pipe and (>>) a connector?
Or is (a -> m b) a piece of pipe and (>=>) a connector?

In my Haskell exposition for mathematicians I chose the monad of formal
linear combinations for introduction of monads. In this monad M, (M b)
is a vector over basis b, (b1 -> M b2) describes a linear map (matrix)
w.r.t. bases b1 and b2, (<=<) is matrix multiplication and (=<<) is
matrix-vector multiplication. So if you like matrices, mentally replace
(a -> m b) by "linear map" and (m a) by "vector".

Olaf

```