Info about List with terminal element
Hello, 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 An practical application could be lazy reading from a file readFile :: String -> List Error String Obviously there is a Functor instance. There is even a Monad instance. However, it is not defined as obviously because it's not clear what the terminal element should be. There is a straight forward fold like structure. My questions are. Are there more interesting generalizations of List? What rules do they follow? How should the Monad work? Why? I know this is related to the whole Iteratee discussion (I'm not completely familiar with it). Cheers Silvio
I'm not quite sure I understand the purpose of this structure. As far as I can tell, it's isomorphic to list (even under laziness) with some minor differences in performance characteristics (determining whether a cons cell is terminal requires evaluating the subsequent list to WHNF, whereas in your structure it follows from the constructor. But I think that's just a minor performance detail). On 11/25/2015 8:04 PM, Silvio Frischknecht wrote:
readFile :: String -> List Error String
should have been
readFile :: String -> IO (List Error String) _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
On 25.11.2015 20:38, David Kraeutmann wrote:
I'm not quite sure I understand the purpose of this structure. As far as I can tell, it's isomorphic to list (even under laziness) with some minor differences in performance characteristics (determining whether a cons cell is terminal requires evaluating the subsequent list to WHNF, whereas in your structure it follows from the constructor. But I think that's just a minor performance detail).
I think you misunderstand the structure. It is just a list that has an element of a type t at the end. It might not terminate. data List t e = Cons e (List t e) | Null | Terminal t data List t e = Cons e (List t e) | Null t are somewhat similar to ([e],Maybe t) ([e],t) respectively. but it is guaranteed that all cons of [e] are evaluated before t can be touched. Silvio
Oh, sorry. Yes, I missed the t. Thanks for clearing it up.
On Wed, Nov 25, 2015 at 9:47 PM, Silvio Frischknecht
On 25.11.2015 20:38, David Kraeutmann wrote:
I'm not quite sure I understand the purpose of this structure. As far as I can tell, it's isomorphic to list (even under laziness) with some minor differences in performance characteristics (determining whether a cons cell is terminal requires evaluating the subsequent list to WHNF, whereas in your structure it follows from the constructor. But I think that's just a minor performance detail).
I think you misunderstand the structure. It is just a list that has an element of a type t at the end. It might not terminate.
data List t e = Cons e (List t e) | Null | Terminal t data List t e = Cons e (List t e) | Null t
are somewhat similar to
([e],Maybe t) ([e],t)
respectively.
but it is guaranteed that all cons of [e] are evaluated before t can be touched.
Silvio _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
On Wed, Nov 25, 2015 at 08:00:32PM +0100, Silvio Frischknecht 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
I think this is isomorphic to Producer e Identity r https://hackage.haskell.org/package/pipes-4.1.7/docs/Pipes.html#g:2 Tom
On Thu, Nov 26, 2015 at 04:47:51PM +0100, Silvio Frischknecht wrote:
data List t e = Cons e (List t e) | Null t
I think this is isomorphic to
Producer e Identity r
Interesting. It does appear to be very similar.
Except that the Monad/Functor variable is 'r' not 'e'
Yes, I should have said isomorphic to Producer e Identity t The type parameters get arranged differently, so they will interact in different ways with the standard typeclasses, but morally I think they are the same. Tom
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.
The type Cofree (Either t) e is isomorphic to a non-empty version of List t e On Wednesday, November 25, 2015 at 8:00:40 PM UTC+1, Silvio Frischknecht wrote:
Hello,
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
An practical application could be lazy reading from a file readFile :: String -> List Error String
Obviously there is a Functor instance. There is even a Monad instance. However, it is not defined as obviously because it's not clear what the terminal element should be. There is a straight forward fold like structure.
My questions are.
Are there more interesting generalizations of List? What rules do they follow? How should the Monad work? Why?
I know this is related to the whole Iteratee discussion (I'm not completely familiar with it).
Cheers
Silvio _______________________________________________ Haskell-Cafe mailing list Haskel...@haskell.org javascript: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
participants (5)
-
Daniel Díaz -
David Kraeutmann -
Richard A. O'Keefe -
Silvio Frischknecht -
Tom Ellis