CODEWITHSUNDEEP
haskell
BrianWilson
BrianWilson

Reputation: 1703

Recursive arithmetic sequence in Haskell

It's been nearly 30 years since I took an Algebra class and I am struggling with some of the concepts in Haskell as I work through Learn you a Haskell. The concept that I am working on now is "recursion". I have watched several youtube videos on the subject and found a site with the arithmetic sequence problem: an = 8 + 3(an-1) which I understand to be an = an-1 + 3 This is what I have in Haskell.

addThree :: (Integral a) => a -> a
addThree 1 = 8
addThree n = (n-1) + 3

Running the script yields:

addThree 1
8
addThree 2
4
addThree 3
6

I am able to solve this and similar recursions on paper, (after polishing much rust), but do not understand the syntax in Haskell.

My Question How do I define the base and the function in Haskell as per my example?

If this is not the place for such questions, kindly direct me to where I should post. I see there are Stack Exchanges for Super User, Programmers, and Mathematics, but not sure which of the Stack family best fits my question.

Upvotes: 3

Views: 1626

Answers (1)

Random Dev
Random Dev

Reputation: 52290

First a word on Algebra and you problem: I think you are slightly wrong - if we write 3x it usually means 3*x (Mathematicans are even more lazy then programmers) so your series indeed should look like an = 8 + 3*an-1 IMO

Then an is the n-th element in a series of a's: a0, a1, a2, a3, ... that's why you there is a big difference between (n-1) and addThree (n-1) as the last one would designate an-1 while the first one would just be a number not really connected to your series.

Ok, let's have a look at your series an = 8 + 3an-1 (this is how I would understand it - because otherwise you would have x=8+3*x and therefore just x = -4:

  • you can choose a0 - let's say it`s 0 (as you did?)
  • then a1=8+3*0 = 8
  • a2=8+3*8 = 4*8 = 32
  • a3=8+3*32 = 8+3*32 = 104
  • ...

ok let's say you want to use recursion than the problem directly translates into Haskell:

a :: Integer -> Integer
a 0 = 0
a n = 8 + 3 * a (n-1)

series :: [Integer]
series = map a [0..]

giving you (for the first 5 elements):

λ> take 5 series
[0,8,32,104,320]

Please note that this is a very bad performing way to do it - as the recursive call in a really does the same work over and over again.

A technical way to solve this is to observe that you only need the previous element to get the next one and use Data.List.unfoldr:

series :: [Integer]
series = unfoldr (\ prev -> Just (prev, 8 + 3 * prev)) 0

now of course you can get a lot more fancier with Haskell - for example you can define the series as it is (using Haskells laziness):

series :: [Integer]
series = 0 : map (\ prev -> 8 + 3 * prev) series

and I am sure there are much more ways out there to do it but I hope this will help you along a bit

Upvotes: 9

Related Questions