Как я могу объединить две карты в один и тот же список?

Мы могли бы объединить два обхода списка xs в выражении

(map f xs, map g xs)

вот так

unzip (map (\x -> (f x, g x)) xs)

Есть ли какие-либо исследования по автоматическому выполнению такого слияния?

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

Редактировать: на самом деле я не собираюсь применять слияние к реальным спискам Haskell в памяти, где это преобразование может не иметь смысла в зависимости от того, можно ли unzip объединить с его потребителем (ями). У меня есть настройка, в которой я знаю, что unzip может плавиться (см. «FlumeJava: простые и эффективные конвейеры параллельных данных»).


haskell fusion
person tibbe    schedule 03.09.2012    source источник
comment
Не автоматически, но в любом случае неплохо: squing.blogspot.com/2008/11/ красивый складной.html   -  person Daniel Wagner    schedule 03.09.2012
comment
Если результат этого не объединяется с чем-то другим, накладные расходы на создание пар и их распаковку будут больше, чем стоимость дополнительного обхода.   -  person augustss    schedule 03.09.2012
comment
@augustss Нет, если обход идет по огромному файлу! Я не планирую применять это к реальным спискам.   -  person tibbe    schedule 03.09.2012
comment
Распаковка будет проходить по списку той же длины, что и карта, поэтому вы не будете сохранять обходы. Теперь, если вы заботитесь об экономии места, которое дает вам слияние, это может иметь огромное значение. Из вашего комментария я сделал вывод, что вы не интересовались космосом, но я вижу, что это не совсем то, что вы сказали. :)   -  person augustss    schedule 03.09.2012
comment
предотвращение дополнительного обхода xs также может быть достигнуто большинством пакетов в стиле итератора.   -  person Chris Kuklewicz    schedule 03.09.2012
comment
@augustss У меня есть потребитель, который может слиться с распаковкой. Я пытаюсь создать слияние братьев и сестер, как описано в FlumeJava: простые и эффективные конвейеры параллельных данных (pages.cs.wisc.edu/~akella/CS838/F12/838.../FlumeJava.pdf) в одном из фреймворков Haskell.   -  person tibbe    schedule 03.09.2012

Ответы (2)


arrow_upward
4
arrow_downward

Также не полностью автоматический, но вы можете дать GHC список таких правил перезаписи. См. 7.14 Правила перезаписи и Использование правил. Затем компилятор использует эти правила для оптимизации вашей программы при компиляции. (Обратите внимание, что компилятор никоим образом не проверяет, имеют ли правила смысл.)

Редактировать. Чтобы привести пример для этой конкретной проблемы, мы можем написать:

{-# OPTIONS_GHC -fenable-rewrite-rules -ddump-rule-firings -ddump-rule-rewrites #-}

import Data.Char

{-# RULES
"map/zip" forall f g xs. (,) (map f xs) (map g xs) = unzip (map (\x -> (f x, g x)) xs)
   #-}

main :: IO ()
main = let x = "abCD" in
        print $ (,) (map toUpper x) (map toLower x)

(имя функции верхнего уровня в правиле — (,) :: a -> b -> (a, b)). При компиляции вы увидите, как применяются правила. Параметр dump-rule-firings показывает сообщение о применении правила, а -ddump-rule-rewrites подробно отображает каждое применение правила — см. 7.14.6. Управление тем, что происходит в правилах перезаписи.

person Petr    schedule 03.09.2012
comment
Я не думаю, что мы можем написать правило для таких выражений. Правила GHC должны начинаться с имени функции. - person tibbe; 04.09.2012

arrow_upward
3
arrow_downward

Мне удалось найти два ресурса, в которых хотя бы кратко упоминаются функции, подобные fusion (un-)zip:

Йозеф Свеннингссон. "Shortcut Fusion для накопления параметров и функций, подобных Zip" http://www.cse.chalmers.se/~josefs/publications/fusion.pdf

Дункан Куттс. «Потоковое слияние: практическое ускоренное слияние для коиндуктивных типов последовательностей» https://community.haskell.org/~duncan/thesis.pdf

Однако ни в одном из ресурсов явно не упоминается этот вид «слияния братьев и сестер».

person tibbe    schedule 03.09.2012
comment
Я не видел эту презентацию, но вот слайды Йозефа о TupleFusion< /а>. - person danr; 03.09.2012
comment
Стратегия автоматической обработки кортежей может быть интересной. - person Jan Christiansen; 04.09.2012