相关疑难解决方法(0)

我正在学习Haskell,并且遇到了以下代码:

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

就其工作方式而言,我在解析方面遇到了一些麻烦.它非常整洁,我知道不需要更多内容,但我想了解Haskell在写作时如何设法"填写"文件:

take 50 fibs

有帮助吗？

谢谢!

我在浏览Erlang编译器源时遇到了这个问题.

我不是真的得到它.(去图;)),考虑到我刚刚意识到5分钟前有这样的事情).

请原谅我先问一下,不要先试着理解它存在的原因.

有关于它的维基百科文章,但它非常神秘.

嗨,我正在从Memoization看这个例子:

memoized_fib :: Int -> Integer
memoized_fib = (map fib [0 ..] !!)
    where fib 0 = 0
          fib 1 = 1
          fib n = memoized_fib (n-2) + memoized_fib (n-1)

我只是想知道为什么这甚至可以工作,因为对我来说,如果你打电话,memoized_fib(n-2)那么你正在"创建"一个新列表并用它做事情,在你从它返回后,包含部分结果的列表将会消失？所以memorized_fib(n-1)不会从中受益吗？

为了理解和利用GHC自动记忆，我碰壁了：当纯函数以诸如的固定值调用时fib 42，它们有时又快又慢。如果fib 42通过数学简单地或隐式地调用它们，则它们会有所不同(\x -> fib (x - 1)) 43。这些案件似乎没有押韵或理由，因此我将向他们提出这些案件的目的是询问行为背后的逻辑是什么。

考虑一个慢速的斐波那契实现，这使备忘录有效时显而易见：

slow_fib :: Int -> Integer
slow_fib n = if n < 2 then 1 else (slow_fib (n - 1)) + (slow_fib (n - 2))

我测试了三个基本问题，以查看GHC（8.2.2版）是否可以使用固定参数来记录调用：

1. 可以slow_fib访问以前的顶级通话slow_fib吗？
2. 是否为以后的非平凡（例如数学）顶级表达式记忆了以前的结果？
3. 是否为以后相同的顶级表达式记忆了以前的结果？

答案似乎是：

1. 没有
2. 没有
3. 是[??]

最后一种情况有效的事实令我感到困惑：例如，如果我可以重印结果，那么我应该希望能够添加它们。这是显示此代码的代码：

main = do
  -- 1. all three of these are slow, even though `slow_fib 37` is 
  -- just the sum of the other two results. Definitely no …

下面的两个Haskell函数似乎不同,索引变量是隐式还是显式,但性能差异是两个数量级.

此函数大约需要0.03秒来计算mfib 30:

let mfib = (map fib [0..] !!)
  where
    fib 0 = 0
    fib 1 = 1
    fib x = mfib (x-1) + mfib (x-2)

对于mfib 30,此功能大约需要3秒钟:

let mfib i = map fib [0..] !! i
  where
    fib 0 = 0
    fib 1 = 1
    fib x = mfib (x-1) + mfib (x-2)

我猜它与GHC内联规则有关,并且一直在尝试添加内联/无内置编译指示以获得匹配的性能.

编辑:我理解如何查找惰性列表可以用来记忆fib函数以及为什么传统的fib定义非常慢.我期待memoization在第二个函数以及第一个函数中工作,并且不理解为什么它不是.

通过阅读和解决Project Euler问题,我是编程和学习Haskell的新手.当然,改善这些问题的性能最重要的是使用更好的算法.但是,我很清楚,还有其他简单易行的方法可以提高性能.粗略搜索提出了这个问题,这个问题给出了以下提示:

• 使用ghc标志-O2和-fllvm.
• 使用Int类型而不是Integer类型,因为它是未装箱的(甚至是Integer而不是Int64).这需要键入函数,而不是让编译器即时决定.
• 使用rem而不是mod进行分区测试.
• 适当时使用Schwartzian变换.
• 在递归函数中使用累加器(尾递归优化,我相信).
• 记忆(？)

(一个答案也提到了工人/包装器转换,但这看起来相当先进.)

问题:在Haskell中可以进行哪些其他简单的优化来提高Project Euler风格问题的性能？是否有任何其他Haskell特定的(或特定于函数编程的？)想法或特性可用于帮助加速Project Euler问题的解决方案？相反,应该注意什么？什么是常见但低效的事情要避免？

我是Haskell的新手,我正试图以流处理方式实现Euler的Sieve.

当我查看关于素数的Haskell Wiki页面时,我发现了一些神秘的流优化技术.在3.8维基的线性合并中:

primesLME = 2 : ([3,5..] `minus` joinL [[p*p, p*p+2*p..] | p <- primes']) 
  where
    primes' = 3 : ([5,7..] `minus` joinL [[p*p, p*p+2*p..] | p <- primes'])

joinL ((x:xs):t) = x : union xs (joinL t)

它说

" 根据Melissa O'Neill的代码,这里引入了双素数反馈,以防止不必要的记忆,从而防止内存泄漏."

怎么会这样？我无法弄清楚它是如何工作的.

在我正在进行的功能编程课程的当前练习作业中,我们必须制作一个给定函数的memoized版本.为了解释memoization,给出了以下示例:

fiblist = [ fibm x | x <- [0..]]

fibm 0 = 0
fibm 1 = 1
fibm n = fiblist !! (n-1) + fiblist !! (n-2)

但我不完全了解这是如何工作的.

我们打电话吧fibm 3.

fibm 3
--> fiblist !! 2 + fibList 1
--> [fibm 0, fibm 1, fibm 2] !! 2 + [fibm 0, fibm 1] !! 1
--> fibm 2 + fibm 1
--> (fiblist !! 1 + fiblist 0) + 1
--> ([fibm 0, fibm 1] !! 1 …

在阅读了memoization介绍之后,我通过使用更通用的memoize函数重新实现了Fibonacci示例(仅用于学习目的):

memoizer :: (Int -> Integer) -> Int -> Integer
memoizer f = (map f [0 ..] !!)

memoized_fib :: Int -> Integer
memoized_fib = memoizer fib
    where fib 0 = 0
          fib 1 = 1
          fib n = memoized_fib (n-2) + memoized_fib (n-1)

这有效,但是当我将最后一行更改为以下代码时,memoization突然无法正常工作(程序再次变慢):

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

记忆化的关键区别在哪里？

我试图了解有关 Haskell 函数的一些内容。

首先，这是一个以典型的“慢”方式定义的斐波那契函数（即没有记忆的递归，也没有无限列表技巧）

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

接下来，相同的规范记忆版本。（仅与教程/书籍/等中的典型示例略有不同，因为我更喜欢!!运算符的前缀版本。）

memfib = (!!) (map fib [0..])
  where
    fib 0 = 0
    fib 1 = 1
    fib k = memfib(k-2) + memfib(k-1)

上面的解决方案使用了!!运算符的部分应用，这是有道理的：我们希望memfib最终成为一个带参数的函数，并且我们正在定义它而不在定义中包含参数。

到现在为止还挺好。现在，我想我可以编写一个等效的记忆函数，在定义中包含一个参数，所以我这样做了：

memfib_wparam n = ((!!) (map fib [0..])) n
  where
    fib 0 = 0
    fib 1 = 1
    fib k = memfib_wparam(k-2) + memfib_wparam(k-1) …