[Haskell-beginners] Brainfuck interpreter stack overflow

[Stephen Tetley]

Hi Edgar

You might want to look at Data.Sequence...

The transform function in your original code did both a cons (add to
the front) and an append / snoc (add one to the end).

transform :: BF -> [BF]
transform (Loop bs) = Jmpz (2 + lengthbs bs) : (bs >>= transform)  -- cons
                             ++ [Jmpb (1 + lengthbs bs)] --snoc / append
transform a = [a]

snoc-ing is expensive on standard lists because you have to implement
it as an appending a singleton list (which you did). Append performs a
full traversal of the first list - here is the implementation copied
from the GHC's libraries:

(++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys

In contrast, Data.Sequence has cheap operations for cons (<|), snoc
(|>) and append (><).

Best wishes

Stephen