Существует ли оптимизированная комбинация `span` и `foldl'`, или эта комбинация будет оптимизирована GHC?

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

addPos l = s `seq` (s,back)
  where
    (front, back) = span (>= 0) l
    s = sum front

где seq должен гарантировать, что никто случайно не создаст огромный преобразователь, заставив вернуться перед суммой.

Однако мне любопытно, достаточно ли умен GHC, чтобы избежать создания промежуточного переднего списка. Кроме того, может ли кто-нибудь объяснить, как (если вообще) выясняется, что он может накапливаться строго в сумме? В определении Prelude используется foldl, а не foldl', и определение GHC выглядит эквивалентно.


optimization fold haskell ghc
person dfeuer    schedule 22.01.2014    source источник
comment
Кроме того, может ли кто-нибудь объяснить, как (если вообще) выясняется, что он может накапливаться строго в сумме? foldl является встроенным, а plus — строгим. Анализатор строгости делает все остальное. foldl' редко требуется по этой причине.   -  person Philip JF    schedule 22.01.2014
comment
span более или менее 'takeWhile' p xs, 'dropWhile' p xs. Но зачем вам использовать span, если у вас проблемы с производительностью addPlus? Изучите haskell.org/ghc/docs/latest/ html/users_guide/rewrite-rules.html, как говорит jberryman.   -  person Jonke    schedule 22.01.2014

Ответы (1)


arrow_upward
5
arrow_downward

Когда мы говорим об оптимизации компилятором промежуточных списков, обычно мы говорим о «слиянии», реализованном в прагме RULES GHC; вы можете узнать, как это работает и какие функции списка являются "хорошими потребителями" и "производителями" здесь.

К сожалению, span не выглядит "хорошим продюсером". Вы можете убедиться в этом сами, попросив посмотреть основные выходные данные GHC и получить список правил, которые сработали с помощью ghc -O2 -ddump-simpl -dsuppress-module-prefixes -dsuppress-uniques -ddump-core-stats -ddump-inlinings -ddump-rule-firings test.hs.

Вот очищенный вывод:

Rule fired: Class op >=
Rule fired: SPEC Data.List.sum
Inlining done: geInt{v r3n} [gid]
Inlining done: sum_sum1{v rkV} [gid]
Inlining done: span{v r1Q} [gid]
Inlining done: sum_sum'1{v rl6} [gid]

==================== Tidy Core ====================
Result size of Tidy Core = {terms: 24, types: 27, coercions: 0}

addPos1 :: Int -> Bool
addPos1 = \ (ds :: Int) -> case ds of _ { I# x -> >=# x 0 }

addPos [InlPrag=INLINE[0]] :: [Int] -> (Int, [Int])
addPos =
  \ (w :: [Int]) ->
    case $wspan @ Int addPos1 w of _ { (# ww1, ww2 #) ->
    case $wsum' ww1 0 of ww3 { __DEFAULT -> (I# ww3, ww2) }
    }

Вы можете видеть, что мы вызываем какой-то переписанный/специализированный span, за которым следует sum.

Вы можете увидеть, может ли библиотека vector объединить их, или посмотреть, как производительность сравнивается для развлечения.

person jberryman    schedule 22.01.2014
comment
Спасибо за исследование! Следующий вопрос, конечно, есть ли стандартная функция объединения foldl с span, или мне просто нужно накатить свою. - person dfeuer; 22.01.2014