module PairList where

data PairList a = PLNil
                | PLCons a (PairList (a,a))

instance Functor PairList where
  fmap = fmapPL

fmapPL :: (a->b) -> (PairList a -> PairList b)
fmapPL f PLNil        = PLNil
fmapPL f (PLCons a l) = PLCons (f a) (fmap f2 l)
  where f2 (x,y) = (f x, f y)

-- PairList is a nested datatype (non-regular datatype). It cannot be
-- expreessed as the fixed point of a functor. Thus the traditional
-- theory for polytypic function breaks down.  This is one of the
-- reasons for adopting Hinze's style of polytypic programming.

-- However, for this type at least, PolyP can generate pmap and crush
-- and some other functions.