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.fill and LazyList.tabulate aren't lazy in the head #11083

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

Comments

Projects
None yet
5 participants
@SethTisue
Copy link
Member

SethTisue commented Aug 15, 2018

for LazyList.fill, I would expect the same output in both cases here:

scala> LazyList.continually(println("hey!")).apply(4)
hey!

scala> LazyList.fill(5)(println("hey!")).apply(4)
hey!
hey!
hey!
hey!
hey!

and similarly for tabulate:

scala> import util.chaining._
import util.chaining._

scala> LazyList.from(0).map(_.tap(println)).apply(4)
4
res30: Int = 4

scala> LazyList.tabulate(5)(_.tap(println)).apply(4)
0
1
2
3
4
res32: Int = 4

perhaps there are other methods with this problem?

noticed in @paulp's gist: https://gist.github.com/paulp/fac614c6de23c10644a7af25f4ef96e4

tentatively assigning @NthPortal as this is a continuation of scala/scala#7000


methods to fix:

  • fill
  • tabulate

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

@paulp

This comment has been minimized.

Copy link

paulp commented Aug 16, 2018

None of these terminate. If this is intended to be the forever replacement for Stream, I'd think that they would. YMMV.

(LazyList from 1 dropRight 1).head
(LazyList from 1).reverse.reverse.head
(LazyList from 1 takeRight 0)
(LazyList from 1 dropRight 0)
@NthPortal

This comment has been minimized.

Copy link

NthPortal commented Aug 16, 2018

(LazyList from 1 dropRight 1).head can be fixed by scouting ahead
(LazyList from 1 takeRight 0) and (LazyList from 1 dropRight 0) can be fixed by checking for non-positive values

I'm not sure if I agree that I would expect (LazyList from 1).reverse.reverse.head to terminate, but I will think about it some more

@NthPortal

This comment has been minimized.

Copy link

NthPortal commented Aug 17, 2018

In order to have (LazyList from 1).reverse.reverse.head terminate, you would need to have a special LazyList variant representing a reversed one, so that reversing that would return the original LazyList; however, I don't personally think that makes a lot of sense.

@paulp

This comment has been minimized.

Copy link

paulp commented Aug 17, 2018

It makes enough sense that it already exists as a view:

scala> (LazyList from 1).view.reverse
res0: scala.collection.SeqView[Int] = View(?)

scala> res0.getClass
res1: Class[_ <: scala.collection.SeqView[Int]] = class scala.collection.SeqView$Reverse

But of course that doesn't work either.

scala> (LazyList from 1).view.reverse.reverse.head
[...]
@NthPortal

This comment has been minimized.

Copy link

NthPortal commented Aug 17, 2018

I will agree that reverse shouldn't evaluate the elements (even though it has to evaluate all of the states in order to reverse it).

At the very least, reverse is documented as $willNotTerminateInf.

@SethTisue

This comment has been minimized.

Copy link
Member

SethTisue commented Aug 17, 2018

I suggest spinning off the reverse/dropRight/takeRight stuff to a separate ticket; it's separate.

returning to fill and tabulate:

at https://twitter.com/StefanZeiger/status/1030056916981096449 @szeiger wrote of fill that he thought "you can use side-effects to build consecutive elements. It only makes sense if they are evaluated in order"

@szeiger are you sure? it seems to me that the possibility of out-of-order evaluation of side-effects is everywhere with LazyList, given that there are countless paths by which you can evaluate the tail without evaluating the head, yet still decide to evaluate the head later on. for example:

scala> var counter = 0
counter: Int = 0

scala> LazyList.continually{counter += 1; counter}
res10: scala.collection.immutable.LazyList[Int] = LazyList(?)

scala> res10.tail.head
res11: Int = 1

scala> res10.take(5).toList
res12: List[Int] = List(2, 1, 3, 4, 5)

why should fill be different?

to impose order dependence, we offer e.g. LazyList.iterate:

scala> import util.chaining._
import util.chaining._

scala> val ll = LazyList.iterate(0)(_.tap(println) + 1)
ll: scala.collection.immutable.LazyList[Int] = LazyList(?)

