[Haskell-cafe] Capped lists and |append|

[David Menendez]

On Fri, Jan 8, 2010 at 6:38 PM, John Millikin <jmillikin at gmail.com> 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.
>
> 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 <dave at zednenem.com>
<http://www.eyrie.org/~zednenem/>