Compiler optimizations for infinite lists in Haskell?

Question

I've various "partial permutation" functions of type t -> Maybe t that either take me to a new location in a data structure by returning a Just or else return a Nothing if they cannot yet get there.

I routinely must applying these partial permutations in repeated specific patterns, building a list of all intermediate values, but truncating the list whenever I return to my starting position or a permutation fails.

scan_partial_perms :: Eq t => [t -> Maybe t] -> t -> [t]
scan_partial_perms ps v = map fromJust . takeWhile test $ scanl (>>=) (Just v) ps
   where  test (Just i) | i /= v = True
          test _ = False

iterate_partial_perm = scan_partial_perm . iterate
cycle_partial_perms = scan_partial_perms perms . cycle

I'm fairly confident that scanl has the desirable strictness and tail recursion properties in this context. Any other tips on optimizing this code? In particular, what compiler options beyond -O3 -fllvm should I read about?

At worst, I could replace the scanl and infinite list with an accessor function defined like

perm l i = l !! i `rem` length l

I'd imagine this cannot improve performance with the right optimizations however.

Thanks! Also, should I have posted this to codereview.SE instead? — Jeff Burdges
I think it's a pretty good fit for SO because the question is fairly concrete. — Owen

Daniel Fischer Daniel Fischer · Accepted Answer · 2012-01-21T21:40:59

I think you have a bug in scan_partial_perms,

scan_partial_perms ps v = map fromJust . takeWhile test $ scanl (>>=) (Just v) ps

scanl f s list always starts with s, so takeWhile test (scanl ...) is []. If that is intentional, it's quite obfuscated. Assuming what you want is

scan_partial_perms ps v = (v:) . map fromJust . takeWhile test . tail $ scanl (>>=) (Just v) ps

there's not much you can do. You can {-# SPECIALISE #-} it so the Eq dictionary is eliminated for the specialised-for types. That'll do you some good if the compiler doesn't do that on its own (which it may if it can see the use site). With ghc >= 7, you can instead make it {-# INLINABLE #-}, so that it can be specialised and perhaps inlined at each use site.

I don't know what happens down the llvm road, but at the core-level, map, fromJust and takeWhile are not yet inlined, so if you're desperate enough, you can get maybe a few tenths of a percent by inlining them manually if they aren't inlined later in the llvm backend:

scan_partial_perms ps v = v : go v ps
  where
    go w (q:qs) = case q w of
                    Just z
                      | z /= v -> z : go z qs
                    _ -> []
    go _ _      = []

But those are very cheap functions, so the gains - if at all present - would be small.

So what you have is rather good already, if it's not good enough, you need a different route of attack.

The one with the list indexing,

perm l i = l !! (i `rem` length l)
-- parentheses necessary, I don't think (l !! i) `rem` length l was what you want

doesn't look good. length is expensive, (!!) is expensive too, so both should in general be avoided.

Compiler optimizations for infinite lists in Haskell?

1 Answers