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

我知道这太可怕了.写这个的最好和最直观的方法是什么？

回复:谢谢你的精彩答案!使用修复功能的那个似乎是我机器中最快的(Redhat 6.4 64bit/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,我想我们只需要计算高达150,000,000的术语![f(n)=\frac_ {3n ^ 2 + 5n} ^ {4n ^ 2 + 12n + 8}].我使用Integer而不是Int,但它也没有帮助.如果我将阈值设置为大于0.7499999936264,有什么理由不能完成......？

Answer 1

我喜欢在这种情况下倒退:

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(使用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 2

本质上是显式的递归,但我喜欢这样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 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中编写命令式代码.

它只会导致非惯用的Haskell,它不像原始代码那样难以读取或写入.毕竟,callCC朋友之间有一两个什么？:-P