Установка верхнего предела для входа, установленного в соответствии с функцией выхода

Question

В настоящее время я застрял в установке верхних пределов в списках.

Я пытаюсь найти все числа Фибоначчи ниже миллиона. Для этого я разработал довольно простую рекурсивную функцию Фибоначчи

fib :: Int -> Integer
fib n
    n == 0    = 0
    n == 1    = 1
    otherwise = fib (n-1) + fib (n-2)

То, на чем я застрял, это определение миллионной части. Теперь у меня есть:

[ fib x | x <- [0..35], fib x < 1000000 ]

Это потому, что я знаю, что 35-е число в последовательности Фибоначчи - достаточно большое число. Однако я хотел бы найти этот предел с помощью функции и установить его таким образом.

[ fib x | x <- [0..], fib x < 1000000 ]

Это дает мне цифры, но оно просто не останавливается. Это приводит к тому, что Хаскелл пытается найти числа Фибоначчи ниже миллиона в последовательности, что довольно бесполезно.

Может ли кто-нибудь помочь мне с этим? Это будет высоко ценится!

Answer 1

Проверка fib x < 1000000 в понимании списка отфильтровывает значения fib x, которые меньше, чем 1000000; но понимание списка не может знать, что большие значения x подразумевают большее значение fib x и, следовательно, должны продолжаться, пока все x не будут проверены.

Используйте takeWhile вместо:

takeWhile (< 1000000) [ fib x | x <- [0..35]]

Answer 2

Понимание списка гарантированно просматривает каждый элемент списка. Вы хотите takeWhile :: (a -> Bool) -> [a] -> [a]. С этим ваш список просто takeWhile (< 1000000) $ map fib [1..]. Функция takeWhile просто возвращает ведущую часть списка, которая удовлетворяет данному предикату; есть также похожая функция dropWhile, которая удаляет ведущую часть списка, которая удовлетворяет данному предикату, а также span :: (a -> Bool) -> [a] -> ([a], [a]), которая равна (takeWhile p xs, dropWhile p xs), и аналогично break, который разбивает список на две части, когда предикат истинен (и эквивалентен span (not . p). Таким образом, например:

• takeWhile (< 3) [1,2,3,4,5,4,3,2,1] == [1,2]
• dropWhile (< 3) [1,2,3,4,5,4,3,2,1] == [3,4,5,4,3,2,1]
• span (< 3) [1,2,3,4,5,4,3,2,1] == ([1,2],[3,4,5,4,3,2,1])
• break (> 3) [1,2,3,4,5,4,3,2,1] == ([1,2,3],[4,5,4,3,2,1])

Answer 3

Следует отметить, что для такой задачи «каноническим» (и более быстрым) способом является определение чисел как бесконечного потока, например:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

takeWhile (<100) fibs
--[0,1,1,2,3,5,8,13,21,34,55,89]

Рекурсивное определение может выглядеть страшно (или даже«Волшебный»), но если вы «думаете ленивый», это будет иметь смысл.

«Нечеткий» (и в некотором смысле более «императивный») способ определить такой бесконечный список:

fibs = map fst $ iterate (\(a,b) -> (b,a+b)) (0,1) 

[Редактировать]

Для эффективного прямого вычисления (без бесконечного списка) вы можете использовать умножение матриц :

fib n = second $ (0,1,1,1) ** n where
   p ** 0 = (1,0,0,1)
   p ** 1 = p
   p ** n | even n = (p `x` p) ** (n `div` 2)
          | otherwise = p `x` (p ** (n-1))
   (a,b,c,d) `x` (q,r,s,t) = (a*q+b*s, a*r+b*t,c*q+d*s,c*r+d*t)
   second (_,f,_,_) = f

(Это было действительно весело писать, но я всегда благодарен за предложения)

Answer 4

Самое простое, о чем я могу подумать:

[ fib x | x <- [1..1000000] ] 

С fib n > n для всех n > 3.