[Haskell-cafe] Info about List with terminal element

[Silvio Frischknecht]

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
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

[Silvio Frischknecht]

> readFile :: String -> List Error String

should have been

readFile :: String -> IO (List Error String)

[David Kraeutmann]

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).

[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

[David Kraeutmann]

Oh, sorry. Yes, I missed the t. Thanks for clearing it up.

[Tom Ellis]

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

[Richard A. O'Keefe]

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

[Silvio Frischknecht]

>> 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'

Silvio

[Daniel Díaz]

The type

Cofree (Either t) e

is isomorphic to a non-empty version of 

List t e 

[Tom Ellis]

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

[Silvio Frischknecht]

On 26.11.2015 21:35, Daniel Díaz wrote:
> The type
>
> Cofree (Either t) e
>
>
> is isomorphic to a non-empty version of
>
> List t e

Thanks. This is exactly the kind of thing I was looking for.