Calculating Mersenne numbers in Haskell

user_8908375 0
Viewed 464

We have the task to build a simple recursive function displaying the Mersenne number in Haskell, sorted from smallest to biggest number. It's basicly 2^n-1 So mersenne 7 looks something like that [0,1,3, 7, 15, 31, 63]

We couldn't get it done sadly and are stuck on that piece of code.

mrs :: Integer -> [Integer]
mrs 1 = [0]
mrs n = n : mrs (2^(n-1)-1)

But somehow the numbers are increasing in size while they should decrease because n is getting lower. I believe it's easy to solve and I'll feel dumb afterwards, but so be it.

Currently, for input 7 it spits out [7, 63, 46.........giant number, error]

For input 3 it constantly spits out 3's: [3,3,3,3...] and lower than that tells me about negativ exponents.

We are quite new to Haskell, all googling and reading through scripts didn't work.

haskell
2 Answers

You need to decrease your n value with each call, but you're currently increasing it. What you really want is probably: 

mrs :: Integer -> [Integer]
mrs 1 = [0]
mrs n = (2^(n-1)-1) : mrs (n-1)

> mrs 7
[63,31,15,7,3,1,0]

If you want to keep the order increasing, just reverse the list: 

> reverse $ mrs 7
[0,1,3,7,15,31,63]
user_38060460

A more declarative style to do this is probably defining a range [1..n] and then perform a mapping over it: \x -> 2^(x-1)-1:

mrs n = map (\x -> 2^(x-1)-1) [1..n]

or a pointfree approach:

mrs n = map (subtract 1 . (2 ^) . subtract 1) [1..n]

Now we can improve the situation by performing the subtract 1 already in the range:

mrs n = map (subtract 1 . (2 ^)) [0..n-1]

This produces:

Prelude> mrs 7
[0,1,3,7,15,31,63]
user_675790
Related