Extreme branchless: Expr without GADTs or sum-types

Summary

In the previous log we have continued my branchless journey, based on Church encoding, having this type definition: newtype CExpr a = CExpr { runCExpr :: forall r. (a -> r a) -> (CExpr Int -> CExpr Int -> r Int) -> (CExpr Int -> CExpr Int -> r Bool) -> r a } As a reminder, I did so to avoid relying on extensions, but, to be fair, it takes some efforts to get use to that notation. After a second thought, well, maybe more a 20th, there is a more mainstream way to tackle it. However, it involves embedded all operations in a product-type, leaving the implementations open, as it is done in OOP, as follows: data FExpr a = FExpr { feval :: a, fprint :: String } Thanks to GHC defaults, nothing is evaluated until it is needed. We can define operations one by one as follows: fval :: (Show a) => a -> FExpr a fval x = FExpr { feval = x, fprint = show x } fadd :: FExpr Int -> FExpr Int -> FExpr Int fadd x y = FExpr { feval = x.feval + y.feval, fprint = "(" <> x.fprint <> ") + (" <> y.fprint <> ")" } feq :: FExpr Int -> FExpr Int -> FExpr Bool feq x y = FExpr { feval = x.feval == y.feval, fprint = "(" <> x.fprint <> ") == (" <> y.fprint <> ")" } It's clearly more readable, and it makes adding new kind of expression cheap, but adding new operation costly. We get a similar expressive power, as follows: fexpr :: FExpr Bool fexpr = fval 42 `feq` (fval 32 `fadd` fval 10) Note: in previous logs, I have emphasized the equivalence of type-classes and records/product-types. It could be tempting to transform previous binding in data-types and type-classes as follows: newtype SVal a = SVal {getSVal :: a} data SAdd f g a = SAdd {x :: f Int, y :: g Int} data SEq f g a = SEq {x :: f Int, y :: g Int} class SExpr (f :: Type -> Type) where seval :: f a -> a sprint :: (Show a) => f a -> String It seems to be a great idea, until we try to define instances: class SExpr (f :: Type -> Type) where seval :: f a -> a sprint :: (Show a) => f a -> String instance SExpr SVal where seval = getSVal sprint = s...