к
рекурсия тут есть, в самом определении fix
Size: a a a
2021 February 19
D
так а почему она конечная тогда
D
f применяет fix f который применяет fix f
D
блин - не вижу выхода
к
она и не конечная, просто сама функция f из fix f можно не использовать аргумент
D
а, погоди - там пропал аргумент с двух сторон, да?
к
fix (\_ -> 0)
вернет 0, не вычисляя свой аргумент (который бесконечный)
вернет 0, не вычисляя свой аргумент (который бесконечный)
к
язык же ленивый, если не использовать значение (пусть оно и бесконечное), то оно и не будет вычисляться
к
length1 x =
case x of
[] -> 0
_:xs -> 1 + length1 xs
length2 = fix $ \len ->
\x ->
case x of
[] -> 0
_:xs -> 1 + len xs
case x of
[] -> 0
_:xs -> 1 + length1 xs
length2 = fix $ \len ->
\x ->
case x of
[] -> 0
_:xs -> 1 + len xs
к
тут мы на ветке [] -> 0 не стали использовать дальше len, поэтому бесконечное значение из fix (\len -> ...) дальше уже не вычисляется
D
окей окей, до меня аккуратно доходит, спасибо
к
f :: ([a] -> Int) -> ([a] -> Int)
f len x =
case x of
[] -> 0
_:xs -> 1 + len xs
length2 :: [a] -> Int
length2 = fix f
вот тут с типами, больше понятно почему несколько аргументов в лямбде fix
f len x =
case x of
[] -> 0
_:xs -> 1 + len xs
length2 :: [a] -> Int
length2 = fix f
вот тут с типами, больше понятно почему несколько аргументов в лямбде fix
D
да, спасибо, мне на самом деле по этой функции досаточно было понять что просто аргумент кикнули
D
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
а скажи пожалуйста, ты здесь использовал fmap, потому что сложная функция внутри?
просто я вижу работу с листом
просто я вижу работу с листом
к
можно и просто map
к
map :: (a -> b) -> [a] -> [b]
map = fmap
map = fmap
к
берется список [0, 1, ...]
и каждый элемент i превращается в fib' i
и каждый элемент i превращается в fib' i
к
получется бесконечный список из всех чисел фибоначчи
к
но каждый элемент в списке не вычислен (как и вообще список), и только когда мы зарашиваем N-ый элемент списка, мы его вычисляем
то есть получается кэш, в котором уже есть все значения, но не вычисленные, а когда мы запрашиваем элемент, то вычисляем его
то есть получается кэш, в котором уже есть все значения, но не вычисленные, а когда мы запрашиваем элемент, то вычисляем его
D
то есть кэш - это просто ленивая функция?