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

[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. Просто в одном случае израсходуешь память, а во втором-третьем - выжрешь стек.

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

jane neale fashion

[(Anonymous)]

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