Can I “factorize” a type signature?

Question

Suppose I wanted a function of type [[a]] -> [[b]] -> [[(a, b)]]. I'm sure I could figure something out, but chances are, it wouldn't be as clean as, for example, zipWith zip, which also has that type.

Entering this type signature into Hoogle gives me a few functions that fill this role, but they come from the leancheck and extrapolate packages, which I wouldn't want to drag into my project without a good reason.

Given that you can compute function composition through equational reasoning, I am wondering if there is an inverse to this process: is there a way that I could “factorize” a complex type signature and reduce it down to its simplest function composition?

Answer 1

Thank you to DanielWagner and Willem Van Onsem, who answered my question in the comments. What I thought was some sort of category-theory factorization turned out to simply be code generation.

The package exference does just what I wanted. From the documentation:

Type inference takes an expression and tells you its type. This process can be inversed: We recursively create random expression trees while checking that they -so far- match a given input type. At each step we do the backwards step of the inference algorithm step. If you are lucky, this search yields one or more expressions.

---

The package djinn also does code generation from type expressions, but supports less types, and has little documentation. However, it is guaranteed to always terminate, unlike exference.

For emacs users, it seems that djinn is already integrated into ghc-mod.

---

There is also Djest, by luqui, which is somewhat in between Quickcheck and the previous tools. It allows you to enter a few sets of input and output, for which the program will try and make up a function that satisfies them.

Thanks to all those who contributed and made me discover these packages.