[Haskell-cafe] Capped lists and |append|
jmillikin at gmail.com
Fri Jan 8 18:38:15 EST 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
which showed up in a thread I posted regarding lazy error handling
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
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.
More information about the Haskell-Cafe