[Haskell-cafe] beginner's problem about lists

Duncan Coutts duncan.coutts at worc.ox.ac.uk
Wed Oct 11 07:50:32 EDT 2006

On Wed, 2006-10-11 at 11:40 +0100, Malcolm Wallace wrote:
> ihope <ihope127 at gmail.com> wrote:
> > It's possible to make both "infinite list" and "finite list"
> > datatypes:
> > 
> > data Inf a = InfCons a (Inf a)
> > data Fin a = FinCons a !(Fin a) | FinNil
> > 
> > At least, I think the Fin type there has to be finite...
> No, your Fin type can also hold infinite values.  The strictness
> annotation on the (Fin a) component merely ensures that the tail exists
> to one constructor's depth (Head Normal Form).  It does not force
> strictness all the way down (full Normal Form).

Are you sure?

Since it does it recursively, if each cons ensures that it has a tail.
Then that tail must be Nil or Cons (since we know it can't be _|_), and
if it's Cons...

It's not full normal form of course because it's not strict in the list
elements, but it is spine strict all the way down.

longList 0 = undefined
longList n = n : longList (n-1)

case longList 3 of n : _ -> n

longFin 0 = undefined
longFin n = n `FinCons` longFin (n-1)

case longFin 3 of FinCons n _ -> n
*** Exception: Prelude.undefined

Or am I really confused?


More information about the Haskell-Cafe mailing list