我理解Big-O表示法,但我不知道如何为许多函数计算它.特别是,我一直试图弄清楚Fibonacci序列的幼稚版本的计算复杂性:
int Fibonacci(int n)
{
if (n <= 1)
return n;
else
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
Fibonacci序列的计算复杂度是多少以及如何计算？
看一下GHC源代码,我可以看到修复的定义是:
fix :: (a -> a) -> a
fix f = let x = f x in x
在一个示例中,修复程序使用如下:
fix (\f x -> let x' = x+1 in x:f x')
这基本上产生了一个数字序列,它们增加1到无穷大.为了实现这一点,修复必须将它接收的函数作为它的第一个参数直接回到该函数.我不清楚上面列出的修复定义是如何做到的.
这个定义是我如何理解修复的工作原理:
fix :: (a -> a) -> a
fix f = f (fix f)
所以现在我有两个问题:
我正在从命令式（主要是 C）编程角度学习 Haskell，并对 Prolog 有一些基本的了解。在尝试解决一些练习时，我遇到了一个困扰我一段时间的练习。找到答案后，更多的疑问出现了。我必须生成一个无限的列表列表，从作为输入给出的字母表开始（也称为 kleene 闭包）。该函数定义如下：
kleene :: [a] -> [[a]]
kleene xs = []:[kle++[x] | kle <- kleene xs, x <- xs]
它有效，但我似乎不明白它是如何工作的（我认为这是练习的要点）。根据我对列表理解的理解，我获取第一个列表的第一个元素（此处kleene xs），然后遍历第二个列表的元素（xs）。此示例显示了 kleene 闭包的前 20 个元素。
> take 20 $ kleene [1,2,3]
> [[],[1],[2],[3],[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3],[1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3],[1,3,1]]
现在，这是怎么回事？为什么对此的评价没有失控？是否是因为惰性评估，如果不需要的话，可以继续进行而无需真正计算？如果我尝试替换并计算表达式，我就会陷入循环：
[[],[kleene [1,2,3],1],[kleene [1,2,3],2],[kleene [1,2,3],3],[kleene [1,2,3],...]
为了计算 kleene，我必须无限地计算它。在第一行，一旦我解决了 kleene 我得到
[[],[[],kleene [1,2,3],1,1],[[], kleene [1,2,3],1,2],[[], kleene [1,2,3],1,3],...]
但这样它就应该永远持续下去。为什么我得到的输出逐渐变大，而不是无限大的元素？是不是因为惰性求值，每次递归调用都算作链表的一个元素，导致下一个元素 of只是后续的递归调用，而每次都kle携带 的元素？xs有人可以帮助我理解这一点吗？
懒惰评估被认为是一种延迟流程直到第一次需要的方式.这往往会避免重复评估,这就是为什么我认为这样做的速度要快得多.像Haskell(和JavaScript ..？)这样的函数语言内置了这个功能.
但是,我不明白为什么和为什么其他"正常"方法(即相同的功能但不使用惰性评估)更慢..这些其他方法如何以及为什么重复进行评估？有人可以通过提供简单的例子并解释每种方法的机制来详细说明这一点吗？
另外,根据Wikipedia关于懒惰评估的页面,这些被认为是这种方法的优点:
但是,我们可以控制所需的计算并避免重复相同的计算吗？(1)我们可以使用ie链接列表来创建无限数据结构(2)我们可以做(3)已经.. ??? 我们可以定义类/模板/对象并使用它们而不是原语(即JavaScript).
另外,在我看来(至少从我见过的案例中),懒惰的评估与递归和使用"头部"和"尾部"(以及其他)概念密切相关.当然,有些情况下递归是有用的,但懒惰的评价不仅仅是......？不仅仅是一种解决问题的递归方法..？Streamjs是一个JavaScript库,它使用递归和一些其他简单的操作(头部,尾部等)来执行惰性求值.
看来我无法理解它...
在此先感谢任何贡献.
recursion performance haskell lazy-evaluation lazy-initialization
嗨,我需要将我的F#代码更改为Haskell代码,但我在Haskell中是如此新,我不能这样我的代码只是从键盘读取数据,如果数据不是整数返回错误消息然后计算n斐波纳契数然后写入list之后将列表写入txt文件这是我的代码
open System
let rec fib n =
match n with
|0->0
|1->1
|2->1
|n->fib(n-1)+fib(n-2);;
let printFibonacci list =
for i=0 to (List.length list)-1 do
printf "%d " (list.Item(i));;
let writeToFile list =
let file = System.IO.File.Create("C:\out2.txt")
let mutable s =""
let writer = new System.IO.StreamWriter(file)
try
for i=0 to (List.length list)-1 do
s <- list.Item(i).ToString()
writer.Write(s+" ")
finally
writer.Close()
file.Dispose()
printfn "Writed To File"
let mutable control = true
let mutable num = 0
while control do
try
printfn …我有一个代码,用于计算Motzkin数字:
module Main where
-- Program execution begins here
main :: IO ()
main = interact (unlines . (map show) . map wave . (map read) . words)
-- Compute Motzkin number
wave :: Integer -> Integer
wave 0 = 1
wave 1 = 1
wave n = ((3 * n - 3) * wave (n - 2) + (2 * n + 1) * wave (n - 1)) `div` (n + 2)
但即使是简单数字的输出也30需要一段时间才能返回.
任何优化的想法？
尽管可以使用此线程，但是由于答案的不同，我不允许在答案下问我的问题，因此我不得不为此创建一个新问题。（我只是stackoverflow中的新手：）
关于以下fib功能如何工作，我并不清楚
fibs :: [Integer]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
nichijou逐步解释了我从nichijou引用的以下线程：
首先，我们使用fib和tail fib可以得到第3个：
Run Code Online (Sandbox Code Playgroud)fibs : [1, 1, ? tail fibs : [1, ? zipWith (+) fibs (tail fibs): [2, ?现在，我们知道第三个是2，我们可以得到第四个：
Run Code Online (Sandbox Code Playgroud)fibs : [1, 1, 2, ? tail fibs : [1, 2, ? zipWith (+) fibs (tail fibs): [2, 3, ?现在的第五名：
Run Code Online (Sandbox Code Playgroud)fibs : [1, 1, 2, 3, ? tail fibs : [1, 2, 3, ? zipWith (+) fibs (tail fibs): [2, …