CODEWITHSUNDEEP
haskellrecursionaccumulator
lattejiu
lattejiu

Reputation: 119

Using Recursion and Accumulators in Haskell

I'm experimenting with guard recursion, but I'm having a difficult time with Haskell syntax.
I'm trying to use recursion in Haskell to reduce an integer 'n' number of times until it reaches my desired base case, while keeping track of 'n', then return the reduced integer and 'n' as a tuple for my piece of information.

My base case would be when the integer is within 1 to 13.

For example,

Prelude> reduce 42
(3, 2)

Prelude> reduce 3
(3, 0)

To explain the logic,

Prelude> reduce 42
( (((42 - 13) - 13) - 13), 1+1+1+1 ) --> assume the accumulator = 0, hence 0,1,2.
(3, 3)

Prelude> reduce 3
(3, 0) --> already in base case!

Currently, I have

reduce (x, 0)
  | x `elem` [1 .. 13] = (x, acc)
  | otherwise = reduce (x -13, acc + 1)
  where
    acc = 0

But of course, my IDE is yelling that I'm wrong. I have no clue how to implement initialize tuples into this recursion so that it's like reduce :: a -> (a, b)
EDIT: I think I'm getting closer...but of course, I'm trying to implement it as a -> (a,b).

Upvotes: 0

Views: 454

Answers (3)

amalloy
amalloy

Reputation: 91837

Using an accumulator parameter is a fine approach, and indeed the most efficient one, provided you manage laziness correctly with seq. However, an arguably simpler technique, perhaps easier to learn, would use no accumulator parameter. Instead, do the recursive call and then modify its result:

reduce x | x `elem` [1..13] = (x, 0)
         | otherwise = let (y, n) = reduce (x - 13)
                       in (y, n + 1)

It further turns out that there is a cute shortcut for "modify the second element of a tuple" - I wouldn't recommend using this in your first programs, but it's an interesting taste of what may be to come:

reduce x | x `elem` [1..13] = (x, 0)
         | otherwise = succ <$> reduce (x - 13)

Upvotes: 4

Alistair Wall
Alistair Wall

Reputation: 332

You need to initialise it with a helper function:

reduce::Int->(Int,Int)
reduce x = reduce' (x,0)

reduce'::(Int,Int)->(Int,Int)
reduce' (x,n)

  | elem x [1..13] = (x,n) 

  | otherwise = reduce' (x-13,n+1)

Upvotes: 2

Alistair Wall
Alistair Wall

Reputation: 332

Underscore is not allowed in this position.

reduce::Int->Int                                                                                                                                                                        
 reduce x
    | elem x [1..13] = x
    | otherwise = reduce (x - 13)

Upvotes: 0

Related Questions