N. Frisby, A. Gill, and P. Alexander, “A pattern for almost homomorphic functions,” in ACM SIGPLAN Workshop on Generic Programming, Sep 2012.


Strong typing presents the programmer with a trade-off between correctness and code complexity: more exact types prevent errors but less exact types enable reuse. Current functional programming practice prefers general types over exact types in large programs like compilers because of the reuse. Exact typing in these programs would require numerous similar data types and conversions between them. We factor out a pattern in such conversions as a reusable Haskell function. We extend existing generic programming techniques to define it and to use it without introducing undue obfuscation. Our reusable function eliminates the boilerplate for conversions between the numerous exact types. It therefore delivers the benefits of exact types and simulates the reusability of general types with lightweight generic programming. We demonstrate our function by using it to define a lambda-lifting function with an exact range type that has no constructor for lambdas.


  author = {Nicolas Frisby and Andy Gill and Perry Alexander},
  title = {A Pattern for Almost Homomorphic Functions},
  booktitle = {ACM SIGPLAN Workshop on Generic Programming},
  location = {Copenhagen, Denmark},
  year = {2012},
  month = {Sep},