к
и при повторном запрашивании элемента мы берем уже вычисленное значение, не вычисляем его повторно
Size: a a a
2021 February 19
к
кэш это ленивый список из ленивых чисел
D
а как при повторном запросе там что-то остаётся
D
?
к
ленивое значение это или конкретное значение, или описание того как значение вычислить
при первом запросе значения оно вычисляется и на том же месте остается уже вычисленное
при первом запросе значения оно вычисляется и на том же месте остается уже вычисленное
к
если знаком другой язык какой-нибудь, то я могу показать похожий такой же ленивый код на другом языке
к
выше я писал об этом:
> ну то есть мемоизация работает по такому же принципу как и тут
>
> x = 1 + 2
>
> в первый раз когда мы вычисляем x, он сложит 1 + 2, а во второй раз достанет уже
> сразу 3 (если x не инлайнить)
> тут то же самое, только для списка
> ну то есть мемоизация работает по такому же принципу как и тут
>
> x = 1 + 2
>
> в первый раз когда мы вычисляем x, он сложит 1 + 2, а во второй раз достанет уже
> сразу 3 (если x не инлайнить)
> тут то же самое, только для списка
к
но если мы никогда не запросим x вычислиться, то 1 и 2 никогда не сложатся, а в памяти просто будет инструкция, как вычислить x (сложить 1 и 2)
D
да ленивость-то это понятно что
а вот само взаимодействие двух рекурсий - фибоначчи и cache
и ещё одно уточнение: !! - это чтобы гетать из списка индекс текущего снимка рекурсии?
а вот само взаимодействие двух рекурсий - фибоначчи и cache
и ещё одно уточнение: !! - это чтобы гетать из списка индекс текущего снимка рекурсии?
D
вообще, спасибо большое за такое детальное объяснение
потому что сам бы я разбирался чёрти сколько
потому что сам бы я разбирался чёрти сколько
к
!! это просто получение значения из списка по индексу
к
просто так вышло, что в списке предыдущие шаги рекурсии
так получается, что прямой рекурсии и нет, cache нерекурсивен, fib' нерекурсивен
просто n-ый элемент cache основывается на n-1 и n-2 элементах cache
так получается, что прямой рекурсии и нет, cache нерекурсивен, fib' нерекурсивен
просто n-ый элемент cache основывается на n-1 и n-2 элементах cache
D
fib' n = cache !! (n - 2) + cache !! (n - 1)а ведь и правда
D
а где рекурсия ж делась для фибоначчи
D
типа из-за fmap?
D
перетекла в бесконечный список получается?
к
рекурсии для фибоначчи нет, она превратилась в рекурсию для cache просто, каждый элемент cache основывается на предыдущих
D
мне очень стыдно что я тупой
D
спасибо!
к
да, я соврал, cache все таки рекурсивен, просто через fmap
fib :: Int -> Integer
fib = \i -> cache !! i
where
cache = fmap
(\x -> case x of { 0 -> 1; 1 -> 1; n -> cache !! (n - 2) + cache !! (n - 1) })
[0..]
если вот так написать то видно
fib :: Int -> Integer
fib = \i -> cache !! i
where
cache = fmap
(\x -> case x of { 0 -> 1; 1 -> 1; n -> cache !! (n - 2) + cache !! (n - 1) })
[0..]
если вот так написать то видно