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

[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

[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), но поскольку корневой + энергичный, то он спровоцирует вычисление (начиная со строительства) всего правого поддерева.
Вот если бы вместо + было что-нибудь ленивое - например, конструктор структуры или функция с условием, - то личико бы не открылось.