[Haskell-cafe] Monadic bind with associated types + PHOAS?

oleg at okmij.org oleg at okmij.org
Wed Nov 19 00:21:39 EST 2008

Ryan Ingram wrote:
> One thing that often comes up is a desire to do a pass on the
> resultant code to optimize it, but it's pretty difficult with the
> standard monadic formulation because of embedded functions.  You can't
> do introspection on functions in Haskell; they aren't elements of Eq
> or Show.  This has caused, for example, some implementations of FRP to
> switch to using arrows instead.  However, I find the arrow syntax
> cumbersome and I feel it tends to obfuscate what is actually going on
> in the code.
> An earlier talk at ICFP mentioned using PHOAS instead of HOAS to
> encode expressions.  In HOAS, a lambda expression in the target
> language is represented by a function in the source language:

If one uses a tagless final representation, one benefits from the
conveniences of the higher-order abstract syntax and yet gains the
ability to show terms, count the number of constructors and even
partially evaluate them (i.e., optimize). For the example, please see

(in particular, see Semantics2 for the partial evaluator that does not
use GADT). We can easily add an interpreter that does a CPS transform,
thus letting us embed a CBV object language in a Haskell without
any use of monad or the change of syntax of the object language. We
can easily extend the language to add state (as we have done in the
OCaml part of the project).

More information about the Haskell-Cafe mailing list