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

[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]

Э... в общем, правда. 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)).

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