[Haskell-cafe] Re: Fun with type functions

[Toby Hutton]

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.