CODEWITHSUNDEEP
listfunctionhaskellrecursion
Fale
Fale

Reputation: 147

Haskell Recursive 'sum' Function

I find it really difficult to understand the mechanics of the following recursive function:

sums (x:y:ys) = x:sums(x + y : ys)
sums xs = xs

sums ([0..4])

Output:
[0, 1, 3, 6, 10]

What exactly happens in this line?:

x:sums(x + y : ys)

I would say that before the program can append the 'x' to the list, the function sum(x + y : ys) has to be executed first. But in that case, 'x' would be appended to the list only once - at the end of the recursion loop - which wouldn't result in the given output... so where are the flaws in my logic?

My follow-up question: how should I look at/treat recursive functions in a logical way, that will (hopefully) lead me to an 'aha-erlebnis'?

Any help is much appreciated!

Upvotes: 1

Views: 2570

Answers (4)

Toxaris
Toxaris

Reputation: 7266

You can understand Haskell code by stepwise reduction. Maybe the following example reduction sequence helps with your aha.

(A Haskell implementation actually does something related to such reduction steps, but maybe in a different order. You get the same end result, though).

In this example, you start with:

sums [0..4]

Expand the [0..4] notation a bit:

sums (0 : 1 : [2..4])

Now we see that the first equation of sums matches, with x = 0, y = 1, and ys = [2..4]. So we get:

0 : sums (0 + 1 : [2..4])

We can compute 0 + 1:

0 : sums (1 : [2..4])

And expand [2..4] a bit:

0 : sums (1 : 2 : [3..4])

Now we see that the first equation of sums matches again, this time with x = 1, y = 2, and ys = [3..4]. So we get:

0 : 1 : sums (1 + 2 : [3..4])

We can compute 1 + 2:

0 : 1 : sums (3 : [3..4])

And expand [3..4] a bit:

0 : 1 : sums (3 : 3 : [4..4])

Now we see that the first equation of sums matches again, this time with x = 3, y = 3, and ys = [4..4]. So we get:

0 : 1 : 3 : sums (3 + 3 : [4..4])

We can compute 3 + 3:

0 : 1 : 3 : sums (6 : [4..4])

And expand [4..4]:

0 : 1 : 3 : sums (6 : 4 : [])

Now we see that the first equation of sums matches again, this time with x = 6, y = 4, and ys = []. So we get:

0 : 1 : 3 : 6 : sums (6 + 4 : [])

We can compute 6 + 4:

0 : 1 : 3 : 6 : sums (10 : [])

This time, the first equation for sums doesn't match. But the second equation matches. So we get:

0 : 1 : 3 : 6 : 10 : []

This is the observed output [0, 1, 3, 6, 10].

Upvotes: 9

user6996876
user6996876

Reputation:

You could notice that 

sums (x:y:ys) =  x:sums(x + y : ys)

is equivalent to

sums (x:y:z:ys) = x:x+y:sums(x+y+z : ys)
sums (x:y:ys) = x:sums(x + y : ys)

and (with more than 2 items) is also equivalent to

sums (x:y:z: w: ys) = x:x+y:x+y+z:sums(x+y+z +w: ys)
sums (x:y:z:ys) = x:x+y:sums(x+y+z : ys)
sums (x:y:ys) = x:sums(x + y : ys)

so by induction you have that 

sums(1:2:3:4 :[])

is equal to

1 : 1 + 2 : 1 + 2 + 3 : 1 + 2 + 3 + 4 : []

Based on the above you can also predict that with

fact(x:y:ys) = x: fact(x * y : ys)
fact(xs) = xs

then

fact([1..4])

is 

1:1*2:1*2*3:1*2*3*4:[]

Upvotes: 1

n. m. could be an AI
n. m. could be an AI

Reputation: 120079

There are two equation that define the function sums. Keep rewriting an expression that involves sums using the first equation that matches the argument, or other suitable equations (like 1+2=3).

sums [0..4] = 
    -- by syntactic sugar
sums (0:1:2:3:4:[]) = 
    -- by eq. 1, x=0,y=1,ys=2:3:4:[]
0 : sums ((0+1) : 2 : 3:4:[]) = 
    -- by addition 
0 : sums (1 : 2 : 3:4:[]) = 
    -- by eq. 1, x=1, y=2, ys=3:4:[]
0 : 1 : sums ((1+2) : 3 : 4:[]) =
    -- by addition 
0 : 1 : sums (3 : 3 : 4:[]) =
    -- by eq. 1, x=3, y=3, ys=4:[]
0 : 1 : 3 : sums ((3+3) : 4 : []) = 
    -- by addition
0 : 1 : 3 : sums (6 : 4 : []) = 
    -- by eq. 1, x=6, y=4, ys=[]
0 : 1 : 3 : 6 : sums ((6+4):[]) = 
    -- by addition
0 : 1 : 3 : 6 : sums (10:[]) = 
    -- by eq  2,xs=(10:[]) 
0 : 1 : 3 : 6 : 10 : [] = 
    -- by syntactic sugar
[0,1,3,6,10]

Upvotes: 0

chepner
chepner

Reputation: 532208

This is no different than recursion in any other langauge. When sums [0..4] (the parentheses are unnecessary) is first called, x==0, y==1, and ys == [2..4]. Thus, the return value is a new list created from 0 and sums [1..4].

In a strict language, the recursive call would complete before finally creating the new list. Since Haskell is lazy, a list starting with 0 and continuing with a promise to evaluate sums [1..4] is returned. The recursive call won't actually be evaluated until someone actually tries to access the tail of the list.

Upvotes: 3

Related Questions