Re: [stack] map fusion

On Aug 1, 2008, at 12:29 PM, Christopher Diggins wrote:

> I think I understand. To summarize with Cat type notation:
>
> map : (list ('a -> 'a) -> list)
> map* : (list ('A 'b -> 'A 'b) -> list)

I don't understand when you're allowed to omit row variables in Cat's  
notation. I also think you mean "'a -> 'b" rather than "'a -> 'a".

In any case, here are the (simplified) type signatures as they'd  
appear in 5th:

         map[a -> b] : R (a) -> R (b).
    map*[R a -> R b] : R (a) -> R (b).

> In other words, "map" accepts only 1->1 functions, while map*  
> accepts n->n functions where n >= 1.

Correct.

> In Cat I simply disallowed "map" and similar combinators from  
> modifying the stack. It made type analysis easier,

Why would it make type analysis easier?

> it preserved the fusion properties, and it didn't really cause any  
> huge loss of
> expressiveness AFAICT.

This is arguably a reasonable solution in Cat because you have  
'papply' (aka 'curry' in Factor). In 5th however, you don't, so you'd  
have to use variables to write things like 'map-with':

    x map-with[F] -> map[x F].

The only way to write 'map-with' without variables is to use a version  
of 'map' that can call a function that uses more than one element:

    map-with[F] -> map*[over dip[swap F]] nip.

Of the two, I prefer the first version for (obvious) reasons, so  
perhaps this is a bad example.

Still, there are cases where 'map*', 'each*', etc, are quite handy,  
even in a language like Cat. Slava has given me a few examples of  
where they're used in Factor (although obviously not with those names).

- John