CODEWITHSUNDEEP
haskellrecursion
buydadip
buydadip

Reputation: 9407

Haskell- How to keep track of counter in recursive function

I'm having some difficulty trying to keep track of a counter variable in my function.

I created a function that takes a number as a single parameter and recursively multiplies the number by two, summing all the numbers multiplied by two together, the code below makes it more clear what I intend to do:

sum :: Float -> Float
sum x = x + sum (2*x)

However, the difficulty I am facing, is that I want the function to recurse only ten times. So I want it to stop once ten numbers have been added together. I tried using a counter to keep track of how many times the function has recursed, but to no avail.

This is what I tried:

sumTen :: Float -> Float
sumTen x n
    where
      n=10
       |n == 0 = x
       |otherwise = x + sumTen (2*x) (n-1)

I realize the code above does not work, counter n would be given the value ten through every recursive call, meaning it will never reach the base case n == 0.

What makes this so difficult is that sumTen must be called using one parameter. In the code above, I tried to give the function a default parameter n with a predetermined value, but it clearly does not work.

Can someone help me make the recursive function stop after 'n' recursive calls?

Upvotes: 4

Views: 9013

Answers (4)

Dan D.
Dan D.

Reputation: 74645

Perhaps this even:

sumTen x = sum $ take (10+1) $ iterate (* 2) x

Upvotes: 1

chi
chi

Reputation: 116139

Let's solve the problem in a general way. Start with your original function:

sum :: Float -> Float
sum x = x + sum (2*x)

As a first step, add an extra rec argument. This rec stands for "recursive call", and is a function that we are going to call instead of all the recursive calls in the function body. Concretely, just replace any sum that appears in the right hand side of the definition with rec:

sumK :: (Float -> Float) -> Float -> Float
sumK rec x = x + rec (2*x)

Now, if we wanted the recursive function executed zero times, we would get id. To recurse just once, we can use sumK id since

sumK id x = x + id (2*x) = x + 2*x

To recurse twice: sumK (sumK id) since

sumK (sumK id) x = x + sumK id (2*x) = x + (2*x) + 2*(2*x)

And so on: to recurse n times we just run sumK (... (sumK id)...) where sumK is applied n times. Equivalently, this can be written as the composition sumK . sumK . ... . sumK $ id. So, to obtain that it is enough to generate a list [sumK,sumK,...], compose them, and apply id at the end.

sum10 :: Float -> Float
sum10 = compose (replicate 10 sumK) id

compose :: [a -> a] -> a -> a
compose = foldr (.) id

If you prefer, you can write a small general helper:

recurseOnly :: Int -> ((a->a)->(a->a)) -> (a->a)
recurseOnly n funK = compose (replicate n funK) id

sum10 :: Float -> Float
sum10 = recurseOnly 10 sumK

Upvotes: 4

Fernando
Fernando

Reputation: 1450

You can use an auxiliary function:

sumNRec x 0     = 0 
sumNRec x times = x + sumNRec (x*2) (times - 1)

sumTen x = sumNRec x 10

Upvotes: 6

amalloy
amalloy

Reputation: 91837

sumTen :: Float -> Float
sumTen x = go 10 x
    where
      go n x
       | n == 0 = x
       | otherwise = x + go (n-1) (2*x)

There are two main points here: go is a simple recursive function of two arguments, which passes along the n to make you stop at the right time. But because you don't want to expose that argument, the top-level sumTen function is just a partially-applied version of go. You could even write this as:

sumTen = go 10
  where go n x = -- ...

Which one you prefer is a style choice, really.

Upvotes: 2

Related Questions