I came up with the following Brainfuck interpreter in Haskell after thinking about how to represent the program and the memory functionally using zippers to represent current location. This works since in Brainfuck, there is no way to reference more than one memory location away from your present location at one time.
import Control.Monad
import System.Environment
data ZL a = EM | ZL [a] a [a]
fromList [] = EM
fromList (x:xs) = ZL [] x xs
zprv EM = EM
zprv (ZL [] x rs) = EM
zprv (ZL (l:ls) x rs) = ZL ls l (x:rs)
znxt EM = EM
znxt (ZL ls x []) = EM
znxt (ZL ls x (r:rs)) = ZL (x:ls) r rs
zmap (ZL ls x rs) f = ZL ls (f x) rs
run code = go (fromList (repeat 0)) (fromList code)
where
go m EM = return m
go m i@(ZL _ '>' _) = go (znxt m) (znxt i)
go m i@(ZL _ '<' _) = go (zprv m) (znxt i)
go m i@(ZL _ '+' _) = go (zmap m (\x -> x + 1)) (znxt i)
go m i@(ZL _ '-' _) = go (zmap m (\x -> x - 1)) (znxt i)
go m@(ZL ml x mr) i@(ZL _ '[' _) = go m (if x /= 0 then znxt i else skip znxt 0 i)
go m@(ZL ml x mr) i@(ZL _ ']' _) = go m (if x == 0 then znxt i else skip zprv 0 i)
go m@(ZL _ x _) i@(ZL _ '.' _) = putChar (toEnum x) >> go m (znxt i)
go m@(ZL ml _ mr) i@(ZL _ ',' _) = getChar >>= \x -> go (ZL ml (fromEnum x) mr) (znxt i)
go m@(ZL ml x mr) i@(ZL _ _ _) = go m (znxt i) -- Ignore
skip _ 1 i@(ZL _ ']' _) = znxt i
skip _ (-1) i@(ZL _ '[' _) = znxt i
skip d n i@(ZL l '[' r) = skip d (n+1) (d i)
skip d n i@(ZL l ']' r) = skip d (n-1) (d i)
skip d n i@(ZL l _ r) = skip d n (d i)
main = do
getArgs >>= \args -> case args of
[] -> putStrLn "Usage: bf <program.bf>"
(x:_) -> readFile x >>= run >> return ()