foldr in terms of map

[Hal Daume]

Hi, quick reply :)...i've reordered some of what you've said (i hope you
don't mind!)

> However the monad is defined, sequence_ has to process the entire list
> before anything can be determined about the result. The entire result
> of (>>) depends upon both arguments, whereas you can deduce the head
> of the result of (:) based solely upon the first argument.

yes, thanks.

> 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?).

> An implementation using a simple state-transformer monad (s -> (a, s))
> wouldn't look significantly different to one using IORef/STRef.

True :).

Thanks for your comments!

 - Hal