New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

`LazyList`'s `last` method (and perhaps others?) should be lazier #11089

Closed
SethTisue opened this Issue Aug 17, 2018 · 15 comments

Comments

Projects
None yet
4 participants
@SethTisue
Copy link
Member

SethTisue commented Aug 17, 2018

scala> def ll() = { var counter = 0 ; LazyList.continually{println(counter); counter += 1; counter} }
ll: ()scala.collection.immutable.LazyList[Int]

scala> ll()(5)
0
res9: Int = 1

scala> ll().take(5).last
0
1
2
3
4
res10: Int = 5

reported by @paulp at https://twitter.com/contrarivariant/status/1030065587559362561

are there other methods that may have this problem?

related: #11083

/cc @NthPortal @szeiger @julienrf


methods to fix:

  • last
  • dropRight
  • takeRight
  • slice

@SethTisue SethTisue added this to the 2.13.0-RC1 milestone Aug 17, 2018

@SethTisue

This comment has been minimized.

Copy link
Member

SethTisue commented Aug 17, 2018

@szeiger writes:

There should be a LinearSeq#last that only looks at the tails, not the heads along the way

@SethTisue

This comment has been minimized.

Copy link
Member

SethTisue commented Aug 17, 2018

as @szeiger indicates, there is a fundamental mismatch between the semantics of Iterator (always evaluates all traversed elements) and LazyList (can evaluate tail without evaluating head)

@paulp

This comment has been minimized.

Copy link

paulp commented Aug 17, 2018

Those were the first methods I thought to try, so probably it's safe to say there are more examples.

scala> def ll = (1 to 10).foldRight(LazyList[Int]())((x, xs) => (try x finally println(x)) #:: xs)
ll: scala.collection.immutable.LazyList[Int]

scala> ll.length
res3: Int = 10

scala> LazyList.fill(3)(try 1 finally println(1)).length
1
1
1
res4: Int = 3

@SethTisue SethTisue changed the title `LazyList#last` should be lazier `LazyList#last`, `length` (and others?) should be lazier Aug 17, 2018

@SethTisue SethTisue changed the title `LazyList#last`, `length` (and others?) should be lazier `LazyList#last` should be lazier Aug 17, 2018

@SethTisue SethTisue changed the title `LazyList#last` should be lazier `LazyList`'s `last` and `length` methods, and probably others, should be lazier Aug 17, 2018

@sjrd

This comment has been minimized.

Copy link
Member

sjrd commented Aug 17, 2018

as @szeiger indicates, there is a fundamental mismatch between the semantics of Iterator (always evaluates all traversed elements) and LazyList (can evaluate tail without evaluating head)

Maybe the head of LazyList shouldn't be lazy after all, as I initially suggested at scala/scala#6880 (comment):

As added food for thought: I wonder whether it is still useful that the head be lazy. Are there use cases where one already knows that the lazy list is non-empty, but doesn't know yet what its head will be (and cannot synchronously compute it)? My experience from programming in Oz (where this lazier LazyList is basically the base data type used everywhere--and optimized by the VM) doesn't support any such use case. [...]

@paulp

This comment has been minimized.

Copy link

paulp commented Aug 17, 2018

@sjrd I had the impression that a non-lazy head is the entire reason for this class's existence. With an eager head, isn't it Stream?

@sjrd

This comment has been minimized.

Copy link
Member

sjrd commented Aug 17, 2018

No. The biggest difference between my alternative proposal and Stream is that (non-)emptiness is lazy. So you can hold a LazyList for which you haven't decided yet whether it's going to be empty or not. But once you ask for that info, and it happens to be non-empty, then you eagerly evaluate the head, whereas the current LazyList can decide that it is non-empty but still defer the evaluation of head later.

I strongly believe that the years-old complaint about Stream that "it is not lazy in the head" was actually a mischaracterization of the fact that "it is not lazy in its (non-)emptiness". Because what people typically see for Stream is that they can't create an instance of Stream without evaluating the head. But you can do that even if the head is eager, as long as (non-)emptiness is lazy.

See also scala/collection-strawman#367

@paulp

This comment has been minimized.

Copy link

paulp commented Aug 17, 2018

@sjrd I always thought the way to deal with this was to propagate what is known about the size, as seen here. But I suppose that's neither here nor there.

/** The Size hierarchy is:
  *                     Size
  *                  /        \
  *               Atomic     Bounded
  *              /      \
  *          Infinite  Precise
  *
  *  Precise implies the exact size is known. Infinite means it's infinite.
  *  Bounded is a size lower bound and a (possibly infinite) atomic upper bound.
  *  Size forms a partial order, with some liberties taken at present.
  *  Operations on sizes which are ill-defined will result in "Unknown", which
  *  encodes no available size information: Bounded(Zero, Infinite).
  *
  *  Invariants:
  *  - Precise is non-negative
  */
@sjrd

This comment has been minimized.

Copy link
Member

sjrd commented Aug 17, 2018

Hum ... I'm not sure how that is relevant, except that:

  • For Stream, sizes of the shape Bounded(>= 0) would never happen, because they are not representable. A Stream is either known to be empty (size 0) or it is known to be non-empty (Infinite, Precise, or Bounded(>= N) for N >= 1).
  • With my suggestion, the state where the size would be Bounded(>= 0) is representable.
@paulp

This comment has been minimized.

Copy link

paulp commented Aug 17, 2018

It's relevant because... never mind, it's irrelevant.

@NthPortal NthPortal self-assigned this Aug 17, 2018

@NthPortal

This comment has been minimized.

Copy link

NthPortal commented Aug 17, 2018

for tracking purposes, can people add a list of methods that need more laziness to the description?

@NthPortal

This comment has been minimized.

Copy link

NthPortal commented Aug 18, 2018

@SethTisue length seems sufficiently lazy to me already

@SethTisue SethTisue changed the title `LazyList`'s `last` and `length` methods, and probably others, should be lazier `LazyList`'s `last` method (and perhaps others?) should be lazier Aug 18, 2018

@SethTisue

This comment has been minimized.

Copy link
Member

SethTisue commented Aug 18, 2018

@NthPortal okay I changed the ticket name again :-)

@NthPortal

This comment has been minimized.

Copy link

NthPortal commented Sep 6, 2018

There are other methods that got missed that aren't sufficiently lazy. I am in the middle of fixing them, and will try to add them to the description soon. If you find any other methods, please add them to the description as well or drop a comment.

@NthPortal NthPortal reopened this Sep 6, 2018

@NthPortal

This comment has been minimized.

Copy link

NthPortal commented Sep 6, 2018

Tentatively leaving #11083 closed for now, but that may end up getting reopened as well.

@NthPortal

This comment has been minimized.

Copy link

NthPortal commented Dec 16, 2018

Note: this may be reverted by #11307

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment