A simple brainf*** interpreter in Haskell
Well done. Overall, there are no big flaws, just some minor issues.

Type annotations

While it's great that all top-level functions have proper type signatures, the local bindings inside those functions usually don't. After all, their types should get inferred, e.g.

example :: [Int] -&gt; [Int]
example = map inc
  where
    inc x = 1 + x


doesn't need a type signature since x's type is already fixed to Int. It makes refactoring also a lot easier if we change the type later. If we started with

example :: [Int] -&gt; [Int]
example = map inc
  where
    inc :: Int -&gt; Int
    inc x = 1 + x


and later want to generalize, we might forget the second type signature and end up with an error message:

example :: Num a =&gt; [a] -&gt; [a]
example = map inc
  where
    inc :: Int -&gt; Int -- whoops, GHC will yell about that
    inc x = 1 + x


Therefore, type signatures for local functions are usually not written out. There are some instances where they're necessary, but that's usually with RankNTypes or other extensions.

The tape

The tape works well, and is pretty much how you would expect it. 

Infinite tapes and debugging

That being said, an infinite tape has the slight inconvenience that you can never inspect it for debugging purposes. 

Also, if you ever create a module from your code, you must not export the Tape data constructor, as it would enable Tape [] 0 [] and therefore break assertions.

A finite tape circumvents those issues, but needs slightly more effort in the movements.

Working on the current value

In runBf we can find several spots where we advance the program after we worked on the current value, e.g.:

        Increment -&gt; advance prog (Tape ls (x+1) rs)
        Decrement -&gt; advance prog (Tape ls (x-1) rs)


That's now a possible source of errors, since we could have used

        Increment -&gt; advance prog (Tape ls (x+1) ls)
        Decrement -&gt; advance prog (Tape ls (x-1) ls)


by accident. A small helper can prevent that issue:

onCurrent :: (a -&gt; a) -&gt; Tape a -&gt; Tape a
onCurrent f (Tape ls x rs) = Tape ls (f x) rs

current   :: Tape a -&gt; a
current (Tape _ x _ ) = x


Then we end up with

        MovLeft   -&gt; advance prog (moveLeft tape)
        MovRight  -&gt; advance prog (moveRight tape)
        Increment -&gt; advance prog (onCurrent (+1) tape)
        Decrement -&gt; advance prog (onCurrent (subtract 1) tape)
        Input     -&gt; do 
            char &lt;- getChar 
            advance prog (onCurrent (const (fromEnum char)) tape)


Naming and scope

As neither advance nor getLoop use any of the bindings in their scope, they're candidates for top-level functions.

runBf' can be called go or another short name. Calling the inner worker just go is really common and won't alienate other readers.

Make interfaces hard to use wrong

getLoop uses an Int as first argument that's not properly documented. Types only go so far as documentation, and we could accidentally use getLoop 0 in BeginLoop.

Instead, we should make it impossible to misuse getLoop:

getLoop :: BfProgram -&gt; BfProgram
getLoop = go 1
  where
    go _ [] = error "Mismatched brackets in BF program"
    go 1 (EndLoop:ps) = [] 
    go n (p:ps) = p:case p of 
        BeginLoop -&gt; go (n + 1) ps 
        EndLoop   -&gt; go (n - 1) ps 
        _         -&gt; go n ps


Similarly, runBf should probably take a BfProgram, not an arbitrary String, as this doesn't decrease the strength of your program, we can recreate the previous behaviour with

runBf . parseBf


However, speaking of parsing…

Loop validation

A drawback with our current BfProgram is that we might end up with mismatched brackets, e.g.

parseBf "]["


parses fine and leads to a runtime error. However, we could easily detect that during parsing. Our parseBf needs a way to report errors:

type ParserError = String

parseBf :: String -&gt; Either ParserError BfProgram
parseBf = go
  where 
    go []     = Right []
    go (x:xs) = case x of
        '&lt;' -&gt; MovLeft &lt;$:&gt; go xs
        '&gt;' -&gt; MovRight &lt;$:&gt; go xs
        '+' -&gt; Increment &lt;$:&gt; go xs
        '-' -&gt; Decrement &lt;$:&gt; go xs
        ',' -&gt; Input &lt;$:&gt; go xs
        '.' -&gt; Output &lt;$:&gt; go xs
        '[' -&gt; -- exercise ; use `getLoop`-like function
        ']' -&gt; -- exercise ; easier if previous one done correctly.
        x   -&gt; go xs
   x &lt;$:&gt; xs = fmap (x:) xs


but afterwards, we can be sure that parseBf only returns BfPrograms with valid brackets.

Unfortunately, we still need to use getLoop, as BeginLoop and EndLoop are still in our instruction set. If we change the instruction set, we can get rid of that too:

data BfInstruction 
    = MovLeft
    | MovRight
    | Increment
    | Decrement
    | Output
    | Input 
    | Loop BfProgram
    deriving (Show, Eq)  


I go into more details in some of my previous Bf reviews, feel free to read them if you get stuck on Loop.

Final remarks

Other than the usual re-evaluation of loops (which is a common scenario in Haskell Bf interpreters), your code was fine, so all the issues are really minor. Again: well done.