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