Alex Rivera | Logout

Haskell: Lists vs Streams

Asked 2012-06-08T02:42:51.367
24

I've noticed streams seem to act a lot like lists, except with constant time append. Of course, adding constant time append to lists isn't too complicated, and DList does exactly that.

Lets assume for the rest of the discussion that either lists have constant time append, or that we're simply not interested in it.

My thought is that Haskell lists should simply be implemented as streams. For this not to be the case, I assume that the following would need to hold:

  1. There are cases where lists are better than streams AND
  2. There are cases where streams are better than lists.

My question is: what are examples of the two above cases?

Note: For the purpose of this question, please ignore easily fixable omissions in the particular implementations I've discussed. I'm looking more for core structural differences here.

Additional info:

I guess part of what I'm getting at here is say if we write [1..1000000], does a Haskell compiler (say GHC) do:

  1. Make a list OR
  2. Make an object with two ints: 1 and 1000000 which fully describes the list.

If it's case (1), why do this, as creating intermediate lists seems to be an unnecessary performance penalty?

Or if it's case (2), then why do we need streams?

list haskell stream
Edit
Report

1 Answer

9

The advantage of streams is they are more powerful. The interface:

data Stream m a = forall s . Stream (s -> m (Step s a)) s Size

lets you do many things that normal lists cannot. Eg:

  • Track the size (eg Unknown, Max 34, Exact 12)
  • Perform monadic actions to get the next element. Lists can partly do this with lazy IO, but that technique has proved to be error prone, and normally is only used by beginners, or for simple small scripts.

However, they have a big downside as compared to lists - complexity! For a beginner programmer, to understand streams you have to be on top of existential types and monadic actions. It would be very hard to learn haskell if to use the basic list type you had to learn those two complex subjects.

Compare that to lists, which have the interface:

data [] a = a : [a] | []

This is very simple, and something that can be taught easily to a new programmer.

Another advantage of lists is you can pattern match them simply. For example:

getTwo (a : b : _) = Just (a,b)
getTwo _ = Nothing

This is both useful to experienced programmers (I still use list pattern matching in many methods), and for beginner programmers who haven't yet learnt the standard higher order functions that can be used to manipulate lists.

Efficiency is also another potential advantage of lists, since ghc has spent a lot of time working on list fusion. In a lot of code, intermediate lists are never generated. That could be a lot harder to optimize with streams.

So I think it would be a poor choice to swap lists with Streams. The current situation is better, where you can bring them in if you need them, but beginners aren't stuck with their complexity and skilled users don't have to lose pattern matching.

EDIT: about [1..1000000]:

This is equivalent to enumFromTo 1 10000

answered 2012-06-08T03:33:51.043

Your Answer