-2

我在博客中搜索了与我想要的类似的斐波那契实现。尽管有很多关于 Haskell 的 Fibonacci 实现的问题，但什么也没出现。

我想要一个递归斐波那契函数（速度无关紧要），在每次调用 fib 函数时将每个斐波那契数附加到一个全局列表中。我是 Haskell 的新手，来自命令式背景。这是我认为可行但没有成功的方法。

fibos = []

fib 0 = 1
fib 1 = 1
fib n = (fib(n-1) + fib(n-2)):fibos


main = do 
    putStrLn "Please enter a number:"
    n <- readLn
    fib n
    print fibos

我知道 Haskell 中已经存在的斐波那契列表，但我的分配规范希望我以这种方式进行。我正在尝试将每个斐波那契数限制为用户定义的数 n 到空的全局 fibos 列表中。任何帮助或指示将不胜感激。

编辑：

我现在有一个工作函数，它返回一个包含 n 个元素的斐波那契数列表，其中 n 是用户输入，这里是代码：

fib::Int->Int
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
fibList n = map fib [0..n]

main :: IO ()
main = do 
    putStrLn "Please enter a positive integer:"
    n <- readLn 
    print (fibList n)

我需要的是一个函数，如果用户输入 2，则打印 [0,1,1,2]，如果用户输入 8 或 8 到 12 之间的任何值，则打印 [0,1,1,2,3,5,8]（因为 13 是一个小数字）。

4

4 回答 4

2 
import Data.List

fibo :: Int -> Int
fibo 0 = 0
fibo 1 = 1
fibo n = fibo (n-1)+fibo(n-2)


fiboList x =map fibo [1..x]

main = do
    print ( fiboList 35 )
于 2019-08-14T12:27:09.350 回答
1

如果可以返回列表，您可以根据需要执行类似的操作：

fibs 0 = [0]
fibs 1 = [0,1]
fibs n = let fs@(f1:f2:_) = fibs (n-1) 
         in (f1+f2) : fs

然后fibs 10会返回[55,34,21,13,8,5,3,2,1,1,0]。请注意，以相反的顺序构建列表会浪费或更复杂，因为 Haskell 列表仅在“前面”运行。对于奇怪的fs@(f1:f2:_)，请查阅https://en.wikibooks.org/wiki/Haskell/Pattern_matching（@是“as”-pattern）

对于“真正的”斐波那契函数，您只需要返回头部：

fib n = head (fibs n)

我认为这个版本非常接近你的意图，它的性能也还可以。但是，此代码不是很地道。这里的典型方法是无限列表（如其他一些答案所示）。

如果你允许我说个人的话：我发现在学习 Haskell 时，“命令式”知识比帮助更令人恼火。我认为您应该有意识地尝试“忘记”或“忘记”您对（命令式）编程的了解，以便“了解”函数式编程。

于 2015-10-26T14:02:49.877 回答
1

编辑：

如果您只需要查看导致 的值序列，则fib n应该使用以下内容：

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
fib n = (take n fibs, fibs !! n)

像这样工作：

*Main> fib 0
([],0)
*Main> fib 1
([0],1)
*Main> fib 10
([0,1,1,2,3,5,8,13,21,34],55)

如果您愿意，您可以使用 State monad 来分离计算的列表方面，但这仅意味着在有限范围内（例如main函数）是“全局”的列表。这是您在适当的 Haskell 土地上最接近您想要的方式。

正确的方式

我假设您正在尝试这样做是为了做momoization？如果是，基本上在任何基于列表的实现的引擎盖下已经有一个全局列表fib——任何调用者fib使用与 Haskell（例如 GHC）运行时在引擎盖下使用的相同的惰性评估列表；该列表中已计算的任何元素都不会被重新计算。

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

— 这里fibs 是一个全局列表，虽然您不能显式/手动改变它，但通过访问其中的单个元素 ( fibs !! n)，当运行时向它添加新值时，您会间接导致底层列表发生突变。

错误的方式（但如果您不打算在实际代码中使用它，请继续）

