да, понятно, спасибо

В хаскелле есть аналог питоновского None?

(), может

в каком-то смысле (), в каком-то Nothing. смотря для чего

граждане, мне не понятно ни что такое fix, ни как работает memoize
чем дольше смотрю - тем меньше понимаю

fix f это способ сделать f (f (f ...))

например

f : Char -> String -> String
f c s = c : s

fix (f 'a') это
f 'a' (f 'a' (f 'a' ...))

то есть

'a' : ('a' : ('a' ...))

тогда в первый раз при вычислении n-ого элемента он пойдет в список, в списке лежит thunk, он вычислит этот thunk (используя n-1 и n-2 элементы по такому же алгоритому), сохранит в списке значение, и в следующий раз оно будет браться из списке

ну то есть мемоизация работает по такому же принципу как и тут

x = 1 + 2

в первый раз когда мы вычисляем x, он сложит 1 + 2, а во второй раз достанет уже сразу 3 (если x не инлайнить)

тут то же самое, только для списка

import Debug.Trace (traceShowId)

fib :: Int -> Integer
fib = \i -> cache !! i
 where
   cache = fmap (fib' . traceShowId) [0..]
   fib' 0 = 1
   fib' 1 = 1
   fib' n = cache !! (n - 2) + cache !! (n - 1)

main = print (fib 10)
-- 10
-- 9
-- 8
-- 7
-- 6
-- 5
-- 4
-- 3
-- 2
-- 1
-- 0
-- result: 89

вот то же самое без всяких фиксов и memoize

traceShowId срабатывает на момент вычисления значения в кеше, и тут видно, что на каждый индекс он срабатывает только один раз

так а fix - это типа рекурсивная композиция?

просто я не понимаю, fix это типа имитация бесконечной структуры данных как дерево?

нет, я же написал, fix f это буквально f (f (f ...))

все остальное неверно

никаких деревьев, никакой структуры данных

понял

сори, у меня просто спутался пример со стековерфлоу

собственно можно так fix и определить, просто это будет неоптимально

fix f = f (fix f)

а определение

fix f = let x = f x in x

шарит одну и ту же f ... в памяти

просто я вижу обращение в правой чати к левой, и думаю что это рекурсия

и вот понимаю что это просто аргумент