计算递归的数量 [英] Counting the number of recursions

问题描述

我有一些代码接近解决方案recusively，它实际上做什么并不重要，但它通过改变mg（m猜测，从4.0开始，因为我知道应该是在r'== rt球场）。

  solve_m f st st qt = solve_m'f ar st qt 4.0 
 where 
 solve_m'f ar st qt mg 
 | rd> precis = f'（mg  -  sf）
 | rd< （-precis）= f'（mg + sf）
 |否则= mg 
其中
 f'= solve_m'f st st qt 
 rt = st + qt 
 r'= f st ar mg 
 rd = rt  -  r '
 sf = abs（rd）
  

我希望能够做的是计算周期数，我知道正确的方法是使用State Monad，但是最适合这种功能的最佳方法是什么？让f'做一个块？或者只是添加一个计数器solve_m'并返回（counter，mg）？

谢谢！

编辑：这似乎基本上是我想要的，并且不需要Monads：

  solve_m f st st qt =（last（series ），长度（系列））
其中
 series = takeWhile termPred（iterate solve_m'4.0）
 termPred m'=（abs（rt  - （f st ar m'）））> precis 
 rt = st + qt 
 solve_m'mg 
 | rt> r'=（mg  -  sf）
 | rt< r'=（mg + sf）
其中
 r'= f st ar mg 
 rd = rt -r'
 sf = abs（rd）
  

仍然看起来有点乱（重复的代码），但我会整理它...这让我可以接受的结果在1 / 10000th的代码迭代它将取代！


解决方案

没有看你的算法，通用的做法是从迭代算法中划分出终止条件：



  terminatePred :: a  - > Bool 
 algorithm :: a  - > a 
  

然后使用iterate和takeWhile：

  itermediates = takeWhile（not。terminationPred）。迭代算法
 resultAndRecursions :: a  - > （a，Int）
 resultAndRecursions a =（last（中间体a），length（中间体a） -  1）
  - 你想在这里创建自己的安全函数，而不是使用last和length 
  

或展开：



  intermediates = unfoldr op 
其中
 op a | terminatePred a = Nothing 
 | （a'，a'）
  



编辑：也注意到这两个中间体略有不同，第一个维护基本情况（输入 a ，因此 - 1 ），而第二个则不会，因此在补充 resultAndRecursions 中会有细微差别。

I have some code that approximates a solution recusively, what it actually does is not important, but it works towards r' == rt by varying mg (m guess, starting with 4.0 because I "know" that ought to be in the ballpark).

solve_m f ar st qt = solve_m' f ar st qt 4.0
  where
    solve_m' f ar st qt mg 
      | rd > precis    = f' (mg - sf)  
      | rd < (-precis) = f' (mg + sf)  
      | otherwise = mg
        where 
          f' = solve_m' f ar st qt
          rt = st + qt   
          r' = f st ar mg 
          rd = rt - r'    
          sf = abs(rd) 

What I would like to be able to do is count the number of cycles, I know the right way to do this is with the State monad, but what is the most elegant way to fit the put/get into a function like this? Make f' a do block? Or is it simply to add a counter solve_m' and return (counter, mg)?

Thanks!

Edit: This seems to be basically what I want, and no Monads necessary:

solve_m f ar st qt = (last (series), length(series))
  where
  series = takeWhile termPred (iterate solve_m' 4.0)
  termPred m' = (abs (rt - (f st ar m'))) > precis
  rt = st + qt   
  solve_m' mg 
    | rt > r' = (mg - sf)  
    | rt < r' = (mg + sf)  
      where
        r' = f st ar mg 
        rd = rt - r' 
        sf = abs(rd)

Still looks a little messy (repeated code) but I'll tidy it up... This is getting me acceptable results in 1/10000th of the iterations of the code it will replace!

解决方案

Without looking at your algorithm, the generic way to do this is divide up your termination criteria from the iterative algorithm:

terminationPred :: a -> Bool
algorithm :: a -> a

then use either iterate and takeWhile:

itermediates = takeWhile (not . terminationPred) . iterate algorithm
resultAndRecursions :: a -> (a, Int)
resultAndRecursions a = (last (intermediates a), length (intermediates a) - 1)
-- you'd want to make your own safe function here, not use last and length

or unfold:

intermediates = unfoldr op
  where
  op a | terminationPred a = Nothing
       | otherwise = let a' = algorithm a
                     in Just (a', a')

EDIT: also notice these two intermediates are slightly different in that the first maintains the base case (the input a, hence the - 1) while the second does not and thus would have a minor difference in the complementary resultAndRecursions.

这篇关于计算递归的数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！