Brainfuck interpreter stack overflow

He Stephen Thanks for the tip. I will test the performance of Data.Sequence against Immutable arrays. I also have another question about deriving monads. I have modified Data.List.Zipper, so it supports 2 extra directions (up and down): data Zipper a = Zip [a] [a] [a] [a] Now I made a functor out of it: ** instance Functor Zipper where -- fmap :: (a -> b) -> f a -> f b f `fmap` (Zip ls rs ds us) = Zip (f `fmap` ls) (f `fmap` rs) (f `fmap` ds) (f `fmap` us) This works. Now I try to make an monad out of it: instance Monad Zipper where return a = Zip [a] [] [] [] (Zip ls rs ds us) >>= f = Zip (ls >>= f) (rs >>= f) (ds >>= f) (us >>= f) This doesn't work like expected, but when using the newtype derive mechanism it works. Thanks for all your help so far. Best Wishes, Edgar

Hi Edgar I'm not sure what a 'lawful' monad would be for your zipper, so I can sympathize with the author of the package on Hackage who omitted one. Monads have three laws which instances of the Monad class are obliged to obey, but the language cannot check that they do (i.e the type system can't check you obey them): http://www.haskell.org/haskellwiki/Monad_Laws A text book on Haskell would cover the monad laws if it covers monads, for instance in Paul Hudak's book they are on page 254. For a more general zipper, Chung-chieh Shan has a monad: http://conway.rutgers.edu/~ccshan/wiki/blog/posts/WalkZip3/ However that monad looks very similar to a resumption monad (resumption monads are commonly used to model concurrency as they can pause computations and so yield to other threads). This seems appropriate to a zipper - I think that Gerard Huet, the inventor of the zipper, originally used it to move a cursor around a tree structure within an interactive editor. A quick web search reveals another one here, I've never looked at this one before but it looks close to a state monad: http://www.haskell.org/haskellwiki/Zipper_monad
From your definition, I suspect if you use GHCs deriving mechanism it will make a quadruple list monad which will obviously compile and run but doesn't seem appropriate.
Best wishes Stephen

On Tue, Jan 26, 2010 at 05:06:25PM +0100, Edgar Klerks wrote:
I also have another question about deriving monads. I have modified Data.List.Zipper, so it supports 2 extra directions (up and down):
data ZipperQuad a = Zip [a] [a] [a] [a]
(I've changed the name to ZipperQuad.) How do you go up and down? If say that up :: ZipperQuad a -> ZipperQuad a up (Zip ls rs ds (u:us)) = Zip ls rs (u:ds) us up z = z then your new zipper is isomorphic to two old zippers data ZipperQuad' a = Z4 !(Zipper a) !(Zipper a) with functions up,down,left4,right4 :: ZipperQuad' a -> ZipperQuad' a up (Z4 h v) = Z4 h (right v) down (Z4 h v) = Z4 h (left v) left4 (Z4 h v) = Z4 (left h) v right4 (Z4 h v) = Z4 (right h) v Wouldn't a really fair ZipperQuad walk on a grid? -- Felipe.
participants (3)
-
Edgar Klerks
-
Felipe Lessa
-
Stephen Tetley