Recursion

unknown＠example.com

6 Mar 2007 6 Mar '07

10:06 a.m.

Does the following code increase the level of recursion once for each input line or is the recursive construct converted to an iteration? Thanks, Dave Feustel main :: IO () main = do line <- getLine processIt line main processIt :: String -> IO () processIt s = do print (length s)

Show replies by date

Bryan Burgers

6 Mar 6 Mar

11:52 a.m.

On 3/6/07, Dave@haskell.org wrote:

...

Does the following code increase the level of recursion once for each input line or is the recursive construct converted to an iteration?

Thanks, Dave Feustel

main :: IO () main = do line <- getLine processIt line main

processIt :: String -> IO () processIt s = do print (length s)

Dave, I would imagine it does not, but I will let somebody more knowledgeable tell you for sure. My thought, though, is that if this is your whole code and not a simplified version (eg, one that terminates on certain input), then you could consider using the Prelude's 'interact'[1] function, which performs a transformation on standard input. In your case, the code would simplify to: main = interact (unlines . map (show . length) . lines) The unlines/lines combo breaks up the whole input into a list of lines of input, and the (show . length) is the heart of your 'processIt' function. Alternately, you could also use something like: main = getContents >>= mapM_ processIt . lines Which takes everything from standard in, splits it up into lines, and then performs processIt for each line. [1] http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v%3Ainte... Bryan

Jefferson Heard

1:50 p.m.

Bryan, The code here does not take advantage of laziness, which is probably what you want to do, as it is much cleaner to look at and more Haskell like. In answer to your question it is tail recursive, and strict, which means that in some compilers, with some optimization flags (i.e. GHC) you will get an iteration instead of a recursion, but consider instead this: main = do input = readFile stdin let r = map processit (lines input) putStrLn (unlines s) For more details, see: http://blogs.nubgames.com/code/?p=22 On Tuesday 06 March 2007 11:52, Bryan Burgers wrote:

...

On 3/6/07, Dave@haskell.org wrote:

...
Does the following code increase the level of recursion once for each input line or is the recursive construct converted to an iteration?

Thanks, Dave Feustel

main :: IO () main = do line <- getLine processIt line main

processIt :: String -> IO () processIt s = do print (length s)

Dave,

I would imagine it does not, but I will let somebody more knowledgeable tell you for sure. My thought, though, is that if this is your whole code and not a simplified version (eg, one that terminates on certain input), then you could consider using the Prelude's 'interact'[1] function, which performs a transformation on standard input. In your case, the code would simplify to:

main = interact (unlines . map (show . length) . lines)

The unlines/lines combo breaks up the whole input into a list of lines of input, and the (show . length) is the heart of your 'processIt' function.

Alternately, you could also use something like:

main = getContents >>= mapM_ processIt . lines

Which takes everything from standard in, splits it up into lines, and then performs processIt for each line.

[1] http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v%3Aint eract

Bryan _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Kirsten Chevalier

2 p.m.

On 3/6/07, Dave@haskell.org wrote:

...

Does the following code increase the level of recursion once for each input line or is the recursive construct converted to an iteration?

As was pointed out, tail recursion in Haskell isn't straightforward. The answer may also depend on which implementation of Haskell you're using. But I assume you mean GHC. If you want to know for sure, I suggest reading the intermediate code produced by GHC for this example (or perhaps an even smaller version of your example that retains the recursive structure but doesn't do IO). For some help with that, check out the manual's section on "How to read Core Syntax": http://www.haskell.org/ghc/docs/latest/html/users_guide/options-debugging.ht... and ask on this mailing list if you have any questions. Depending on why you're asking, actually reading the intermediate code may be overkill, but since you didn't say why you wanted to know, I assume you're just curious. Cheers, Kirsten -- Kirsten Chevalier* chevalier@alum.wellesley.edu *Often in error, never in doubt "Instant gratification takes too long."--Carrie Fisher

6651

Age (days ago)

6651

Last active (days ago)

List overview

Download

3 comments

4 participants

participants (4)