Extreme branchless: Expr without GADTs or sum-types
3 days ago
- #branchless-programming
- #type-classes
- #haskell
- Explores branchless programming using Church encoding and product-types.
- Introduces `FExpr` data type for embedding operations in a product-type, making adding new expressions cheap but new operations costly.
- Demonstrates defining operations like `fval`, `fadd`, and `feq` with examples.
- Discusses the equivalence of type-classes and records/product-types, with an attempt to transform bindings into data-types and type-classes.
- Highlights GHC's type constraints issues and the need for `TypeFamilies` to enforce output types.
- Attempts to implement instances using `Identity` and `Const`, facing challenges with wrapped values.
- Proposes a solution with `Extracted` type family and `UndecidableInstances` for type-checking instances.
- Concludes with the expressiveness of the approach, despite its complexity, and a preference for basic constructs over rigid type-classes.