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 parametrized by the list monad. Decomposing it into head and tail 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