Proposal: Applicative => Monad: Call for consensus

[wren ng thornton]

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