Вырубка лесов в коллекциях Scala - PullRequest
Новая
       23

Вырубка лесов в коллекциях Scala

5 голосов
/ 21 ноября 2011

Из дизайна коллекций Scala я понимаю, что что-то вроде: 

scala> BitSet(1,2,3) map (_ + "a")
res7: scala.collection.immutable.Set[String] = Set(1a, 2a, 3a)

не создает промежуточную структуру данных: новый набор создается, поскольку BitSet итерируется с использованием Builder.На самом деле в этом случае это очевидно, поскольку набор строк не имеет смысла.

А как насчет карт из списков?Я почти уверен, что следующее строит промежуточный список: 

scala> List(1,2,3) map (_ -> "foo") toMap
res8: scala.collection.immutable.Map[Int,java.lang.String] =
    Map(1 -> foo, 2 -> foo, 3 -> foo)

, а именно список List((1,foo), (2,foo), (3,foo)).Если нет, то как?Теперь, как насчет следующего? 

scala> Map.empty ++ (List(1,2,3) map (_ -> "foo"))
res10: scala.collection.immutable.Map[Int,java.lang.String] =
    Map(1 -> foo, 2 -> foo, 3 -> foo)

На этот раз из того, что я, кажется, понимаю из типа ++: 

def ++ [B >: (A, B), That]
       (that: TraversableOnce[B])
       (implicit bf: CanBuildFrom[Map[A, B], B, That]): That

Я думаю возможно, карта построена на лету, а промежуточный список не составлен.

Так ли это?Если да, является ли это каноническим способом обеспечения обезлесения или существует более простой синтаксис?

Ответы [ 2 ]

14 голосов
/ 21 ноября 2011

Вы можете использовать breakOut, чтобы убедиться, что промежуточная коллекция не создана. Например: 

// creates intermediate list.
scala> List((3, 4), (9, 11)).map(_.swap).toMap 
res542: scala.collection.immutable.Map[Int,Int] = Map(4 -> 3, 11 -> 9)

scala> import collection.breakOut
import collection.breakOut

// doesn't create an intermediate list.
scala> List((3, 4), (9, 11)).map(_.swap)(breakOut) : Map[Int, Int]
res543: Map[Int,Int] = Map(4 -> 3, 11 -> 9)

Подробнее об этом можно прочитать здесь .

UPDATE:

Если вы прочитаете определение breakOut, вы заметите, что это в основном способ создания CanBuildFrom объекта ожидаемого типа и явной передачи его методу. breakOut просто спасает вас от ввода следующего шаблона. 

// Observe the error message. This will tell you the type of argument expected.
scala> List((3, 4), (9, 11)).map(_.swap)('dummy)
<console>:16: error: type mismatch;
 found   : Symbol
 required: scala.collection.generic.CanBuildFrom[List[(Int, Int)],(Int, Int),?]
              List((3, 4), (9, 11)).map(_.swap)('dummy)
                                                ^

// Let's try passing the implicit with required type.
// (implicitly[T] simply picks up an implicit object of type T from scope.)
scala> List((3, 4), (9, 11)).map(_.swap)(implicitly[CanBuildFrom[List[(Int, Int)], (Int, Int), Map[Int, Int]]])
// Oops! It seems the implicit with required type doesn't exist.
<console>:16: error: Cannot construct a collection of type Map[Int,Int] with elements of type (Int, Int) based on a coll
ection of type List[(Int, Int)].
              List((3, 4), (9, 11)).map(_.swap)(implicitly[CanBuildFrom[List[(Int, Int)], (Int, Int), Map[Int, Int]]])

// Let's create an object of the required type ...
scala> object Bob extends CanBuildFrom[List[(Int, Int)], (Int, Int), Map[Int, Int]] {
     |   def apply(from: List[(Int, Int)]) = foo.apply
     |   def apply() = foo.apply
     |   private def foo = implicitly[CanBuildFrom[Nothing, (Int, Int), Map[Int, Int]]]
     | }
defined module Bob

// ... and pass it explicitly.
scala> List((3, 4), (9, 11)).map(_.swap)(Bob)
res12: Map[Int,Int] = Map(4 -> 3, 11 -> 9)

// Or let's just have breakOut do all the hard work for us.
scala> List((3, 4), (9, 11)).map(_.swap)(breakOut) : Map[Int, Int]
res13: Map[Int,Int] = Map(4 -> 3, 11 -> 9)
3 голосов
/ 21 ноября 2011

Пример 1) Правильно, промежуточного списка нет

2) Да, вы получите промежуточный список.

3) Опять же, да, вы получаете промежуточный список из того, что у вас есть в скобках. Там не происходит никакой "магии". Если у вас есть что-то в скобках, оно оценивается первым.

Я не уверен, что вы имеете в виду под "вырубкой лесов": согласно Википедии это означает устранение древовидных структур. Если вы хотите исключить промежуточные списки, вы должны использовать view . Смотрите, например, здесь: суммирование преобразования списка чисел в scala

Так что без промежуточных результатов ваши примеры будут 

BitSet(1,2,3).view.map(_ + "a").toSet

(toSet требуется, потому что в противном случае у вас есть IterableView[String,Iterable[_]]) 

List(1,2,3).view.map(_ -> "foo").toMap

Map.empty ++ (List(1,2,3).view.map(_ -> "foo"))

Существует также force метод для выполнения операций преобразования, но это, кажется, имеет неприятную привычку возвращать вам более общий тип (возможно, кто-то может прокомментировать причину): 

scala> Set(1,2,3).view.map(_ + 1).force
res23: Iterable[Int] = Set(2, 3, 4)
...