[Haskell-beginners] Brainfuck interpreter stack overflow
stephen.tetley at gmail.com
Fri Jan 22 10:27:25 EST 2010
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 (><).
More information about the Beginners