Подсчет числа рекурсий

Question

У меня есть код, который аппроксимирует решение взамен, то, что он на самом деле делает, не имеет значения, но он работает в направлении r '== rt, изменяя мг (предположим, начиная с 4.0, потому что я «знаю», которые должны быть в шаге).

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) 

То, что я хотел бы быть в состоянии сделать это подсчитать количество циклов, я знаю, что правильный способ сделать это с государством монады, но то, что это самый элегантный способ, чтобы соответствовать пут/получить в такую ​​функцию? Сделать f 'блок блокировки? Или просто добавить счетчик solve_m 'и return (counter, mg)?

Спасибо!

Edit: Это, кажется, в основном то, что я хочу, и не Монады необходимые:

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) 

Тем не менее выглядит немного грязный (повторяющийся код), но я буду убирать это ... Это становится мне приемлемые результаты в 1/10000-й итерации кода, который он заменит!

Answer 1

Не смотря на свой алгоритм, общий способ сделать это разделить ваши критерии терминации от итеративного алгоритма:

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

затем использовать либо итерацию и 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 

или разворачиваться :

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

EDIT: также обратите внимание, что эти два промежуточных продукта немного отличаются друг от друга nt в том, что первый поддерживает базовый регистр (вход a, следовательно, - 1), в то время как второй не имеет и, следовательно, будет иметь незначительную разницу в дополнительном resultAndRecursions.

Answer 2

Ну, во-первых, вы можете удалить большинство аргументов до solve_m': они не меняются в рекурсивных вызовах, а аргументы solve_m могут быть указаны в разделе where. Это также делает ненужной функцию f'.

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

Теперь solve_m' имеет тип Double -> Double, потому что все это делает выполнение следующей итерации, а затем либо закончить или называть себя хвостом рекурсивно. Как обычно, стандартные библиотеки включают в себя функцию с именем iterate с типом (a -> a) -> a -> [a], которая принимает такую ​​функцию, а создает (возможно, бесконечный) список каждого шага итерации. Количество требуемых рекурсивных вызовов - это, конечно, точно длина результирующего списка. вызывает смущающую ошибку в моем ответе.

Что действительно делает iterate, это бесконечный список, в этом случае с бесконечно повторяющимися копиями «окончательного» результата. Не совсем то, что вы хотите. Вероятно, я думал о unfoldr :: (b -> Maybe (a, b)) -> b -> [a].

Другой вариант, который я на самом деле предпочитаю, - удалить защитный элемент, который проверяет, что ответ достаточно близко, и в конце концов использовать iterate, создавая бесконечный список новых приближений, затем уничтожайте полученный список, сравнивающий смежные чтобы увидеть, как близко вы добираетесь. Я бы привел примерный код, но с учетом более ранней ошибки, которая может быть неразумной.

EDIT: Хорошо, для полноты картины, вот пару быстрых примеров:

Использование iterate и takeWhile:

solve_m_iter f ar st qt = takeWhile notDoneYet $ iterate nextApprox 4.0 
    where rd mg = st + qt - f st ar mg 
     notDoneYet mg = abs (rd mg) > precis 
     nextApprox mg | rd mg > precis = mg - abs (rd mg) 
         | rd mg < -precis = mg + abs (rd mg) 

Использование unfoldr:

solve_m_unfold f ar st qt = unfoldr nextApprox 
    where nextApprox mg | rd > precis = keep $ mg - abs rd 
         | rd < -precis = keep $ mg + abs rd 
         | otherwise = Nothing 
      where rd = st + qt - f st ar mg 
        keep x = Just (x, x) 

И еще немного лучше, чтобы получить результат без прохождения списка twi ce:

getResult = foldl (\(n, _) x -> (n + 1, x)) (0, 4.0) 

Определенно быстрый и грязный код, но, надеюсь, полезно.