foldr in terms of map

[Glynn Clements]

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 <glynn.clements@virgin.net>