無法找到我的Haskell程序中的錯誤（Puler＃2來自Project Euler）

Question

SPOILER ALERT：如果您正在嘗試解決Project Euler的問題＃2，請不要看這個問題＃2 。

我已經完成problem #2 of Project Euler (computing the sum of all even Fibonacci(n) numbers less than or equal to 4 million) - 我正在使用這些問題來練習我的C/Ada技能，重新訪問我的Common Lisp並學習Haskell。

當我試圖在Haskell中重新實現我的解決方案時，我遇到了一個問題。在古典方式中，它正在計算錯誤的答案。但是，我認爲我的Haskell實現類似於我的Common Lisp實現（它確實產生了正確的結果）。

該算法僅計算n的斐波那契數，其中n % 3 == 0。這是因爲

1. 我們需要總結僅偶數值斐波那契數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程序中缺少的內容。錯誤在哪裏，還是我錯過了一個非常具體的Haskell特質評估/模式匹配的東西？謝謝。

Answer 1

你有一個錯字

uber_bound = 40000000 

當它應該是

uber_bound = 4000000 

---

僅供參考，更地道的解決辦法是將產生的所有Fibonacci數列表（懶惰評估對此非常有用），然後使用takeWhile,filter和sum。

這也會更有效率，因爲尾遞歸在Haskell中很少有用（懶惰評估妨礙了），並且由於列表元素是共享的（如果列表被適當定義），每個斐波那契數被計算恰好一次。

Answer 2

刪除，不應該給一個擾流板。 dbaupp的建議很好。使用zipWith有一個衆所周知的表達式，但我認爲它太聰明瞭 - 有更直接的方法。