Антипаттерн?

[deniok]

Некоторое время пользовался вычурной техникой для работы с индексированными семействами функций. Есть семейство (список)

f :: Int -> a -> a

причём разные параметры Int задают разные элементы семейства f 1, f 2, f 3. При этом требуемая свёртка имеет вид

f n ( ... (f 3 (f 2 (f 1 x)))) ... )

Техника такая

chain_bad f n = foldl' (flip (.)) id $ map f [1..n]

Мэп делает список функций типа a->a, после чего идёт свёртка по композиции, ну и, скажем,

*Tst> chain_bad (+) 10 0
55

монтирует

(10+).(9+).(8+). ... .(1+).id $ 0

и вычисляет его.

Одна гадость обнаружилась на этом пути - линейный по n space leak, и, ясен перец:

*Tst> chain_bad (+) 1000000 0
*** Exception: stack overflow

Причём, похоже, непобедимый, поскольку непонятно, как тут расставить устрожители ($!) так, чтобы шаг фолдинга инициировал ровно один нужный ему шаг мэппинга. Я потратил часа полтора, но так и не придумал.

Потом стало понятно, что, если без flip, то это будет простой foldr, в котором от линейного по n thunk'а не избавиться - он начинает сворачиваться, только когда мы разобрали список до основанья:

f 1 (f 2 (f 3 ( ... (f n x)...))))

А затем :)

Затем меня осенило! На фиг список! Сделаем убывающую рекурсию по n и поставим seq там где надо:

chain_good f 0 x = x 
chain_good f n x = let res = f n x in 
                   res `seq` chain_good f (pred n) res

Хе-хе, всё работает и на миллионе:

*Tst> chain_good (+) 1000000 0
500000500000

Подлый thunk повержен! Однако, стоп, этот код что-то сильно напоминает. Смотрим исходники GHC - точно: это же foldl', только с инверсией аргументов f. То есть можно и так:

chain_good' f n x = foldl' (flip f) x [n, pred n .. 1]

Осталось поправить пропущенную в процессе "осенения" деталь - вместо

f n ( ... (f 3 (f 2 (f 1 x)))) ... )

у меня теперь

f 1 ( f 2 (f 3 ( ... (f n x) ... ))))

Но это легко поправимо

chain f n x = foldl' (flip f) x [1 .. n]

Глядя на окончательную версию, чувствуешь себя слегка идиотом :)))
И остается вопрос из заголовка: фолдить композицией список функций порожденный мэппингом - это таки антипаттерн из-за space leak?

Comments

[kodt-rsdn.livejournal.com]

Кстати говоря о преобразованиях.
Если бы ты с самого начала увидел, что функция двухместная, и прямо-таки напрашивается записать её инфиксно
n `f` ((n-1) `f` (...(1 `f` x)...)), то сразу получил бы
x `f'` 1 `f'` 2 `f'` ... `f'` n, где f' = flip f.

А насчёт антипаттерна... Конечно: chain_bad возвращает мега-функцию от одного аргумента x. Ну эту мегафункцию надо же где-то хранить, не так ли?
В отличие от chain_good, которая благодаря каррингу не рожает мега-функцию, а терпеливо дожидается x и уже с ним проводит все вычисления.

Причём неважно, используешь в chain_bad энергичный foldl' или ленивые foldl, foldr. Просто в одном случае израсходуешь память, а во втором-третьем - выжрешь стек.

Отсюда мораль: карринг не самоцель :)

[deni-ok.livejournal.com]

Угу, только вот

chain_lazy f n x = foldl (flip f) x [1..n]

тоже даёт

*Tst> chain_lazy (+) 1000000 0
*** Exception: stack overflow

Из-за чего, собственно, весь сыр-бор. Цель - убить большой ленивый thunk, который и даёт space leak.

[kodt-rsdn.livejournal.com]

А ленивые фолды по-любому покажут спейс-личико ;)
foldl идёт по списку и строит левое поддерево ((0+1)+2)+...).
foldr заменяет x:xs на x+(foldr (+) 0 xs), но поскольку корневой + энергичный, то он спровоцирует вычисление (начиная со строительства) всего правого поддерева.
Вот если бы вместо + было что-нибудь ленивое - например, конструктор структуры или функция с условием, - то личико бы не открылось.

[deni-ok.livejournal.com]

Собственно ещё неприятно, что я в принципе понимаю, как chain_bad (+) 10 0 вычисляется, и что там конструируется. По виду псевдокода

(10+).(9+).(8+). ... .(1+).id $ 0

кажется, что форсировать в принципе можно - справа всё последовательно сворачивается. Но где в вызове и/или самом коде расставить ($!) для этого? Вроде выходит, что в такой реализации chain_bad нефорсируем :(

[kodt-rsdn.livejournal.com]

Ещё раз объясни: во что ты предполагаешь форсировать chain_bad?
Это не каррированная функция, которая возвращает мега-функцию от одного аргумента.
Форсировкой ты только добьёшся полного построения этой мега-функции и отжора памяти.

Тут наоборот должно быть: надо возвращать недостроенную функцию.
Причём такую, которая не строится, а сразу вычисляется-и-забывается. Иначе после первого вычисления она опять-таки отожрёт память.
Так мы плавно переходим к мысли, что chain должна быть каррированной... ;)

[deni-ok.livejournal.com]

Когда я пишу

let chain_bad f n = foldl (flip (.)) id $ map f [1..n]

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

chain_bad (+) 1000000 0

на каждом шаге фолдинга форсировалось бы откусывание от списка функций одной штуки (при разборе конструктора), и ее применение. То есть - ленивость по деконструированию и строгость по обработке каждого шага. Похоже это слишком :)

[kodt-rsdn.livejournal.com]

Э... в общем, правда. Thunk.

Если отвлечься от фолдов, то правильная рекурсия выглядит так

chain f n x = run 1 x where
  run k x | k<=n      = run (k+1) $! (f k x)
          | otherwise = x

И вот каким-то макаром надо выдрать x из определения run.

  run k | k<=n      = run (k+1) .! (f k)
        | otherwise = id

где неведомый .! - комбинатор, форсирующий вычисление правой функции.
Что-то типа

f .! g = \x -> f $! (g x)

Что-то меня обуяли вопросы, где здесь надо форсировку ставить... то ли между (run (k+1)) и (f k), то ли между (f k) и x.
И не получится ли так, что форсировка приведёт к конструированию всей ветки (run (k+1)).

А экспериментировать сейчас не очень досуг.

jane neale fashion

[(Anonymous)]

whats the fashion in china http://clothingtrends.eu/zu-elements-brand48.html 2007 fwomen fashion 2785944