Hal Daume wrote: > > map f = foldr ((:) . f) [] > > as I understand it, this is essentially because foldr encapsulates all > primitive recursive functions and since map is primitive recursive, we > can implement it in terms of a fold. > > one thing that is interesting to note is that if we are also given > references, a function to sequence monadic actions ('sequence_') and > reverse, we can write foldr in terms of map
Yeah, but given that sequence_ is essentially the direct monadic translation of fold: sequence_ :: Monad m => [m a] -> m () sequence_ = foldr (>>) (return ()) that might be considered cheating (i.e. we can implement fold using only map and fold, although the fold can be "disguised"). > now, when we're in the IO monad, the difference between the real foldr > and the simulated one is that the simulated one cannot deal with > infinite inputs. for instance: > > > head $ foldr (:) [] [1..] > > should return 1, which it does for the real version. the simulated one > hangs. > > one might like to attribute this to the fact that IO is a strict monad, Yep. > but that doesn't seem to be all -- we would also need to be able to read > and write references lazily in order to get this to work completely. Which is basically the same thing as "IO is strict". > Q1: is this correct? is there a way to "fix" the above definition or to > use a different monad to get laziness? i think not, but can't prove it. 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. > now, if we just limit ourselves to finite inputs, things look a lot > better. however, this brings up really the main question i have. > > foldr (in its original form) is in some sense quintessentially(sp?) PR > on lists, whereas map is not. however, it seems that the combination > map+rsequence_+references is enough to give you full PR power. As mentioned above, sequence_ etc are essentially the embodiment of primitive recursion. > what more can we say about this? clearly references play the largest > role here, I disagree; sequencing is the key factor. The core issue is that each recursive call receives a parameter which depends upon all previous steps, unlike map, where each step is independent (for a monadic implementation, this actually occurs in the "run" operation, e.g. runST). An implementation using a simple state-transformer monad (s -> (a, s)) wouldn't look significantly different to one using IORef/STRef. > but it also seems impossible to remove this dependence on the > sequencing operation. Yep. -- Glynn Clements <[EMAIL PROTECTED]> _______________________________________________ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell