So, I just encountered a most delicious type the other day:
class Finite a where assemble :: Applicative f => (a -> f b) -> f (a -> b)
What's so nice about it is that the only way you can implement it is if the type
a is in fact finite. (But see the notes.) So the questions are:
- Can you see why?
- Can you figure out how to implement it for some chosen finite type?
- Can you figure out how to implement it in general, given a list of all the values? (you may assume
Eq afor this one)
- Can you figure out how to get a list of all the values, given some arbitrary implementation of
A trivial note: Well, of course you can implement anything in Haskell by using
undefined or equivalent. For the sake of these problems, assume you're constrained to use only fully-defined functions.
A big note, also a hint perhaps: And really, there's nothing here that truly forces the type to be finite. In order to get some real logical guarantees, you should assume you're in a total language (preferably a provably-total language), and you should use the following dependent type instead:
class Finite a where assemble :: Applicative f => ((x::a) -> f (b x)) -> f ((x::a) -> b x)