scala> ll.tail.head
0
res15: Int = 1

scala> ll.take(5).toList
1
2
3
res16: List[Int] = List(0, 1, 2, 3, 4)
@SethTisue

This comment has been minimized.

Copy link
Member

SethTisue commented Aug 17, 2018

it would be worthwhile for LazyList's Scaladoc to clearly state that not only are both head and tail lazy, they are independently lazy; evaluating the tail neither necessarily evaluates nor necessarily discards the head.

@NthPortal

This comment has been minimized.

Copy link

NthPortal commented Aug 17, 2018

The whole scaladoc probably needs to be revamped. I didn't touch it at all. I think I will tackle that last, after fixing all the other laziness problems.

Edit: or if someone else wants to, I won't stop them - it shouldn't conflict with the code

@NthPortal

This comment has been minimized.

Copy link

NthPortal commented Aug 17, 2018

wrt fill (and continually): I'm not sure how I feel about whether or not tail should force evaluation of head or not.

tabulate on the other hand, should not evaluate head when it evaluates tail. I don't expect the element generating function to be side-effecting, since it takes in an index

@NthPortal

This comment has been minimized.

Copy link

NthPortal commented Aug 18, 2018

@SethTisue do you mind if I broaden this issue to cover all factories/generators with laziness problems? (and the other issue can cover all methods on an instance of LazyList with laziness problems)

@shawjef3

This comment has been minimized.

Copy link

shawjef3 commented Aug 30, 2018

wrt fill (and continually): I'm not sure how I feel about whether or not tail should force evaluation of head or not.

It seems to me that which factory method I use should not determine the laziness.

@shawjef3

This comment has been minimized.

Copy link

shawjef3 commented Aug 30, 2018

I can see laziness being determined by a factory method when it takes a thunk vs a value. So like I'd expect LazyList(1,2,3) to be more strict because of varargs, but other methods use => T, Int => T, and so on, so I expect those to be lazy. A version of fill that is strict could be LazyList.strictFill[A](Int)(A).

@NthPortal

This comment has been minimized.

Copy link

NthPortal commented Aug 31, 2018

@shawjef3 But there are already factory methods for which tail forces evaluation of head - unfold, from(Iterator), iterate, and possibly others

@shawjef3

This comment has been minimized.

Copy link

shawjef3 commented Aug 31, 2018

@NthPortal I guess I misunderstood head to mean the value in the head and not just the node in the list.

@NthPortal

This comment has been minimized.

Copy link

NthPortal commented Sep 1, 2018

@shawjef3 I don't think it's very useful to talk about whether or not the actual head value of the node gets evaluated - only whether the eventual result of it gets evaluated. None of the factory methods will actually call head, but several will evaluate that value before creating/evaluating the next tail, either because the method is iterative (see unfold and iterate) or uses an iterator (see from(Iterator))

@szeiger

This comment has been minimized.

Copy link

szeiger commented Sep 7, 2018

My argument for fill to keep evaluating in order was that side-effects are the only way to use it, unless you want to produce equivalent values for every element. A version of fill that produces values in an undefined or at least difficult to know (and keep correct) order (i.e. the evaluation order) seems much less useful to me.

@SethTisue

This comment has been minimized.

Copy link
Member

SethTisue commented Sep 10, 2018

hmm, that seems rather convincing, actually. @NthPortal what do you think?

@NthPortal

This comment has been minimized.

Copy link

NthPortal commented Sep 10, 2018

I'm torn. On the one hand, the argument is convincing to me as well. On the other hand, the only side effects I've seen it used with are Random.nextThing(), for which the evaluation order doesn't (shouldn't) matter anyway (on the other hand, if it's random values, why would you specifically evaluate them out of order?). Additionally, the fact that it's by-name (as opposed to being a Function0) makes me feel like its arguments ought not to be side-effecting, and that calling it with Random.nextInt() is actually a bit "wrong".

On the whole though, I think I agree with @szeiger (and the same for continually)

@NthPortal

This comment has been minimized.

Copy link

NthPortal commented Sep 16, 2018

Reopening this issue to return fill and continually to less lazy semantics

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