Haskell take sum recursively

Question

Hello I want to take a sum of functions call in Haskel but I cannot figure out what I am doing wrong. To be more specific, I have a function f(a,b,c)=a+b+c and I want to take an int like this:

x=Sum( from i=0 to i=c) f(1,1,i)

so far I have written this, but it doesn't even compile. Can you help me?

f a b c = a+b+c

my_sum f a b c+1 =f a b c+1 + my_sum f a b c

I get parse error in pattern my_sum

eg for my_sum f 1 1 5 the result would be f(1,1,5)+f(1,1,4)+f(1,1,3)+f(1,1,2)+f(1,1,1)

I dont want to use lists

your example corresponds to `Sum( from i=1 to i=c) f(1,1,i)`, not `i=0`. — Will Ness, Mar 16 '14 at 08:34

score 2 · Answer 1 · answered Mar 12 '14 at 13:52

n+k patterns are bad

Your code:

my_sum f a b c+1 =f a b c+1 + my_sum f a b c

includes a pattern in the form c+1 which A) should have parentheses B) Needs a base case (I assume you want to stop when c == 0) and C) is a syntactic form that has been removed from the language.

Instead, explicitly subtract 1 from c when you want and be sure to handle the base case:

my_sum f a b 0 = f a b 0
my_sum f a b n = f a b n + my_sum f a b (n-1)

This also has a memory leak meaning it will build up a large computation in the form f1 + (f a b n' + (f a b n'' + (f a b n''' + (.... You can handle the leak by using an accumulator or a higher level function and optimization at compile-time.

A cleaner Solution

List comprehension strikes me as the most reasonable solution here:

sum [f a b i | i <- [0..c] ]

The sum of the function f applied to arugments a, b and finally i where i ranges from 0 to c inclusively.

Because it's too easy and I dont care about doing it efficiently. I am more interested in learning how to use recursion — JmRag, Mar 13 '14 at 18:28

bheklilr · Accepted Answer · 2014-03-12T13:53:51.600

You can't have the c+1 on the left side of a definition. Since you're just summing, it doesn't matter if you count up from 0 to c or count down from c to 0, so you could instead do

my_sum f a b 0 = f a b 0
my_sum f a b c = f a b c + my_sum f a b (c - 1)

Then you could use it as

> let g x y z = x + y + z
> my_sum g 0 0 10
55

Some more detail on why your code failed to compile: Whenever you have a pattern on the left side of a definition, such as

fib 0 = 1
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

You can only match on constructors, names (like n or c), and literals (which are essentially constructors for the basic types). The function + is not a constructor, it is a function belonging to the Num typeclass, so therefore you can not pattern match on it. You may be confused from seeing list pattern matching before because it uses an operator:

myListSum [] = 0
myListSum (x:xs) = x + myListSum xs

but in fact, : is the Cons constructor for lists, and [] is the empty list constructor. You can think of the list type defined as

data [a] = [] | a : [a]

Or, if you were to replace all the symbols with words

data List a = Empty | Cons a (List a)

although its a bit different in reality since there's more that goes into defining lists, but that's the basic idea. This means that a pattern like

f [] = ...
f (x:xs) = ...

Is equivalent to

f Empty = ...
f (Cons x xs) = ...

just with more convenient syntax.

However, Int can be though of as a very large ADT defined as

data Int = -2147483648 | -2147483647 | ... | -1 | 0 | 1 | ... | 2147483646 | 2147483647

where each number itself is a different constructor. Then you can match on any individual number, but not anything like (x + 1) or (x * 2), because + and * are not constructors, just regular functions. (Note: Int is not actually defined this way because that would be really inefficient, it's defined at a more primitive level)

score 0 · Answer 3 · edited May 23 '17 at 10:31

You can get from list formulations to the non-list, recursive formulations, with manual inlining and fusing of the functions in play:

{-# LANGUAGE BangPatterns #-}
import Data.List

f a b c   = a+b+c
g f a b c = sum . map (f a b) $ [0..c]
          = foldl' (\ !x y -> x + f a b y) 0 $ enumFromTo 0 c
          = h 0 0   where
              h !acc i | i > c     = acc
                       | otherwise = h (acc + f a b i) (i+1)

Strictness annotations prevent uncontrolled build-up of thunks and stack overflow for big values of c.

Haskell take sum recursively

3 Answers3