iteration over elements of a list vs iterations over cons cells

[Jim Newton]

In Lisp there are two common mapping functions for iterating over lists, mapcar and maplist. The mapcar function corresponds to the Scala map function, but there does not seem to be an equivalent of maplist in Scala, although it is not difficult to create one for lists as follows.

def maplist[T,U](seq:List[T],client:(List[T]=>U)):List[U] = {
  def loop(rest:List[T], acc:List[U]):List[U] = rest match {
    case Nil => acc
    case _::tail => loop(tail,client(rest)::acc)
  }
  loop(seq,Nil).reverse
}

maplist does not iterate over the elements as such, but rather iterates over the cons cells.  Thus at each iteration you can look t the head and tail to see the current element and the elements to come.

My question concerns the marriage of for expressions map.   And expression such as

  for { x <- List(1,2,3) ; y <- List(10,20,30) } yield List(x,y)

will collect all paris of one element from the first list and one element from the second list.  But if the two given lists are the same

there will be duplicates making the loop do twice as much work as necessary and allocate twice as much memory as necessary.  This duplication is because iteration is done via map rather than maplist.

Can I somehow extend for so that I can use my own syntax, e.g., <::- to indicate that I want to use maplist rather than map?  I.e., first iteration x=List(1,2,3), second x=List(2,3), finally x=List(3).

for { x <::- List(1,2,3) ; y <- x } yield List(x.head,y)

And if I want to eliminate the elements List(1,1), List(2,2), and List(3.3) I could do the following:

for { x <::- List(1,2,3) ; y <- x.tail } yield List(x.head,y)

Of course I'd also have to apply a flatMap analog to maplist, which is not so difficult to do.  Albeit perhaps a challenge to do efficiently, admittedly the following has the problem that lists are reversed twice in order to make it purely functional.

def mapcon[T,U](seq:List[T],client:(List[T]=>List[U])):List[U] = {
  def loop(rest:List[T], acc:List[U]):List[U] = rest match {
    case Nil => acc
    case _::tail => loop(tail,client(rest).reverse++acc)
  }
  loop(seq,Nil).reverse
}

The other way to do this might be to define a subtype of List[T] called ListPrime[T], and therein override map and maplist.   Perhaps it's a more Scala-ish way to do it, but I'm not sure what the hidden consequences would be of overriding map and flatMap especially if my class inherits from List[T].

I'd love to hear anyone's comments on this.  It it a problem that for does not let you describe how iteration should occur?  And is it possible/safe to override map and flatMap on subclasses of List?

[Seth Tisue]

On Tuesday, July 12, 2016 at 3:13:12 AM UTC-7, Jim Newton wrote:
> In Lisp [...]

greetings fellow Lisp refugee!

> maplist does not iterate over the elements as such, but rather iterates over the cons cells. Thus at each iteration you can look t the head and tail to see the current element and the elements to come.

In Scala I would use `tails` for this:

scala> List.range(1, 5).tails.map(_.sum).toList
res1: List[Int] = List(10, 9, 7, 4, 0)

> Can I somehow extend for so that I can use my own syntax

