Оптимизация компилятора для бесконечных списков в Haskell? - PullRequest
Новая
       19

Оптимизация компилятора для бесконечных списков в Haskell?

1 голос
/ 21 января 2012

У меня есть различные функции «частичной перестановки» типа t -> Maybe t, которые либо переводят меня в новое место в структуре данных, возвращая Just, либо возвращают Nothing, если они еще не могут туда добраться.

Мне обычно приходится применять эти частичные перестановки в повторяющихся определенных шаблонах, составлять список всех промежуточных значений, но обрезать список всякий раз, когда я возвращаюсь к своей исходной позиции или перестановка завершается неудачей. 

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

Я вполне уверен, что scanl обладает желательными свойствами строгости и хвостовой рекурсии в этом контексте. Любые другие советы по оптимизации этого кода? В частности, о каких параметрах компилятора, помимо -O3 -fllvm, мне следует прочитать?

В худшем случае я мог бы заменить scanl и бесконечный список функцией доступа, определенной как 

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

Я думаю, что это не может улучшить производительность при правильной оптимизации.

1 Ответ

2 голосов
/ 22 января 2012

Я думаю, у вас есть ошибка в scan_partial_perms, 

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

scanl f s list всегда начинается с s, поэтому takeWhile test (scanl ...) равно [].Если это намеренно, это довольно запутано.Предполагая, что вы хотите 

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

, вы мало что можете сделать.Вы можете {-# SPECIALISE #-} сделать это так, словарь Eq исключен для специализированных типов.Это пойдет вам на пользу, если компилятор не сделает этого сам по себе (а может, если увидит сайт использования).С ghc> = 7 вы можете вместо этого сделать его {-# INLINABLE #-}, чтобы он мог быть специализированным и, возможно, встроенным на каждом сайте использования.

Я не знаю, что произойдет в будущем, но нана уровне ядра, map, fromJust и takeWhile еще не встроены, поэтому, если вы достаточно отчаялись, вы можете получить, возможно, несколько десятых процента, вставив их вручную, если они не встроены позже вбэкэнд llvm: 

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 _ _      = []

Но это очень дешевые функции, поэтому выгоды - если они вообще есть - были бы небольшими.

Так что то, что у вас уже есть, довольно хорошо, если ононедостаточно хорош, вам нужен другой путь атаки.

Тот, с индексированием списка, 

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

выглядит не очень хорошо.length стоит дорого, (!!) тоже дорого, поэтому в общем следует избегать обоих.

...