[Haskell-cafe] Capped lists and |append|

[Twan van Laarhoven]

John Millikin wrote:
> Earlier today I uploaded the capped-list package; I didn't think there
> would be any interest, since it's a relatively trivial data structure,
> but already there's been three emails and an IRC convo about it.
> 
> Since uploading, there's been a big problem pointed out to me
> regarding this structure, namely the possible definitions of |append|.
> 
> Any ideas? This seems like a useful structure, since several people
> have described it, but some of the semantics seem troublesome.

Some ideas:

     append :: Monoid c => CappedList c a -> CappedList c a -> CappedList c a
     append (Cap a) (Cap b) = Cap (a `mappend` b)

This also leads to an instance Monoid (CappedList c):

     instance Monoid c => Monoid (CappedList c) where
         mempty  = Cap mempty
         mappend = append

You could also make the combining function flexible:

     appendWith :: (c -> d -> e) -> CappedList c a -> CappedList d a
                -> CappedList e a


The problem with this definition is that it doesn't really respect the structure 
of the second list: the entire list has to be traversed just to update the cap. 
More random ideas:

     -- this is bind in the CappedList _ a monad
     bindCap :: CappedList c a -> (c -> CappedList d a) -> CappedList d a

     bindCapF :: Functor f => CappedList c a
              -> (c -> f (CappedList d a))
              -> f (CappedList d a)


Twan