# Proposal: Applicative => Monad: Call for consensus

wren ng thornton wren at freegeek.org
Thu Jan 20 07:12:48 CET 2011

On 1/19/11 1:24 PM, Tyson Whitehead wrote:
> On January 17, 2011 16:20:22 Conor McBride wrote:
>> To achieve such a thing, one would need to ensure a slightly more
>> deliberate separation of "value" and "computation" in the presentation
>> of types. In Haskell, we use, e.g., [Int], for
>>
>>     * pure computations of lists of integers
>>     * nondeterministic computations of integers
>>
>> and we spend syntax (do-notation, lifting operators) to distinguish the
>> two modes of usage. If every type was clearly decomposable into its
>> computation and value components, the above possibilities would be
>> distinct (but isomorphic) and we could spend less syntax on plumbing
>> in programs.
>
> I'm pretty sure I know what "pure computations of lists of integers" is, but
> I'm not so sure about "nondeterministic computations of integers".

Consider I have two black boxes, each with a shiny button on them. The
first box is a deterministic machine, and when I press the button it
gives me a sequence of integers.

The second box is a nondeterministic machine, and when I press the
button it gives me a superposition of many versions of one integer. For
deterministic purposes I can just select one of those versions at
random. Or, if I have another nondeterministic machine, I can just feed
it the whole superposition as the new machine's starting (multi)state.

The difference is just that for the first box I like to think of the
result as many numbers, like a list of phone numbers for all my friends;
whereas I like to think of the second box as only giving me one number,
but it's a bit fuzzy about which number that is.

In a lot of ways lists are actually a horrible model for nondeterminism.
Because lists have an order, and because of how that order is preserved
by the list monad, one of the major pieces of information lists work at
preserving is the history of choices that lead to each particular
possibility. But in practice we usually don't care about that history.
We often just want to know which possibilities are viable, in which case
a set or skiplist is a more helpful representation (or weighted variants
if we care about multiplicity). Or we care about possibilities in order
of how "good" they are, in which case we really want a priority queue or
similar structure.

Any monad which behaves sufficiently like a container (lists, sets,
multisets, priority queues,...) can serve as a model for nondeterminism.
They just vary in what sorts of information they preserve about the
versions of the value they contain.

--
Live well,
~wren