No. (Well, unless you write a compiler plugin or something, but that's really hard.)

> It it a problem that for does not let you describe how iteration should occur?

No, I've always found satisfactory alternatives. I find processing lists (and collections in general) to be at least in pleasant in Scala as in Common Lisp, often more so.

> And is it possible/safe to override map and flatMap on subclasses of List?

It is absolutely not recommended to subclass List at all for any reason.

If you want to be able to use a method such as `maplist` in your code, add it as an extension method. See http://stackoverflow.com/questions/3119580/scala-equivalent-of-c-s-extension-methods

[Jim Newton]

Hi Seth, thanks for the insightful response.   Can I ask you some follow up questions?

greetings fellow Lisp refugee!

Yes, there seems to be lots of assumptions in most scala literature that a person knows java.  Often it seems that a lisp background helps more than a java background, of course discounting the familiarity with java libraries, and ability to use eclipse and intelliJ.

I often wonder whether after learning Scala, do I need to go back and learn some about Java?  I fear the pain, however, learning the javaVM might be useful.   What's your recommendation?

> maplist does not iterate over the elements as such, but rather iterates over the cons cells. Thus at each iteration you can look t the head and tail to see the current element and the elements to come.

In Scala I would use `tails` for this:

scala> List.range(1, 5).tails.map(_.sum).toList
res1: List[Int] = List(10, 9, 7, 4, 0)

You suggest to use List.range(1, 5).tails.map(_.sum).toList

Does this generate a list of 5 integers, and then generate a list of 5 lists?   If not why not?  What magical optimization prevents it?

Some of the chained operators I see in lots of scala examples make me afraid that lots of extraneous lists are getting created that I don't want.

 

> Can I somehow extend for so that I can use my own syntax

No. (Well, unless you write a compiler plugin or something, but that's really hard.)

> It it a problem that for does not let you describe how iteration should occur?

No, I've always found satisfactory alternatives. I find processing lists (and collections in general) to be at least in pleasant in Scala as in Common Lisp, often more so.

> And is it possible/safe to override map and flatMap on subclasses of List?

It is absolutely not recommended to subclass List at all for any reason.

Hmmm, this is a very tempting verbote.   I feel like a child who's forbidden to do something now.  All I want to do is try it.    Will trying to do it be insightful as to why it should be avoided?

 

If you want to be able to use a method such as `maplist` in your code, add it as an extension method. See http://stackoverflow.com/questions/3119580/scala-equivalent-of-c-s-extension-methods

But adding as an extension method won't solve the problem; i.e., for(x<-y ...) will still use map, and not maplist.  Right?

Kind regards

[Simon Ochsenreither]

You suggest to use List.range(1, 5).tails.map(_.sum).toList

Does this generate a list of 5 integers, and then generate a list of 5 lists?   If not why not?  What magical optimization prevents it?

It does, but it shouldn't do that. If others agree, you should definitely file a bug about it!

[Seth Tisue]

On Thursday, August 4, 2016 at 1:34:36 AM UTC-7, Jim Newton wrote:
> I often wonder whether after learning Scala, do I need to go back and learn some about Java? I fear the pain, however, learning the javaVM might be useful. What's your recommendation?

Most Scala programmers consume Java-based libraries, so it helps to be able to read Java well enough to read method signatures in Javadoc. I really don’t think it’s necessary to actually write any Java code. JVM knowledge is definitely helpful, but you can pick that up as you work in Scala (IMO).

> Some of the chained operators I see in lots of scala examples make me afraid that lots of extraneous lists are getting created that I don't want.

You can use views to avoid this (though they have a number of design and implementation shortcomings and are long overdue for an overhaul). You can also use Iterator; that’s normally what I would do if I wanted to be sure not to generate garbage. In ordinary code, though, I wouldn’t worry about it all; the JVM is really good at efficiency GC’ing short-lived objects.

> > It is absolutely not recommended to subclass List at all for any reason.

> Hmmm, this is a very tempting verbote. I feel like a child who's forbidden to do something now. All I want to do is try it. Will trying to do it be insightful as to why it should be avoided?

Well, scala.collection.immutable.List in particular is declared as sealed. But supposing we're not just talking about that one in particular:

The first problem you hit with “class MyCollectionType extends BuiltInCollection” is that operations on MyCollectionType will return a BuiltInCollection rather a MyCollectionType. For an idea of what’s involved with defining your own collection type correctly, see e.g. http://daily-scala.blogspot.com/2010/04/creating-custom-traversable.html

If you want to be able to use a method such as `maplist` in your code, add it as an extension method. See e.g. http://stackoverflow.com/questions/3119580/scala-equivalent-of-c-s-extension-methods

> But adding as an extension method won't solve the problem; i.e., for(x<-y ...) will still use map, and not maplist. Right?

correct

Seth Tisue / Scala team / Lightbend, Inc.

[Jim Newton]

I noticed a function called "scan" which is very similar to maplist, but does a fold rather than a mapping.

Although I didn't quickly find documentation for this function.  It seems to call fold effectively N/2 times on the

leading (scanLeft) prefixes or trailing (scanRight) suffixes.

Does someone have examples of using these functions?  Are they in the standard scala library, or are they provided by shapeless?