[Haskell-cafe] Re: Fun with type functions
Toby Hutton
toby.hutton at gmail.com
Thu Nov 27 18:06:42 EST 2008
On Thu, Nov 27, 2008 at 8:29 PM, Simon Peyton-Jones
<simonpj at microsoft.com> wrote:
> So this message is to ask you:
>
> can you tell us about the most persuasive, fun application
> you've encountered, for type families or functional dependencies?
I only just discovered functional dependencies a week or two ago, and
when it solved my problem it absolutely made my day.
I was reading 'Bananas, Lenses, etc.' and wanted to implement
paramorphic recursion with a type class. My initial attempt:
class Paramorphic p where
term :: p -> Bool
this :: p -> a
next ::: p -> p
para :: (Paramorphic p) => t -> (a -> (p, t) -> t) ->p -> t
para a f p | term p = a
| otherwise = f (this p) (next p, para a f (next p))
instance Paramorphic Int where
term = (== 0)
this = id
next = subtract 1
This is broken, since 'a' in 'this' is loose. Then I found multiple
class parameters:
class Paramorphic p a where
...
But 'a' was still too loose--para's type became
para :: (Paramorphic p a, Paramorphic p a1, Paramorphic p a2,
Paramorphic p a3) => t -> (a1 -> (p, t) -> t) -> p -> t
But a fundep solved it for me:
class Paramorphic p a | p -> a where
...
I could now pretty much do factorial and tails from the paper.
fact = para 1 (\a (_, b) -> a * b)
instance Paramorphic [a] a where
term = null
this = head
next = tail
tails = para [[]] (\a (as, b) -> (a : as) : b)
Not exactly a 'fun' example, but I was smiling for hours after
discovering this. :)
Toby.
More information about the Haskell-Cafe
mailing list