Почему не работает мемоизация?

Речь идет о явном и неявном совместном использовании. Когда вы явно называете вещь, она, естественно, может использоваться совместно, то есть существовать как отдельная сущность в памяти и использоваться повторно. _{(Конечно, совместное использование не является частью языка как такового, мы можем лишь немного подтолкнуть компилятор к совместному использованию некоторых вещей).}

Но когда вы пишете одно и то же выражение дважды или трижды, вы полагаетесь на то, что компилятор заменит общие подвыражения одной явно общей сущностью. Это может случиться, а может и не случиться.

Ваш первый вариант эквивалентен

memoized_fib :: Int -> Integer
memoized_fib = (map fib [0 ..] !!)  where
        fib 0 = 0
        fib 1 = 1
        fib n = memoized_fib (n-2) + memoized_fib (n-1)

Здесь вы конкретно называете сущность и обращаетесь к ней по этому имени. Но это функция. Чтобы сделать повторное использование еще более определенным, мы можем указать фактический список значений, которые передаются здесь, явно:

memoized_fib :: Int -> Integer
memoized_fib = (fibs !!)  where
        fibs = map fib [0 ..] 
        fib 0 = 0
        fib 1 = 1
        fib n = memoized_fib (n-2) + memoized_fib (n-1)

Последнюю строку можно сделать еще более наглядной, добавив явную ссылку на реальную сущность, которой мы делимся здесь, — список fibs, который мы только что назвали на шаге выше:

        fib n = fibs !! (n-2) + fibs !! (n-1)

Ваш второй вариант эквивалентен этому:

memoized_fib :: Int -> Integer
memoized_fib = (map fib [0 ..] !!)  where
        fib 0 = 0
        fib 1 = 1
        fib n = (map fib [0 ..] !!) (n-2) + (map fib [0 ..] !!) (n-1)

Здесь у нас есть три, казалось бы, независимых выражения map, которые могут быть разделены или не разделены компилятором. Компиляция с помощью ghc -O2, по-видимому, снова вводит совместное использование, а вместе с ним и скорость.

momoized_fib = ... - это простое определение верхнего уровня. это может быть прочитано как постоянное ленивое значение (без каких-либо дополнительных аргументов, необходимых для привязки перед его расширением. Это своего рода «источник» ваших запомненных значений.

Когда вы используете (memoizer fib) (n-2), создается новый источник значений, который не имеет отношения к memoized_fib и поэтому не используется повторно. На самом деле вы переносите большую нагрузку на GC здесь, так как вы создаете много (map fib [0 ..]) последовательностей во втором варианте.

Рассмотрим также более простой пример:

f = \n -> sq !! n where sq = [x*x | x <- [0 ..]]
g n = sq !! n where sq = [x*x | x <- [0 ..]]

Сначала будет сгенерирован один f и связанный с ним sq, потому что в заголовке объявления нет n. Второй создаст семейство списков для каждого другого значения f n и переместится по нему (не ограничиваясь фактическими значениями), чтобы получить значение.