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
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.
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)