Brainfuck Interpreter
Disclaimer: I know nothing about Frege, all comments apply to Haskell only.

1)

Running hlint on your code shows places where you can remove $ and brackets. Please do it!

2)

In exec, you always do exec prog tape after finishing current instruction. So you are iterating the list in some sense. This is a fold.

exec :: [Op] -&gt; Tape -&gt; IO Tape
exec prog tape = foldM f tape prog

  where f (Tape ls c rs) Plus    = return $ Tape ls (c+1) rs
        f (Tape ls c rs) Minus   = return $ Tape ls (c-1) rs
        f (Tape ls c rs) GoLeft  = let (hd, tl) = uncons ls in return $ Tape tl hd (c:rs)
        f (Tape ls c rs) GoRight = let (hd, tl) = uncons rs in return $ Tape (c:ls) hd tl
        f tape           Output  = printAsChar (cell tape) &gt;&gt; return tape
        f (Tape ls _ rs) Input   = do n &lt;- getChar
                                      return $ Tape ls (digitToInt n) rs

        f tape again@(Loop loop) | cell tape == 0 -&gt; return tape
                                 | otherwise -&gt; do tape' &lt;- exec loop tape
                                                   f tape' again


3)

printAsChar i = putStr $ [chr i]


hlint will tell you the $ is redundant:

printAsChar i = putStr [chr i]


You can use putChar:

printAsChar i = putChar (chr i)


and finally get:

printAsChar =  putChar . chr


You have a strange asymmetry - output uses chr, and input digitToInt. These are not inverses! digitToInt '0' is 0, but chr 0 is '\NUL', not '0'.

If you want to output numbers longer than 1 character, use

printAsString = putStr . show


4)

I would merge execute and exec:

 execute :: [Op] -&gt; IO Tape
 execute = foldM f (Tape [] 0 [])
   where f = ...


5)

 putStrLn $ "\n" ++ show tape ++ "\n" 


putStrLn already adds '\n" to the end, you might remove it.

6)

If you remove the requirement to print the tape (is it needed for debugging only?), you can use an infinite list:

 execute = foldM f (Tape (repeat 0) 0 (repeat 0))


and get rid of uncons:

       f (Tape (hd:tl) c rs) GoLeft  = return $ Tape tl hd (c:rs)
       f (Tape ls c (hd:tl)) GoRight = return $ Tape (c:ls) hd tl