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. In short, this is Heinrich Apfelmus's "Train" type from http://www.haskell.org/pipermail/haskell-cafe/2009-December/069895.html, which showed up in a thread I posted regarding lazy error handling http://www.haskell.org/pipermail/haskell-cafe/2009-November/069825.html. The structure of a Train / CappedList (I like my name better) is: data Train a b = Wagon a (Train a b) | Loco b data CappedList cap a = Next a (CappedList cap a) | Cap cap Since uploading, there's been a big problem pointed out to me regarding this structure, namely the possible definitions of |append|. Because the list terminus is itself a value, but isn't / shouldn't be the same type as the elements, either obvious implementation will drop it. append :: CappedList cap a -> CappedList cap a -> CappedList cap a append (Cap 0) (Cap 1) = -- either (Cap 0) or (Cap 1), but information has been lost This problem can be solved using an unusual type signature for |append|, such as: append :: CappedList cap1 a -> CappedList cap2 a -> (cap1, CappedList cap2 a) or by declaring that a capped list is truly "capped": append :: CappedList cap a -> CappedList cap2 b -> CappedList cap a but these makes defining a reasonable |concat| difficult. Any ideas? This seems like a useful structure, since several people have described it, but some of the semantics seem troublesome.
[Disclaimer: I didn't really read all the thread from which this data structure originated on Cafè =).] On Fri, Jan 08, 2010 at 03:38:15PM -0800, John Millikin wrote:
Since uploading, there's been a big problem pointed out to me regarding this structure, namely the possible definitions of |append|. Because the list terminus is itself a value, but isn't / shouldn't be the same type as the elements, either obvious implementation will drop it.
append :: CappedList cap a -> CappedList cap a -> CappedList cap a append (Cap 0) (Cap 1) = -- either (Cap 0) or (Cap 1), but information has been lost
I don't think there is an easy solution here. In a first approach, what I would do would be to provide -- Returning one of the caps out of list. appendL :: CappedList cap a -> CappedList cap' a -> (cap', CappedList cap a) appendR :: CappedList cap' a -> CappedList cap a -> (cap', CappedList cap a) -- Discarding one of the caps. appendL_ :: CappedList cap a -> CappedList discarded a -> CappedList cap a appendR_ :: CappedList discarded a -> CappedList cap a -> CappedList cap a -- 'mappend'ing the caps appendM :: Monoid cap => CappedList cap a -> CappedList cap a -> CappedList cap a and then define mappend = appendM If we used appendL_ then we would violate Monoid's law that says that mappend mempty x = x And if we used appendR_ we would violate mappend x mempty = x Of course, you would have to change your 'empty' package to include the following law: "For every data type implementing Empty and Monoid, empty should be mempty." This way you will guarantee that when using appendM Cap empty `mappend` Cap c = Cap c Also, you may want to have CappedList an instance of Control.Functor.Bifunctor from category-extras: -- Hask is a synonym for (->). instance Bifunctor CappedList Hask Hask Hask where bimap f g = foldr (Next . f) (Cap . g) And, of course, import Data.Monoid (First(..), Last(..)) appendL_ = bimap id getFirst . appendM . bimap id First appendR_ = bimap id getLast . appendM . bimap id Last Cheers, -- Felipe.
Everything here makes much more sense than the previous implementation
-- I've upped 1.2, which splits up |append|, implements the instances
in terms of Monoid, etc.
Also included is |toList| and |toList_| , which are like functions
defined in Felipe's earlier email to me. The first returns the cap and
values, the second only the values.
Last (but not least), some of the |append*| functions are now defined
in terms of |appendWith| from Twan van Laarhoven's email. For example,
|appendM = appendWith mappend|.
On Fri, Jan 8, 2010 at 17:57, Felipe Lessa
Of course, you would have to change your 'empty' package to include the following law:
"For every data type implementing Empty and Monoid, empty should be mempty."
"empty" turned out to be a dumb idea -- I had hoped to use it for types which support a NIL value but not appending. Turns out, there's not much point to lists which can't be appended. C'est la vie.
Also, you may want to have CappedList an instance of Control.Functor.Bifunctor from category-extras: [...]
This is probably a good idea, but, I am nervous about making such a small package depend on the huge category-extras and mtl.
On Fri, Jan 08, 2010 at 09:10:38PM -0800, John Millikin wrote:
Also, you may want to have CappedList an instance of Control.Functor.Bifunctor from category-extras: [...]
This is probably a good idea, but, I am nervous about making such a small package depend on the huge category-extras and mtl.
Well, then just provide the plain function in the module bimap :: (a -> b) -> (cap -> cap') -> CappedList cap a -> CappedList cap' b bimap f g = foldr (Next . f) (Cap . g) :) -- Felipe.
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
On Fri, Jan 8, 2010 at 6:38 PM, John Millikin
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.
In short, this is Heinrich Apfelmus's "Train" type from http://www.haskell.org/pipermail/haskell-cafe/2009-December/069895.html, which showed up in a thread I posted regarding lazy error handling http://www.haskell.org/pipermail/haskell-cafe/2009-November/069825.html. The structure of a Train / CappedList (I like my name better) is:
data Train a b = Wagon a (Train a b) | Loco b data CappedList cap a = Next a (CappedList cap a) | Cap cap
The order of the type parameters is important. In particular, Train is
a free monad, with (>>=) acting as a generalized append.
instance Monad (Train a) where
return = Loco
Loco a >>= f = f a
Wagon x t = Wagon x (t >>= f)
Monad instances for CappedList are also possible, but more complex:
instance Monoid cap => Monad (CappedList cap) where
return a = Next a mempty
Cap c >>= f = Cap c
Next a as >>= f = f a `mappend` (as >>= f)
(I can't check what you've uploaded because Hackage is down, so my
apologies if I'm telling you things you already know.)
--
Dave Menendez
Excerpts from John Millikin's message of Sat Jan 09 00:38:15 +0100 2010:
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.
In short, this is Heinrich Apfelmus's "Train" type from http://www.haskell.org/pipermail/haskell-cafe/2009-December/069895.html, which showed up in a thread I posted regarding lazy error handling http://www.haskell.org/pipermail/haskell-cafe/2009-November/069825.html. The structure of a Train / CappedList (I like my name better) is:
data Train a b = Wagon a (Train a b) | Loco b data CappedList cap a = Next a (CappedList cap a) | Cap cap
Since uploading, there's been a big problem pointed out to me regarding this structure, namely the possible definitions of |append|. Because the list terminus is itself a value, but isn't / shouldn't be the same type as the elements, either obvious implementation will drop it.
I would suggest: appendWith :: (cap1 -> cap2 -> cap3) -> CappedList cap1 a -> CappedList cap2 a -> CappedList cap3 a Here is some functions I written when reading about this data-type: data Train a b = Wagon a (Train a b) | Caboose b trainToList :: (b -> [a]) -> Train a b -> [a] trainToList f (Wagon x xs) = x : trainToList f xs trainToList f (Caboose x) = f x addCaboose :: b -> [a] -> Train a b addCaboose b [] = Caboose b addCaboose b (x:xs) = Wagon x (addCaboose b xs) caboose :: Train a b -> b caboose (Wagon _ xs) = caboose xs caboose (Caboose x) = x dropCaboose :: Train a b -> [a] dropCaboose = trainToList (const []) updateCaboose :: (b -> Train a c) -> Train a b -> Train a c updateCaboose f (Wagon x xs) = Wagon x (updateCaboose f xs) updateCaboose f (Caboose x) = f x -- change caboose's contents mapCaboose :: (b -> c) -> Train a b -> Train a c mapCaboose f = updateCaboose (Caboose . f) -- append trains and merge cabooses appendTrain :: (b -> c -> d) -> Train a b -> Train a c -> Train a d appendTrain f xs ys = updateCaboose (\b -> updateCaboose (Caboose . f b) ys) xs -- concat trains and merge cabooses concatTrain :: (b -> c -> c) -> c -> [Train a b] -> Train a c concatTrain f = foldr (appendTrain f) . Caboose foldl'TrainWith :: (a -> c -> d) -> (a -> b -> a) -> a -> Train b c -> Train b d foldl'TrainWith p f z (Wagon x xs) = z `seq` Wagon x (foldl'TrainWith p f (f z x) xs) foldl'TrainWith p f z (Caboose x) = Caboose (p z x) foldl'Train :: (a -> b -> a) -> a -> Train b c -> Train b (a,c) foldl'Train = foldl'TrainWith (,) sumTrain :: Num n => Train n a -> Train n (n, a) sumTrain = foldl'Train (+) 0 productTrain :: Num n => Train n a -> Train n (n, a) productTrain = foldl'Train (*) 1 -- For instance to compute both the sum and the product of a train -- modularly: -- -- fst . caboose . sumTrain . productTrain :: Num n => Train n a -> (n , n) concatAndSumCabooses :: Num b => [Train a b] -> Train a b concatAndSumCabooses = concatTrain (+) 0 -- Nicolas Pouillard http://nicolaspouillard.fr
John Millikin schrieb:
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.
In short, this is Heinrich Apfelmus's "Train" type from http://www.haskell.org/pipermail/haskell-cafe/2009-December/069895.html, which showed up in a thread I posted regarding lazy error handling http://www.haskell.org/pipermail/haskell-cafe/2009-November/069825.html. The structure of a Train / CappedList (I like my name better) is:
data Train a b = Wagon a (Train a b) | Loco b data CappedList cap a = Next a (CappedList cap a) | Cap cap
Since uploading, there's been a big problem pointed out to me regarding this structure, namely the possible definitions of |append|. Because the list terminus is itself a value, but isn't / shouldn't be the same type as the elements, either obvious implementation will drop it.
append :: CappedList cap a -> CappedList cap a -> CappedList cap a append (Cap 0) (Cap 1) = -- either (Cap 0) or (Cap 1), but information has been lost
For exception handling I need append :: CappedList (Maybe exception) a -> CappedList (Maybe exception) a -> CappedList (Maybe exception) a where 'append' appends the second list only, if the first list did not end with an exception.
participants (6)
-
David Menendez -
Felipe Lessa -
Henning Thielemann -
John Millikin -
Nicolas Pouillard -
Twan van Laarhoven