[ACCEPTED]-Basic summation in Haskell-recursion

Accepted answer
Score: 10

You wrap it.

summation :: Integer -> Integer -> Integer
summation x y = summation' x y 0

summation' :: Integer -> Integer -> Integer -> Integer
summation' x y sum =
    if (y<x) then
        summation' x (y-1) (sum+y)


Score: 10

The quick answer:

One simple way would be to use the sum function 35 from Data.List.

Then you could simply say:

summation x y = sum [x .. y]

This solution 34 assumes that x is less than y, and you could 33 fix this by saying:

summation x y = sum [min x y .. max x y]

Defining sum:

Since you are learning 32 Haskell, it might be important to know how 31 sum works, instead of just knowing it exists. For 30 me, the biggest hurdle to get over initially 29 was writing too many functions that already 28 existed; especially since I didn't know 27 how to write them effectively.

Hoogle is a great 26 help in this regard: it's a search engine 25 that allows you to seach for Haskell functions. It's 24 a great thing for productivity, because 23 you'll be able to spend time working on 22 your problem, instead of producing poor 21 rewrites of half of the prelude. It's also 20 great for learning, because there are links 19 to the source code of most of the functions 18 on Hackage. The source code of the Prelude and other 17 "fundamental" libraries such as 16 Data.List is surprisingly accessible to a beginner, and 15 will provide a lot of insight into how "the 14 smart kids" do things.

The :browse command 13 in GHCI is something that I found out about 12 recently that I wish I'd discovered sooner.

Anyway, one 11 way of defining sum is by using a fold:

sum xs y = foldl (+) 0 xs

Or the 10 equivalent in "pointless" style:

sum = foldl (+) 0

I usually prefer the first 9 formulation, but knowing how and why the 8 second one works will help you a lot in 7 your journey.

Further Reading:

You'll notice that I used the 6 function foldl. This function "folds" an 5 input list. To "master" functional 4 programming, knowing how to fold is both one 3 of the most basic and important concepts. A 2 good resource to consult is the page on folds from the 1 Haskell Wiki.

Score: 4

You could do it like Gauss did.

summation begin end
    | end < begin = summation end begin
    | otherwise   = n * (2*a + (n-1)*d) `div` 2
  where a = begin
        d = 1
        n = end - begin + 1

Code is a 2 blatantly literal translation from http://mathcentral.uregina.ca/QQ/database/QQ.02.06/jo1.html (a little 1 ways down that page: S = n[2a + (n-1)d]/2)

More Related questions