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
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>
participants (2)
-
Glynn Clements -
Hal Daume