суммы квадратов целых чисел Haskell

Question

У меня есть этот код, чтобы отработать сумму квадратов целых чисел в диапазоне от т: п

sumsquares :: Integral a=> Int -> Int -> Int -> Int 
sumsquares m n middle 
| m > n = error "First number cannot be bigger than second number" 
|m==n = m*m 
|otherwise = m*m + sumsquares (m+1)n 

Как бы я переопределить функцию sumsquares для этой цели?

Если в диапазоне m: n находится более одного числа, вычислите середину диапазона и добавьте сумму квадратов (m: средняя) к сумме квадратов (средний + 1: n), , в противном случае существует только одно число в диапазоне m: n, поэтому m = = n, а решение - только квадрат m. (Обратите внимание, что при таком подходе рекурсия объединяет два полурешения: каждая подзадача примерно вдвое меньше общей проблемы).

Answer 1

В вашей первоначальной функции ограничение класса Integral a в сигнатуре типа устарело (a не упоминается нигде в подписи, не так ли?). Кроме того, третий параметр функции (middle) остается неиспользованным. Таким образом, вы могли бы написать как

sumsquares :: Int -> Int -> Int 
sumsquares m n 
    | m > n  = error "First number cannot be bigger than second number" 
    | m == n = m * m 
    | otherwise = m * m + sumsquares (m + 1) n 

Переписывая его, чтобы перейти от decrease-and-conquer схемы строгой схемы разделяй и властвуй, то просто включает в себя адаптацию рекурсивный случай соответственно:

sumsquares :: Int -> Int -> Int 
sumsquares m n 
    | m > n  = error "First number cannot be bigger than second number" 
    | m == n = m * m 
    | otherwise = let middle = (m + n) `div` 2 
       in sumsquares m middle + sumsquares (middle + 1) n 

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