winterkoninkje: shadowcrane (clean) (Default)
wren romano ([personal profile] winterkoninkje) wrote2013-01-06 08:05 pm
Entry tags:

Finite sets

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 a for this one)
  • Can you figure out how to get a list of all the values, given some arbitrary implementation of assemble?

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)


Post a comment in response:

This account has disabled anonymous posting.
If you don't have an account you can create one now.
No Subject Icon Selected
More info about formatting

Loading anti-spam test...

If you are unable to use this captcha for any reason, please contact us by email at support@dreamwidth.org