Haskell - сканирование через несколько списков сразу

Question

Выполнение некоторых университеты домашнего задание, я нашел себя делать что-то подобное:

scanl' (\acc (a, b, c) -> expression) 0 $ zip3 as bs cs

с различным количеством молний списков до 7. Это кажется довольно неэффективным, поскольку он создает дополнительный список кортежей.

Не очень сложно определить scanl2, scanl3 и т. Д. Рекурсивно и не создавать дополнительный список, но количество требуемого шаблона смешно.

Есть ли способ иметь оба - отсутствие шаблона и использование низкой памяти?

Answer 1

Как упоминалось в комментариях, программа Haskell, которая выглядит так, будто она генерирует «дополнительный список», редко генерирует дополнительный список (благодаря ленивой оценке, среди прочего), поэтому вряд ли будет добавлено дополнительное использование памяти с использованием zip3. Если функция используется таким образом, что список может быть потреблен по мере его создания, фактические списки (промежуточные или конечные) не будут произведены.

Для примера рассмотрим следующую Scan.hs программу, которая потребляет большой список с sum, как это производится:

import Data.List (scanl') 

scanl3 :: (acc -> (a, b, c) -> acc) -> acc -> [a] -> [b] -> [c] -> [acc] 
scanl3 f z as bs cs = scanl' f z $ zip3 as bs cs 

main = print $ sum $ scanl3 (\z (a, b, c) -> z + a*b + 2*c) 
          0 [1..100000000] [10,20..] [100,200..] 

При компиляции это для профилирования с -O2 оптимизаций:

ghc -prof -rtsopts=all -O2 Scan.hs 

затем запустить с профилированием кучи:

./Scan +RTS -h 
hp2ps Scan.hp 
evince Scan.ps 

вы обнаружите, что он работает в постоянной памяти около 35k), не создавая ни промежуточный список zip3, ни окончательный список scanl3 явно.

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

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

scanl3 :: (acc -> (a, b, c) -> acc) -> acc -> [a] -> [b] -> [c] -> [acc] 
scanl3 f z (a:as) (b:bs) (c:cs) = z : scanl3 f (f z (a, b, c)) as bs cs 
scanl3 _ z _ _ _ = [z] 

, используя тот же тестовый пример, как описано выше собран с -O2 и обнаружил, что во время выполнения, чтобы быть почти идентичны (15.2sec для zip3 против 16.8sec для рекурсивной).

Обратите внимание, что я явно не сделал рекурсивную версию строгой, но в конкретном случае использования (суммируя ее по мере ее создания) это не имеет никакого значения.

Редактировать: На самом деле, я думаю, это имеет значение. Строгий вариант с использованием шаблона Взрыва:

{-# LANGUAGE BangPatterns #-} 

scanl3 :: (acc -> (a, b, c) -> acc) -> acc -> [a] -> [b] -> [c] -> [acc] 
scanl3 f !z (a:as) (b:bs) (c:cs) = z : scanl3 f (f z (a, b, c)) as bs cs 
scanl3 _ z _ _ _ = [z] 

выглядит, как он может работать последовательно 0,5-1,0 секунды быстрее (из 16secs).