How to do inverse series sum in haskell efficiently?

Question

This is the code I am trying to convert in haskell. But immutability creates the problem. How to do calculation without mutable variables. Creating a list of [1..20] and mapping over it doesn't seem like space efficient. Is there any trick or techniques to escape immutability?

int main()
{
    int i,n=0;
    double sum= 0.0;
    for ( i=1; i<20; ++i )
    {
        n += i;
        sum = 1 / (double) n;
    }
    printf("The sum is: %lf",sum);
    return 0;
}

Haskell can probably iterate over the list without materializing it, so maybe there is no space wasted. — Thilo, Aug 20 '16 at 13:16
@Thilo even keeping that in mind, still computation requires little bit of mutation. *The reason why we don't mark everything `const` in C*. Not an argument but the idea of everything immutable itches me sometimes. But Thanks for clearing my doubt up ! :) — GauravP, Aug 20 '16 at 13:23
@GauravP - if you are summing reciprocals of `n` you should fix your C code: `sum += 1 / (double) n` — ErikR, Aug 20 '16 at 14:00
@GauravP You are underestimating the amount of work the compiler can do. Things in Haskell are immutable by default; this *decreases* the overhead because the compiler can make optimizations that a C compiler cannot because immutability is already guaranteed. — chepner, Aug 20 '16 at 14:27
@ErikR not exactly the sum of reciprocals. It's modified for a math problem I have in an assignment. It needs the 'n' to be the sum of 1 to 'i' in each iteration 'i'. — GauravP, Aug 20 '16 at 15:40
Even if the list is materialized, in the sense that all reference to it does not disappear with build/foldr fusion, no more than one element need be in memory at a time, due to laziness and gc. — Michael, Aug 20 '16 at 15:45
@chepner I think I have to change my mind. But I was missing one thing that is the compiler is very smart in Haskell. I feel bad because I have hard time grasping immutable concept. Any advice for me from you. *I am going for functional programming over object oriented* — GauravP, Aug 20 '16 at 15:50
@Michael That makes sense actually ! After all haskell is lazy. It will never do anything that can be avoided. — GauravP, Aug 20 '16 at 15:53

chepner · Accepted Answer · 2016-08-20T14:49:08.757

5

Use scanl1 to generate your list of ns:

> scanl1 (+) $ [1..19]
[1,3,6,10,15,21,28,36,45,55,66,78,91,105,120,136,153,171,190]

From there, it is a simple matter to compute the inverses

> map (1/) . scanl1 (+) $ [1..19]
[1.0,0.3333333333333333,0.16666666666666666, ...]

and sum them:

> sum . map (1/) . scanl1 (+) $ [1..19]
1.8999999999999997

Although the Haskell code treats values as immutable and it appears you are generating a bunch of intermediate lists, the compiler is smart enough to generate efficient executable code.

edited Aug 20 '16 at 14:49

answered Aug 20 '16 at 14:43

chepner

497,756
71
530
681

Or, use math `2-2/(n+1)=1.9` – karakfa Aug 20 '16 at 14:54
Yes, that would apply to the original C code as well. We're trying to point out that what is a bad idea in C isn't necessarily a bad idea in Haskell. – chepner Aug 20 '16 at 14:56
1

I'm waiting for the day compilers to get smart enough to perform these higher level optimizations... – karakfa Aug 20 '16 at 15:02
Exactly the answer I was looking for. And the last output is also identical to that of C. Thank You ! :) – GauravP Aug 20 '16 at 15:55

ErikR · Answer 2 · 2016-08-20T14:14:27.450

You can examine the code that GHC generates with -ddump-asm.

Compile this program:

main = print $ 1.0 / fromIntegral (sum [(1::Int)..12345])

with:

$ ghc -O2 Main.hs -ddump-asm > asm-output

Then have a look at asm-output, search for 12345 and you will see this loop:

_c47b:
        addq %r14,%rsi
        incq %r14
_c476:
        cmpq $12345,%r14
        jne _c47b

This shows that the list [1..12345] is not actually created.

Update

It seems you intended to sum the reciprocals of the triangular numbers, i.e. 1/1 + 1/3 + 1/6 + ... That is, you intended to write:

sum += 1.0 / (double) n;

This can be expressed in Haskell as:

main = print $ sum $ map (\x -> 1 / (fromIntegral x)) $ scanl (+) 1 [(2::Int)..12345]

Examining the generated assembly we see again that no intermediate list is created:

_c4ao:
        cvtsi2sdq %rsi,%xmm0
        movsd _n4aP(%rip),%xmm2
        divsd %xmm0,%xmm2
        addsd %xmm2,%xmm1
        incq %r14
_c4ad:
        addq %r14,%rsi
        cmpq $12345,%r14
        jne _c4ao

Here %r14 is the counter i in your C code, %rsi is the variable n and %xmm1 is the accumulator sum.

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

3

To temporarily escape the immutability you can use the ST monad.

However there's no need for that. In the following expression everything will be optimised out by the compiler due to Stream Fusion:

sum (map (\n -> 1 / fromIntegral n) [1..20])

edited May 23 '17 at 10:28

Community

1
1

answered Aug 20 '16 at 13:37

Nikita Volkov

42,792
11
94
169

note I'm also incrementing n with each iteration so it goes like 1,3,6,10 so on up to 20. i and n is changing simultaneously. Thanks a lot I was looking for that escaping immutability. ST monad. Great resource. – GauravP Aug 20 '16 at 13:56
Data.List uses foldr/build fusion, which is basically the exact opposite of stream fusion. – Michael Aug 20 '16 at 15:33
I wish we'd stop referencing that answer. To much of the information in it is outdated. For example, the default Prelude list functions have had stream fusion for a while now... The first comment on [this](http://stackoverflow.com/questions/38905369/what-is-fusion-in-haskell) question sort of says it. – Alec Aug 20 '16 at 15:43

How to do inverse series sum in haskell efficiently?

3 Answers3