import Data.Monoid

data Checksum = Checksum String deriving (Eq, Show, Read)

instance Monoid Checksum where
    mempty = Checksum ""
    mappend (Checksum s) (Checksum t) = Checksum $ s ++ t

stringOf (Checksum s) = s


class Checksummable a where
    checksum :: a -> Checksum

class (Checksummable a) => FastEq a where
    feq :: a -> a -> Bool
    x `feq` y = checksum x == checksum y
    
instance Checksummable Integer where
    checksum = Checksum . ("Integer::" ++) . show

instance Checksummable String where
    checksum = Checksum . ("String::" ++)

data (Checksummable a) => FooBar a = Foo a | Bar a

instance (Checksummable a) => Checksummable (FooBar a) where
    checksum (Foo x) = Checksum "Foobar a::Foo:" `mappend` checksum x
    checksum (Bar x) = Checksum "Foobar a::Bar:" `mappend` checksum x

data (Checksummable a) => Tree a = Node a (Tree a) (Tree a) | Nil

instance (Checksummable a) => Checksummable (Tree a) where
    checksum (Node v l r) = Checksum "Node::" `mappend` checksum v `mappend` checksum l `mappend` checksum r
    checksum Nil = Checksum "Nil"

instance (Checksummable a) => FastEq (Tree a) where
    s `feq` t = checksum s == checksum t