optimization of fst . unzip . zip

[choener]

Hi,

lets assume this:

f n = map (\(a,b) -> (a+1,b+1)) . zip (enumFromN 0 n) (enumFromN 0 n)
g = fst . unzip

main = print . sum . g . f $ 100

In this case i would like to have sum . g . f reduce to sum . enumFromN 0 but this does not happen. Is it in any way possible to get the optimizer to "cut out" unused code paths? The map operation in "f n" is basically a placeholder for something complicated.

If this is possible to optimize correctly, it becomes possible to nicely describe some complicated code paths.

[rl]

We have some support for this in DPH but I haven't included it in vector yet. Note that for fusion to work, you would have to write this:

g = map fst

rather than this:

g = fst . unzip

The latter is impossible to match on. For the former, we're just missing a couple of rules, I'll add them in the next release.

[choener]

I have no problem writing "map fst" if that enables said optimizations in the next release. It means that I can write a number of things in a very "nice" way.

Thanks, Christian

[rl]

This won't make it into 0.7.1 because I don't want to break DPH with this release. I'll try to release 0.8 soon(ish) after and that should contain the necessary fusion magic (unless there is some unforeseen problem with it).

[rl]

It turns out that implementing this particular bit of fusion is an utter pain. I might have a better idea. If you could create a lazy pair of two strict vectors and treat that pair itself as a vector, would that solve the problem? So something like this (yes, the kinds don't quite work out):

data family Tuple v a
data instance Tuple (va,vb) (a,b) = Tuple2 (va a) (vb b)
instance (Vector va a, Vector vb b) => Vector (Tuple (va,vb)) (a,b) where
  ...

The ticket for this is #58.

[choener]

Currently, what is going on is always:

g i z = map (\k -> (k, work k)) $ enumFromN i z

That is a generator produces indices 'k' which are paired with a function doing work. In the forward phase, we are only interested in the work:

reduce i z = fold reducer neutral $ g i z

In the backtrace, we need the index as well -- but do not care about performance:

xs <- toList $ g i z

I'll upload a number of libraries in the coming days. Once done I'll hope to have some time to optimize those.