foldr in terms of map

[Glynn Clements]

Hal Daume wrote:

> > Yeah, but given that sequence_ is essentially the direct monadic
> > translation of fold:
> > that might be considered cheating (i.e. we can implement fold using
> > only map and fold, although the fold can be "disguised").
> > <snip>
> > As mentioned above, sequence_ etc are essentially the embodiment of
> > primitive recursion.
> 
> Is this true in the same way that the statement 'foldr' is the
> embodiment of PR is true?  That is, can you write foldr in terms of
> sequence_?  It doesn't seem possible: you seem to also need the map in
> order to get the list lifted into the monadic world and I don't think
> you can even write map in terms of sequence_ (am I wrong?).

Well, I did say "the direct *monadic* translation", i.e. a fold of
actions rather than values.

AFAICT, the main problem with implementing "map" itself is that you
would first need to lift the list of elements into the monad, which
would basically require map. OTOH, the actions themselves aren't
recursive (each action would take one element from the input list,
apply the function, and add the result to the output list), so
ignoring the "translation" issue doesn't appear to be cheating.

Maybe I'm overlooking something fundamental (I would have thought that
someone with a stronger theoretical grounding than me would have
picked up on this), but I'm pretty sure that we aren't getting
primitive recursion for free, and I can't see it coming from
references (there's nothing PR about the get/put operations for a
simple state transformer monad).

-- 
Glynn Clements <glynn.clements@virgin.net>