[Haskell-cafe] Info about List with terminal element

[Richard A. O'Keefe]

On 26/11/2015, at 8:00 am, Silvio Frischknecht <silvio.frischi at gmail.com> wrote:
> I'm interested in learning more about a list-like structure with a
> terminal element. I.e.
> 
> data List t e = Cons e (List t e) | Null t
> 
> or maybe
> 
> data List t e = Cons e (List t e) | Null | Terminal t

> Are there more interesting generalizations of List?

There are unrolled lists.
http://www.cs.otago.ac.nz/staffpriv/ok/Ursl.hs
is "Unrolled Strict Lists", something I wrote many years
ago when learning Haskell.

There's a data structure that makes reverse and append
unit time.

Okasaki's "Functional Data Structures" book has some
interesting variations.

        "An Applicative Random-Access Stack"
        Eugene W. Myers
        TR 83-9, Dept of CS, University of Arizona.

gives a data structure with O(1) empty, push, pop, top,
and length, and O(lg(length)) indexing.