> What is the relationship between fold + cons (::) and monadic bind? What is the natural transformation from fold to functorial map? Is there a sensical dual?

Whew, working backwards.

Fold is like your swiss army knife for working with entire lists at once; you just need to tell it what to do when it sees a node (Cons) or a terminator (Nil). If, for example, you instruct fold to apply a function to each element of the list but leave the linked structure intact, you've implemented map! And for lists, the fuctorial map, or fmap, is exactly map.

The monadic bind in the List monad is a way of expressing Nondeterminism. Let's say I have two functions...

  b = makeSomeBsFromAnA(a); c = makeSomeCsFromAB(b);

In the context of the List Monad, you would evaluate the first statement to produce a list of Bs. Then, for each B, you would generate a list of Cs, and then concatenate all of those lists into a big list. That's why bind is sometimes referred to as flatmap in the List Monad - take each element generate in the last list computation to generate a bunch of new lists, and then flatten them (smoosh them together; concatenate them). flatmap could of course be implemented using fold and cons.

The point here is that, since we're working within the context of the list monad, I can deal with a single B and a single C, even though the function calls are really giving back lists of those respective types.

By the way, in Haskell the code would really look like this

  makeSomeCsFromAnA a = do
    b <- makeSomeBsFromAnA a
    makeSomeCsFromAB b