typelevel/general

General topics relating to the the Typelevel project http://typelevel.org/ | See also individual project channels | Code of conduct https://www.scala-lang.org/conduct/

Adam Rosien

@arosien

@AaronDelaplane no it is not. it is evaluated for every element of the source list

Aaron Delaplane

@AaronDelaplane

Is the word "memoized" appropriate here? As in the inner expression is not "memoized"...

Adam Rosien

@arosien

yes

Aaron Delaplane

@AaronDelaplane

Thanks. That surprises me

Adam Rosien

@arosien

i'm surprised you are surprised! :) i don't know of any language which would memoize something like that

Aaron Delaplane

@AaronDelaplane

Oh, ok. Good to know.

Guillaume Martres

@smarter

it's clearer if you see that List(1,3,5).map(intList.filter(_ > 4).contains) expands to List(1,3,5).map(x => intList.filter(_ > 4).contains(x))

so the thing being passed to map is just a lambda

Aaron Delaplane

@AaronDelaplane

Ah, yeah

Adam Rosien

@arosien

i am genuinely curious though, not trying to be dismissive! we humans definitely know the filter could be memoized.

and there are all sorts of optimizations the computer could do, but we don't have access to it.

like maybe the JVM can do it, but we won't know.

unless you are @smarter, of course :)

i guess i mean, the language doesn't do it, but the runtime might. so it depends on what you mean when you say you are surprised.

Aaron Delaplane

@AaronDelaplane

I didn't take that way at all, but thanks. I guess perhaps I thought the function which accepts the lambda's argument (the .contains(x) bit) would not be memoized but that the pure expression preceding it because it is not waiting on any further arguments would.

I mean, obviously, you could not memoize the .contains(_)...

Aaron Delaplane

@AaronDelaplane

Oh, wait, @arosien my question, which I didn't clarify, was meant in the context of the runtime... Isn't that the only thing here that matters when determining whether this expression can be included in the call to .map or must be put outside of it in order to avoid n evaluations for a list of n items being mapped over.

This perhaps is clearer:

  val intList = List(1,2,3,4,5,6,7)

  def fn(xs: List[Int]) =
   List(1,3,5).map(xs.filter(_ > 4).contains)

  fn(intList)

What I'm trying to determine is if the fn function above is the same as the fn function below at runtime:

  def fn(xs: List[Int]) = {
    val filtered = xs.filter(_ > 4)
    List(1,3,5).map(filtered.contains)
  }

I assumed it was

Adam Rosien

@arosien

it depends on what you mean by "the same". :) by substitution, they mean the same thing (they produce the same answer). but their execution is different

but those are two excellent examples that let you (hopefully) see that. extracting sub-expressions shouldn't change the meaning of our programs, hopefully.

Aaron Delaplane

@AaronDelaplane

Right. By "same", I mean the expression in both is only evaluated once. In each, the expression xs.filter(_ > 4) is evaluated once

Adam Rosien

@arosien

if you wrote it as xs.filter { x => println(x); x > 4 } you can see if that is true or not

Aaron Delaplane

@AaronDelaplane

Indeed. Yeah, thanks.

Adam Rosien

@arosien

the key though is what @smarter said, if you write out the map with an explicit lambda you'll see "when" the filter is executed. without the lambda it may look like the argument to map is evaluated before map is called, but it really isn't.

now i'm paranoid and need to check myself

Aaron Delaplane

@AaronDelaplane

List(1,2,3).map(x => List(1,2,3,4,5).filter(x => {
    println("hi");
    x > 3
  }).contains(x))

Adam Rosien

@arosien

this smells like an odersky exercise

Aaron Delaplane

@AaronDelaplane

15 lines are printed out, thus confirming my need to read more:)

Adam Rosien

@arosien

ah write it without the first x lambda

this is great. i was wrong! :)

List(1,2,3).map(List(1,2,3,4,5).filter(x => {
    println("hi");
    x > 3
  }).contains)

hi
hi
hi
hi
hi

it is "memoized", but only due to evaluation order

i hope to regain my credibility by being very happy with being wrong :)

Aaron Delaplane

@AaronDelaplane

Right. I think I thought this because of Odersky's video on the substitution principle, which I watched years ago.

Adam Rosien

@arosien

yes exactly

we defeated somebody who works on scala at EPFL! winning! :P

that is, this stuff is easy to get wrong

Aaron Delaplane

@AaronDelaplane

@arosien Thanks for the help. I feel much less depressed than I did 10 mins ago:)

Adam Rosien

@arosien

success :)

Guillaume Martres

@smarter

ah yeah, eta-expansion does lift the receiver to a separate val

(it's easy to check in the scala 2 repl by typing the expression followed by " // print" followed by pressing TAB to see the generated typechecked tree)

Guillaume Martres

@smarter

now the fun part is that if you write List(1,2,3).map(List(1,2,3,4,5).filter(x => {println("hi"); x > 3}).contains(_)) you'll see it print hi 15 times :)

that's the desugaring I was thinking about

Seth Tisue

@SethTisue

@ChristopherDavenport have you seen https://github.com/debasishg/effRedis ? maybe you and Debasish should be collaborating

Adam Rosien

@arosien

i already bugged him :P

https://twitter.com/debasishg/status/1294335237070061570

but together we can bug even more people

Seth Tisue

@SethTisue

ah :+1:

Where communities thrive

People

Repo info

Activity