如何在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