On 26/11/2015, at 8:00 am, Silvio Frischknecht
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.