[Haskell-begin] Morphing Endo (ICFP Contest 2007)
Benjamin L.Russell
DekuDekuplex at Yahoo.com
Thu Jul 24 03:41:01 EDT 2008
On Wed, 23 Jul 2008 22:11:10 -0300, "Rafael Gustavo da Cunha Pereira
Pinto" <rafaelgcpp at gmail.com> wrote:
>[...]
>
> I have a few problems:
>
>a) the DNA is 8MB long. How can I ensure the stack will hold a recursive
>call?
Forgive me if I'm wrong, but on a hunch, but this sounds like an issue
that could possibly be solved using tail recursion.
For example, according to "Recursion in a monad - HaskellWiki"
(http://haskell.org/haskellwiki/Recursion_in_a_monad), here is a
monadic do-block reads 'n' lines from stdin, using a linear recursive
process:
main = f 3
f 0 = return []
f n = do v <- getLine
vs <- f (n-1)
return $! v : vs
This runs as follows:
$ runhaskell A.hs
1
2
3
["1","2","3"]
Rewriting the code to make it use a linear iterative process (using
tail recursion) results in the following code:
f 0 acc = return (reverse acc)
f n acc = do
v <- getLine
f (n-1) (v : acc)
Here, "acc" stands for an accumulator, which is a register (here, a
variable simulating a register) to store temporary values. This
rewrite enables the process to use constant stack space.
Using this idea, it may be possible to rewrite your recursive function
process::ByteString -> a to use constant stack space.
-- Benjamin L. Russell
More information about the Beginners
mailing list