[Haskell-begin] Morphing Endo (ICFP Contest 2007)

[Benjamin L.Russell]

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