I wrote:
> For the same reasons, length [1..n] does not run in constant space.
Forget that. In this case, any reasonable implementation of course
evaluates the elements (to see if the end of the list is
reached). Thanks to Niklas R=F6jemo who pointed it out.
/M
My complete post:
> The problem is that the elements in the list [1..] are not used by
> the function lens, so they will not be evaluated. This is fatal, since
> the unevaluated elements are becoming larger and larger function appli=
cations:
>=20
> [1..] =3D [1, 1+1, 1+1+1, ...]
>=20
> For the same reasons, length [1..n] does not run in constant space.
>=20
> By using a more strict definition of [1..], the space leak disappears:
>=20
> > myFrom n =3D if n =3D=3D n then t else t where t =3D n : myFrom (n+1=
)
>=20
> > main =3D interact(("Enter stride: "++). unwords . map show .
> > (flip lens)(myFrom 1) .
> > fst . head . readDec)
>=20
> Regards
> /Magnus
>=20
> Rex L. Page writes:
> >=20
> > length[1 .. n] seems to run in constant space (that is, space
> > independent of n), as expected.
> >=20
> > However, length[1 ..] runs out of space.
> > This doesn't seem reasonable to me.
> > =20
> > The following program, which computes length[1 ..]
> > and reports its progress after every n-th element, also runs out of
> > space, inexplicably to me.
> >=20
> > > lens n =3D everyNth n . scanl (\n _ -> n+1) 0
> >=20
> > > everyNth n =3D map head . takeWhile(not.null) . iterate(drop n)
> >=20
> > > main =3D interact(("Enter stride: "++). unwords . map show .
> > > (flip lens)[1 ..] .
> > > fst . head . readDec)
> > =20
> > With a stride of 1000, the program runs out of space=20
> > after 28,000 list elements with the default heap size in Hugs
> > on my Unix (Sun) installation, and after 164,000 list elements unde=
r ghc.
> > With larger strides, it runs out of space sooner on both Hugs and g=
hc.
> > =20
> > What's going on here? It appears to me that both length[1..] and th=
e
> > above definition of main should evaluate in constant space.
> > =20
> > Rex Page
> > [EMAIL PROTECTED]
> > School of Computer Science 405-325-4397
> > University of Oklahoma fax 405-325-4044
> > Norman OK 73019-0631
