如何在Haskell中實現帶條件休息的循環

Question

我想找出滿足的第一個n。如果我使用另一種語言（如c/C++），這是一件簡單而容易的事情，但我不知道如何在Haskell中實現它。

#include <iostream> 
long double term(int k) { return 1.0/(k*k+2.0*k); } 
int main() { 
    long double total = 0.0; 
    for (int k=1;;k++) { 
     total += term(k); 
     if (total>=2.99/4.0) { 
      std::cout << k << std::endl; 
      break; 
     } 
    } 
    return 0; 
} 

我用dropWhile和一個有序列表，並拿1拿起第一個。

term k = 1.0/(k*k+2.0*k) 
termSum n = sum $ take n $ map term [1..] 
main = do 
    let [(n,val)] = take 1 $ dropWhile (\(a,b)->b <= 2.99/4.0) $ map (\n->(n,termSum n)) [1..] 
    print n 

我知道這太可怕了。什麼是最好的和直觀的方式來寫這個？

回覆： 謝謝你的好評！使用修復功能的一個似乎是在我的機器最快（紅帽6.4 64/80GB存儲器）

方法＃0取1和dropWhile（我的最初的實施），使用修復功能

threshold=0.74999   n=99999  time=52.167 sec 

方法＃1

threshold=0.74999   n=99999  time=0.005 sec 
threshold=0.74999999  n=101554197 time=1.077 sec 
threshold=0.7499999936263 n=134217004 time=1.407 sec 

方法＃2向後工作

threshold=0.74999   n=99999  time=0.026 sec 
threshold=0.74999999  n=101554197 time=21.523 sec 
threshold=0.7499999936263 n=134217004 time=25.247 sec 

方法＃3勢在必行方式

threshold=0.74999   n=99999  time=0.008 sec 
threshold=0.74999999  n=101554197 time=2.460 sec 
threshold=0.7499999936263 n=134217004 time=3.254 sec 

RERE： 我注意到，無論執行我使用（修復，勢在必行的方式，或遞歸的方式），如果閾值比0.7499999936264大......它永遠不會結束..爲了讓F（N）大於0.7499999936264，我認爲自從！[f（n）= \ frac_ {3n^2 + 5n}^{4n^2 + 12n + 8}]之後，我們只需計算高達150,000,000的項。我用Integer代替Int，但它也沒有幫助。如果我將閾值設置爲大於0.7499999936264 ...，是否有任何原因尚未完成？

Answer 1

本質上明確的遞歸，但我喜歡fix像這樣的循環：

import Data.Function (fix) 

term k = 1.0/(k*k+2.0*k) 

main = print $ fix (\f total k -> 
         let new = total + term k 
         in if new >= 2.99/4.0 then k else f new (k+1) 
        ) 0 1 

Answer 2

我喜歡這些種類的情況下，反向工作：

main = print k where 
    k = 1 + length (takeWhile (< (2.99/4)) partialSums) 
    partialSums = scanl1 (+) terms 
    terms = [ 1.0/(k*k+2.0*k) | k <- [1..] ] 

這是如何工作的：

terms是一個無限的名單，但由於Haskell是惰性的，我們只計算儘可能多的每學期，我們要求：

λ terms = [ 1.0/(k*k+2.0*k) | k <- [1..] ] :: [Double] 
λ take 5 terms 
[0.3333333333333333,0.125,6.666666666666667e-2,4.1666666666666664e-2,2.857142857142857e-2] 
λ :p terms 
terms = 0.3333333333333333 : 0.125 : 6.666666666666667e-2 : 
     4.1666666666666664e-2 : 2.857142857142857e-2 : (_t5::[Double]) 

partialSums是另一種無限的名單的基礎上，terms內容（全光照g scanl1）。它讓我們分期償還，你計算termSum工作：

λ partialSums = scanl1 (+) terms 
λ take 5 partialSums 
[0.3333333333333333,0.4583333333333333,0.525,0.5666666666666667,0.5952380952380952] 

的takeWhile (< (2.99/4))然後確定partialSums多少而言，我們需要生成，從而的 terms多少而言，我們需要生成：

λ length (takeWhile (< (2.99/4)) partialSums) 
398 

如果我們檢查，我們可以看到第398個terms的總和小於2.99/4，但是第399個碰到它：

λ sum (take 398 terms) < 2.99/4 
True 
λ sum (take 399 terms) < 2.99/4 
False 

，或等效的第397部分和（從0指數）低於目標，而且398是不是：

λ partialSums !! 397 < 2.99/4 
True 
λ partialSums !! 398 < 2.99/4 
False 

Answer 3

這是一個簡單和容易的東西，如果我用另一種語言，如C/C++

那麼，讓我們以同樣的方式來做吧。

import Prelude hiding (break) 
import Data.IORef 
import Control.Monad.Cont 
import Data.Foldable 
import Control.Monad (when) 

-- long double term(int k) { return 1.0/(k*k+2.0*k); } 
term :: Int -> Double 
term k = 1.0/(k'*k'+2.0*k') 
    where k' = fromIntegral k 

-- int main() { 
main :: IO() 
main = flip runContT return $ do 
    -- long double total = 0.0; 
    total <- lift $ newIORef (0.0 :: Double) 
    -- for (int k=1;;k++) { 
    callCC $ \break -> 
     for_ [1..] $ \k -> do 
     -- total += term(k); 
     lift $ modifyIORef total (+ term k) 
     -- if (total>=2.99/4.0) { 
     totalV <- lift $ readIORef total 
     when (totalV >= 2.99/4.0) $ do 
      -- std::cout << k << std::endl; 
      lift $ print k 
      -- break; 
      break() 

是的，以上是比一個嚴肅的答案更開玩笑。儘管如此，至少在理論上，很高興看到它可以在Haskell中編寫命令式代碼。

它只是導致非慣用的哈斯克爾，這是沒有比原來的代碼更難讀寫。畢竟，什麼是callCC或兩個朋友之間？ :-P