[Haskell-cafe] Info about List with terminal element
Richard A. O'Keefe
ok at cs.otago.ac.nz
Thu Nov 26 05:19:58 UTC 2015
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.
is "Unrolled Strict Lists", something I wrote many years
ago when learning Haskell.
There's a data structure that makes reverse and append
Okasaki's "Functional Data Structures" book has some
"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.
More information about the Haskell-Cafe