A
ну тут явно хвостовой вызов
Size: a a a
2020 December 15
AA
также можно не сделать стековерфлоу без тко
AA
ну тут явно хвостовой вызов
ну я так и сказал, что с тко можно стек вышибить
A
можно
AA
это опять исполнение в какой-то песочнице? потому что при настройках стека по умолчанию его скорее при зацикливании только переполнить можно
A
мм, ну у меня вот такое:
game i n m = n' : game (i+1) n' m'
where
n' = i - 1 - M.findWithDefault (i-1) n m
m' = M.insert n (i-1) m
game i n m = n' : game (i+1) n' m'
where
n' = i - 1 - M.findWithDefault (i-1) n m
m' = M.insert n (i-1) m
AA
ну так тут и при работающей ТКО можно стек переполнить
AA
ПМ аллоцирует на СТГ-ном стеке же
AA
но и рекурсия не хвостовая
A
сделал без списка
AA
но даж если переписать с аккумулятором все равно вышибет если вычисление n' не форсировать на каждом шаге
A
game turn i n m = if i == turn then n' else game turn (i+1) n' m'
where
n' = i - 1 - M.findWithDefault (i-1) n m
m' = M.insert n (i-1) m
A
теперь точно хвостовая
AA
ну теперь только форсировать аккумуляторы осталось
AA
да, рекурсивная лапша может и без того соптимизироваться, особенно мономорфная, но лучше ее конечно не писать
A
ага, форсировал, дошло до конца
A
real 1m3.672s
user 1m3.274s
sys 0m0.377s
user 1m3.274s
sys 0m0.377s
TZ
у меня тоже как-то всё не слишком радужно на иммутабельных мапах=)
A
мне вот интересно, насколько там большие числа вообще бывают. На си я бы просто сделал тупо массив вообще без хеширования
AP
Достаточно большие