[Haskell-cafe] Capped lists and |append|
Twan van Laarhoven
twanvl at gmail.com
Fri Jan 8 21:01:28 EST 2010
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.
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)
More information about the Haskell-Cafe