另一方面，如果您只是为了拥有该列表而需要该列表，例如出于调试或其他一些奇怪的原因，您可以使用非常丑陋且不安全的黑客攻击，例如以下IORef基于解决方案，但请记住坚持以 . 结尾的函数名称，Unsafe本着 stdlib 如何标记所有不安全调用的精神，以便使用它们的人意识到危险：

import Data.IORef
import System.IO.Unsafe (unsafePerformIO)

fibsStorageUnsafe :: IORef [Integer]
fibsStorageUnsafe = unsafePerformIO $ newIORef []

-- this is one one that uses the pure definition
-- above to compute the value and then store it
-- in a global, mutable IORef
fibUnsafe n = unsafePerformIO (updateFibs ret) `seq` ret
  where
    ret = fib' n

    updateFibs x = do
      old <- readIORef fibsStorageUnsafe
      writeIORef fibsStorageUnsafe (x:old)

    fib' :: Int -> Integer
    fib' 0 = 0
    fib' 1 = 1
    -- you can recursively call fib' instead of fibUnsafe
    -- to only log the "top level" (non-recursive)
    -- calls to fibUnsafe and not all recursive calls
    fib' n = fibUnsafe (n-1) + fibUnsafe (n-2)

像这样工作：

*Main> readIORef fibsStorageUnsafe
[]
*Main> fibUnsafe 0
0
*Main> readIORef fibsStorageUnsafe
[0]
*Main> fibUnsafe 1
1
*Main> readIORef fibsStorageUnsafe
[1,0]
*Main> fibUnsafe 3
2
*Main> readIORef fibsStorageUnsafe
[1,0,1,1,2,1,0]
*Main> fibUnsafe  10
55
*Main> readIORef fibsStorageUnsafe
[1,0,1,1,2,1,0,1,3,1,0,1,1,2,5,1,0,1,1,2,1,0,1,3,8,1,0,1,1,2,1,0,1,3,1,0,1,1,2,5,13,1,0,1,1,2,1,0,1,3,1,0,1,1,2,5,1,0,1,1,2,1,0,1,3,8,21,1,0,1,1,2,1,0,1,3,1,0,1,1,2,5,1,0,1,1,2,1,0,1,3,8,1,0,1,1,2,1,0,1,3,1,0,1,1,2,5,13,34,1,0,1,1,2,1,0,1,3,1,0,1,1,2,5,1,0,1,1,2,1,0,1,3,8,1,0,1,1,2,1,0,1,3,1,0,1,1,2,5,13,1,0,1,1,2,1,0,1,3,1,0,1,1,2,5,1,0,1,1,2,1,0,1,3,8,21,55,1,0,1,1,2,1,0]

您可以调整 和其他组件的定义以适应您的目标fibUnsafe，fib'但同样：我强烈建议您不要使用这样的方法，除非它仅用于学习或实验目的。

例如，如果您修改为不这样fib'调用自身：fibUnsafe

fib' n = fib' (n-1) + fib' (n-2)

然后调用fibUnsafe 10将产生以下内容，fibStorageUnsafe而不是您在上面看到的内容：

*Main> fibUnsafe  10
55
*Main> readIORef fibsStorageUnsafe
[55]

免责声明：我什至不知道IORef上面的基于代码是否在所有情况下都能正常工作——我承认我不太熟悉IORefs 以及如何unsafePerformIO为上面代码的语义提供任何保证。

于 2015-10-26T13:34:48.313 回答
0

在纯函数式编程中，不使用全局可变变量。因此，如果您定义一个全局值fibos = []，那么该列表将永远是一个空列表。如果您想要一个不可变的顶级定义，则将其固定为第n个斐波那契数（其中n在运行时确定并且fibs没有参数）变得困难。

另一种方法是 Haskell 的惰性求值，它使您能够为所有斐波那契数创建顶级定义，但它们只会在请求的范围内计算。

fibs :: [Integer]
fibs = 1:1:zipWith (+) fibs (tail fibs)

或者不那么花哨：

fibs :: [Integer]
fibs = fib 0 1
  where fib a b = b : fib b (a+b)

然后，您可以根据需要提取尽可能多的斐波那契数：

main :: IO ()
main = do
  putStr "n: "
  n <- readLn
  putStrLn $ "Fibs: " ++ show (take n fibs)
于 2015-10-26T12:06:45.643 回答