Indexing Recursion without using an index parameter

Question

Am trying to write a recurssive function to do something, but at each step I'd like to know the current depth / index in the tree. So how can I achieve this without use of an index parameter in the function signature?

Something like:

rec_fn n = do print index
              do_something n
              if n > 0
                then rec_fn (n-1)
                else print "end"

so how do I obtain index, without doing something like:

rec_fn n i = do print i
                do_something n
                if n > 0
                  then rec_fn (n-1) (i+1)
                  else print "end"

bzn · Accepted Answer · 2011-10-13 10:46:25Z

12

Well, if your function depends on the current index it should get it as an argument. Otherwise you break many nice features of pure functions, such as referential transparency.

If its about getting rid of the extra parameter at the function call, you can use a helper function like the following:

rec_fn n = go n 0
    where go n i = do print i
                      do_something n
                      if n > 0
                         then go (n-1) (n+1)
                         else print "end"

This is a pattern that's used quite often in Haskell.

answered Oct 13, 2011 at 10:46

bzn

2,3922 gold badges18 silver badges21 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

ertes · Accepted Answer · 2011-10-13 12:18:20Z

1

It really depends on what exactly is wrong with the index argument. Do you want to get rid of it, because you don't want to pass it around all the time? Then the answer is: You shouldn't do that, because it would make your code more difficult to understand. However, if you insist, you can use a state monad. Again: If your reason is convenience, really don't do it. In almost all cases and particularly in your case it will be less convenient in the end.

A legitimate reason for getting rid of an argument is when it's redundant like in a list length function, which always initializes its accumulator with 0. In that case see bzn's answer.

answered Oct 13, 2011 at 12:18

ertes

2,29715 silver badges10 bronze badges

Collectives™ on Stack Overflow

Indexing Recursion without using an index parameter

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related