@martijnhoekstra right, so there's a lot of directions you can go from there.
Instructionsare very similar to each other.
List[BFInstruction], transforms to an instruction being an AST with a type parameter for the output type, and a program no longer being just a
List[Instruction], but a
Free[Instruction, A], so you go from Free Monoids to Free Monads.
case class Loop(p: List[BFInstruction)instead, then you can remove that logic and move it to the Parser (you'd need a parser combinator library), at which point translating to tagless should be easier.
There are two versions that do the above:
1) initial: https://github.com/ekmett/lens/blob/b1ca6288fed878d7197416a9ca72983577260ad6/examples/Brainfuck.hs
warning: the haskell there is a bit outdated
data Op = Add Int Int | Const Int
Opto whatever you want to interpret this to (e.g. an
Intfor evaluation, or a String for pretty printing)
data Exp = Add Exp Exp | Lit Int
sealed trait Exp case class Add(l: Exp, r: Exp) extends Exp case class Lit(i: Int) extends Exp