class Table k t | k -> t where
    lam :: (k -> a) -> t a
    app :: t a -> (k -> a)

newtype (O f g) a = Comp { deComp :: f (g a) }

instance (Table a t, Table b u) => Table (a,b) (t `O` u) where
    lam f = Comp (lam (\a -> lam (curry f a)))
    app (Comp x) (a,b) = app (app x a) b

data ListTable t x = ListTable x (t (ListTable t x))

instance Table a t => Table [a] (ListTable t) where
    lam f = ListTable (f []) (lam (\a -> lam (\as -> f (a:as))))
    app (ListTable a _) []     = a
    app (ListTable _ t) (x:xs) = app (app t x) xs

data IntTable x = IntTable [x] [x]

instance Table Int IntTable where
    lam f = IntTable (map f [0..]) (map f [-1,-2..])
    app (IntTable t u) x
        | x >= 0    = t !! x
        | otherwise = u !! (-x - 1)

memoise :: Table a t => ((a -> x) -> (a -> x)) -> (a -> x)
memoise f = g
    where table = lam (f g)
          g = app table

memoise2 :: (Table a t1, Table b t2) =>
            ((a -> b -> x) -> (a -> b -> x)) -> (a -> b -> x)
memoise2 f = curry (memoise (uncurry . f . curry))

-- ---------------------------------------------------------------------------

type Amount = Int
type Coin   = Int
type Count  = Int

memocc :: Amount -> [Coin] -> Count
memocc = memoise2 f
    where f g 0 _  = 1
          f g _ [] = 0
          f g a ccs@(c:cs)
              | a < 0     = 0
              | otherwise = g (a-c) ccs + g a cs