无法在我的Haskell程序中找到bug (来自Project的难题#2 )

Question

扰流警告:如果您试图在自己的w/o上解决Project的问题#2，请不要看这个问题。

我已经完成了项目Euler的问题2(计算所有偶数Fibonacci(n)数小于或等于400万的和) -我正在使用这些问题来练习我的C/Ada技能，重新访问我的Common和学习Haskell。

当我试图在Haskell重新实现我的解决方案时，我遇到了一个问题。以经典的方式，它正在计算错误的答案。但是，我认为我的Haskell实现类似于我的Common (它确实产生了正确的结果)。

该算法只计算n个n % 3 == 0的Fibonacci数。这是因为

1. 我们只需要求和偶数Fibonacci数F(n) <= 4M，并且
2. (n %3 == 0) <-> (F(n) %2 == 0)

下面是Haskell实现：

uber_bound      = 40000000  -- Upper bound (exclusive) for fibonacci values
expected        = 4613732   -- the correct answer

-- The implementation amenable for tail-recursion optimization
fibonacci :: Int -> Int
fibonacci n = __fibs (abs n) 0 1
  where
    -- The auxiliary, tail-recursive fibs function
    __fibs    :: Int -> Int -> Int -> Int
    __fibs 0 f1 f2 = f1 -- the stopping case
    __fibs n f1 f2 = __fibs (n - 1) f2 (f1 + f2)

-- NOT working. It computes 19544084 when it should compute 4613732
find_solution :: Int
find_solution = sum_fibs 0
  where
    sum_fibs :: Int -> Int
    sum_fibs n = 
      if fibs > uber_bound
        then
          0 -- stopping condition
        else
          -- remember, (n % 3 == 0) <--> (fib(n) % 2 == 0)
          -- so, seek the next even fibs by looking at the
          -- the next n = n@pre + 3
          fibs + sum_fibs (n + 3)
      where
        fibs = fibonacci n

actual = find_solution

problem_2 = (expected == actual)

如果正确的答案是19544084，则打印4613732。我的通用Lisp解决方案(，它可以工作)如下所示。

我以为我的Haskell实现会类似于它，但我遗漏了一些东西。

(set `expected 4613732)  ;; the correct answer

;; tail-recursive fibonacci
(defun fibonacci (n)
  (labels 
    ( ;; define an auxiliary fibs for tail recursion optimization
      (__fibs (n f1 f2)
        (if (<= n 0)
          f1 ;; the stopping condition
          (__fibs 
            (- n 1) ;; decrement to ensure a stopping condition 
            f2 
            (+ f1 f2))))
    ) ;; end tail_rec_fibs auxiliary
   (__fibs n 0 1)
  );; end labels
) ;; end fibonacci

(defun sum_fibs(seed)
  (let*
    ((f (fibonacci seed)))
    (if (> f 4000000)
      0
    ;; else
      (+ f (sum_fibs (+ 3 seed)))
    );; end if
  );; end of let
);; end of sum-fibs

(defun solution () (sum_fibs 0))

(defun problem_2 ()
  (let
    (
     (actual (solution))
    )
    (format t "expected:~d actual:~d" expected actual)
    (= expected actual)
  )
) ;; end of problem_2 defun

我到底做错了什么？认为我正在使用尼安德特人的方法来学习Haskell (我目前只是在Haskell上重新实现我的Lisp，而不是学习与语言相匹配的编码/问题解决方法Haskell )。

我不是在找人给我一个解决方案(这不是我能得到的吗？)我正在寻找更多，但更多的解释，我错过了在我的Haskell程序。bug在哪里，还是我缺少了一个非常具体的Haskell特性评估/模式匹配的东西？谢谢。

Answer 1

你有个打字错误

uber_bound = 40000000

当它应该是

uber_bound = 4000000

仅供参考，一个更惯用的解决方案是生成所有Fibonacci数的列表(惰性计算对此非常有用)，然后使用takeWhile、filter和sum。

这也会更有效，因为尾递归在Haskell中很少有帮助(懒散的计算妨碍了)，而且由于列表的元素是共享的(如果列表定义适当的话)，每个Fibonacci数精确地计算一次。

Answer 2

删除了，不应该给扰流器。dbaupp的建议很好。有一个众所周知的使用zipWith的表达式，但我认为它太聪明了--有更直接的方法。