Functional non recursive approach to looping in Haskell

Question

I use Haskell for my programming during leisure these days. Being a programmer in imperative languages for over 8 years, it is tough to wrap my head around some functional constructs (especially the folds). I was solving a problem from project Euler, and happened to produce the following code.

f (num, den) s | num*10 < den = s
               | otherwise = f (ratio (num, den) s') s'
               where s' = (s+2)

Can this explicit recursion be rewritten using folds or some other functional construct? The main hurdle for me in using a fold was to come up with the step function. Eventually I gave up, and resorted to the recursion.

EDIT: Also, how do I make the output returned by another function within a function as the input to the calling function without explicit recursion?

This looks like until to me

luqui
– luqui

2013-06-16 20:13:54 +00:00
Commented Jun 16, 2013 at 20:13 — luqui
– luqui, Commented Jun 16, 2013 at 20:13

daniel gratzer · Accepted Answer · 2013-06-16 20:16:58Z

10

There's always good old until

f = until test func
  where test ((a, b), _) = a * 10 < b
        func (p, s) = (ratio p s+2, s+2)

To be fair though, you're really always going to have some kind of recursion, it's just a matter of how much you abstract it away. There is no "loop" in Haskell.

As to your second question, I believe you've just asked "How do I have a function call itself without doing recursion". In short, you can't since that's the definition of recursion.

However with higher order functions like until iterate and fix (Look at the implementation of that one) you can avoid ever having to call your worker function. They take care of doing the explicit recursion under the covers.

answered Jun 16, 2013 at 20:16

daniel gratzer

54k11 gold badges100 silver badges137 bronze badges

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

4 Comments

Atmaram Shetye Over a year ago

Thanks for the pointer to until. As for the 2nd part, what I meant was whether explicit recursion can be avoided, by using the higher order constructs as you have described. The 'until', 'iterate' and 'fix' were all unknown to me as of now. Thanks again for the pointers.

daniel gratzer Over a year ago

No worries! Haskell's prelude is very expansive and powerful and has lots of nooks and crannies filled with useful functions like that

daniel gratzer Over a year ago

If I've answered your question, feel free to click the check box beside my answer to mark your question as "answered".

jk. Over a year ago

probably worth mentioning foldr and map etc. as well

Collectives™ on Stack Overflow

Functional non recursive approach to looping in Haskell

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related