пятница, 14 сентября 2012 г.

Мысли о структуре данных приложения, проблеме "старого состояния" + ненавязчивое введение в Scala

Здесь я попробую изложить имеющиеся мысли о такой нелёгкой задаче как построение гибкой модели предметной области, а если более конкретно, то о множественных связях внутри такой модели. В качестве языка программирования будет использован статически типизированный язык Scala. Scala выбрана мной, как и множеством именитых компаний, из-за её мощной системы типов (впрочем не такой мощной как у Haskell, но намного мощнее чем, например, у Java) и практичности использования. Изложение попробую вести так, чтобы было понятно даже тем, кто Java помнит с трудом, не говоря уже о Scala. Впрочем получится у меня или нет - посмотрим.
Итак...

... в чем собственно проблема.

Пусть мы хотим смоделировать хранилище информации об исполнителях, альбомах и песнях. Следуя принципу DRY (не повторяйся), планируем использовать модель как при реализации самого хранилища, так и при реализации софта, работающего с этим хранилищем. Пусть, к примеру, для простоты, песня (Song) характеризуется названием (title), годом издания (year) и конечно же коллекцией исполнителей (artists). Уже ясно, что в нашей модели есть ещё и исполнитель (Artist). Пусть у исполнителя есть имя (name) и частная домашняя личная персональная страничка (website). Иногда песни собираются в альбомы (или в более широком смысле - в компиляции). Компиляция (Compilation) характеризуется годом выпуска, песнями (songs), которые в него входят, и конечно же названием (title). Итак, у нас вырисовались типы (с большой буквы - Song, Artist, Compilation) и их свойства (с маленькой буквы - title, website, songs, ...), напишем это все в виде кода:
    case class Artist(name: String, website: String)
(серым цветом текст для тех, кто скалу не знает)
"case class" - ключевые слова указывающие, что это объявление case class'а. По своей сути, case class - это тот же старый добрый class (прям как в Java), но с некоторым набором удобных плюшек. После ключевых слов идёт название класса (Artist) и далее, в скобочках, аргументы конструктора(!) класса. В отличии от Java, тип данных указывается после имени аргумента через двоеточие (для этого есть определённые причины, в частности, используя этот подход, вы с таким же успехом можете подсказывать компилятору правильный тип где угодно в коде, даже посреди выражения, все достаточно унифицировано). Тела у класса нет. Можно было бы конечно написать пустые фигурные скобки {}, как в Java, но тут их можно опустить. Итого, у нас есть имя класса, аргументы конструктора и все! В чем полезность такого класса? Это было бы действительно бесполезным определением, если бы не ключевое слово case. Благодаря его наличию, компилятор генерирует:
  • конструктор, который принимает два аргумента типа java.lang.String и присваивает их значения полям внутри класса
  • для каждого аргумента метод, возвращающий значение из поля объекта, т.е. будут созданы getter'ы (так как аргументы не объявлены с модификатором var, то методы для изменения значений объекты созданы не будут, об этом позже) )
  • осмысленные методы hashCode, equals, toString, использующие оба поля
Уже неплохо! Компилятор сделает за вас все то, что вы делаете сами, описывая свои модели (предметную область, доменные объекты) в Java. Но это не все. Также будет создан метод copy (про него ниже) и ещё всякое полезное... В том числе архиполезный метод для сопоставления с шаблоном (pattern matching), из-за которого case class и получил своё название... Но про него я тут вообще писать ну буду. А т.к. скала компилирует исходники в байткод для виртуальный машины java (JVM), то мы без проблем можем проверить все, что я тут написал, воспользовавшись любым (jad, jd-gui, ..) декомпилятором байткода:
        public class Artist implements Product, Serializable {
            private final String name;
            private final String website;

            public Artist(String name, String website) {
                this.name = name;
                this.website = website;
                super();
            }

            public String name() { return this.name; }
            public String website() { return this.website; }
            public Artist copy(String name, String website) { return new Artist(name, website); }
            public String copy$default$2() { return website(); }
            public String copy$default$1() { return name(); }

            /* ... */
        }

Ну и объявим ещё два типа (ещё два класса):
    case class Song(title: String, year: Int, artists: Set[Artist])
    case class Compilation(title: String, songs: List[Song])
artists является множеством (т.е. элементы не повторяются) элементов типа Artist, а songs представлено списком (т.е. песни идут в определённом порядке) элементов типа Song.

Немного подумав, для удобства добавим значения по умолчанию, и вспомнив, что у сохранённых в базе данных объектов будет идентификатор (пусть он будет целым числом), учтем ещё и это:
    case class Artist(name: String, website: String, id: Option[Int] = None)
    case class Song(title: String, year: Int, artists: Set[Artist] = Set.empty, id: Option[Int] = None)
    case class Compilation(title: String, songs: List[Song] = List.empty, id: Option[Int] = None)
Очевидно, что код идущий после знака "равно" является значением по умолчанию для соответствующего аргумента. Работает это просто - если при вызове метода/функции/конструктора вы не указываете аргумент, то Scala использует значение по умолчанию. Выше я уже говорил, что для case class'ов Scala создает метод copy. И правда, в декомпилированном коде выше, в котором Artist имеет только name и website, вы можете увидеть этот метод. Там же, рядом, вы увидите два метода со странными названиями copy$default$1 и copy$default$2. Первый, как видно из кода, всегда возвращает первый аргумент (name), а второй... ну вы поняли. Эти методы используются скалой для получения значений по умолчанию для аргументов метода copy! Это значит, что создать объект, аналогичный данному за исключением каких-то полей - проще простого! Например:
        val x = new Artist(name = "Me", website = "http://127.0.0.1")
        val y = x.copy(name = "You")
отобразит
        Artist(Me, http://127.0.0.1, None)
        Artist(You, http://127.0.0.1, None)
Идентификатор записи в базе данных у нас опциональный. Т.е. может быть (объект загружен из базы данных), а может и не быть (мы его ещё только планируем создать). Тип Option[T] является запечатанным абстрактным типом. В природе существует аж два класса, для которых Option является родительским классом. Первый - это case class Some[T](value : T). Второй - это объект (синглетон) с именем None. Так как Option[T] запечатан (sealed), то больше типов унаследовать от Option[T] вы не можете. Поэтому, если видите Option[T], то вы всегда уверены, что перед вами либо Some(value), либо None. Может показаться, будто это какая-то странная вариация на тему null. Но это не так. Если вы видите, что функция возвращает объект типа Option[String], то вы всегда(!) знаете, что результат может быть None. А если вы (в Java) видите, что метод возвращает просто String - ну хорошо, если поведение описано в документации, которую читают реже, чем пишут, замечательно, если стоит аннотация.. но в 99% случаев можете только гадать: будет там null или не будет. И даже если сегодня вы точно знаете, что такой метод вам сейчас возвращает всегда строку, то нет никакой гарантии, что завтра он не будет возвращать null! Ещё одно отличие то, что None является полноценным объектом, у него есть методы и все такое. Иногда о типе Option[T] удобно думать как о коллекции, которая состоит либо из одного элемента, либо вообще пустая, но это я уже отвлекся.. Да, я намеренно не стал делать website и year типами Option[T] дабы не загромождать повествование. Пусть они будут обязательными, хотя в реальном мире они были бы также типом Option[T].


И для полной картины нашего примера не достает ещё одного класса. Добавим его:
    case class Artist(name: String, website: String, id: Option[Int] = None)
    case class Song(title: String, year: Int, artists: Set[Artist] = Set.empty, id: Option[Int] = None)
    case class Compilation(title: String, songs: List[Song] = List.empty, id: Option[Int] = None)

    case class Task(artists: Set[Artist] = Set.empty,
                    songs: Set[Song] = Set.empty,
                    compilations: Set[Compilation] = Set.empty)
т.е. я добавил класс Task, олицетворяющий задачу, над которой мы работаем. Например, задачу по добавлению новых песен в коллекцию. Предположим, что пользователь с помощью какого-то интерфейса (чудом) набрал нам то, что по его мнению необходимо добавить в базу данных. Много и сразу надо добавить. Некоторые песни не имеют исполнителей. Какие-то исполнители без песен и т. д. В общем все не просто, но типично для жизни. И вот перед тем как добавить все в базу данных, надо нам эти данные причесать: связаться с другими базами данных, гуглом и много чем ещё, проверить, может где ошибка, опечатка, исправить, год подправить, дополнить, в общем надо нам с этим счастьем теперь работать и видоизменять до неузнаваемости. Или, если в терминах приложения, то из одной Task'и нам надо сделать другую Task'у путём изменения свойств объектов.

Все просто и вы не видите проблем? Тогда скорее всего вы думаете про...

... императивный подход

Для этого нашу модель следует сделать изменяемой (mutable), так как по умолчанию case class'ы неизменны (immutable).
    case class Artist(var name: String, var website: String, var id: Option[Int] = None)
    case class Song(var title: String, var year: Int, var artists: Set[Artist] = Set.empty, var id: Option[Int] = None)
    case class Compilation(var title: String, var songs: List[Song] = List.empty, var id: Option[Int] = None)

    case class Task(var artists: Set[Artist] = Set.empty,
                    var songs: Set[Song] = Set.empty,
                    var compilations: Set[Compilation] = Set.empty)
Очевидно, что модификатор var перед именем аргумента конструктора означает... variable, т.е. переменная, т.е. меняет своё значение! Scala поощряет неизменность состояний и по умолчанию подразумевает модификатор val (т.е. value, т.е. значение) для case class'ов. Как только мы добавляем модификатор var, scala генерирует метод (сеттер) для смены значения переменной. Оператор присваивания именно этот сеттер и вызывает. (замечу, что и геттеры, и сеттеры можно определить явным способом, если(когда) сочтёте нужным)

Работа с изменяемыми объектами в Scala мало чем отличается от всех остальных императивных языков. В том числе, вы получаете весь букет проблем присущий такому подходу:
  • Вы не можете использовать ваши объекты в качестве ключей. Любое изменение состояния влечет смену hashcode'а объекта, а по хэшкоду объект ищется в map'ах в первую очередь.
  • Передавая изменяемый объект в качестве параметра в метод, у вас нет НИКАКОЙ гарантии, что его там не искалечат из добрых побуждений (отсортируют список в поле).
  • К примеру, вызывая метод transform и передавая в него task, вы вероятно получаете task уже в другом состоянии по завершению работы метода. Единственный способ проверить, было ли изменение в таком случае - клонировать (с глубоким копированием (deep clone)) всю task'у, а потом сравнить! Если вы попробуете это реализовать, то упрётесь в проблемы похожие на те, которые я опишу в следующем подходе. В результате поимеете проблемы двух миров. Единственным быстрым решением может быть только сериализация Task'и и последующая десериализация. Либо вариации на тему. А что, если одним из полей является блоб фотографии исполнителя? Об эффективности можно забыть. Как вариант, вы можете попросить transform возвращать взведённый флажок для случая, когда состояние изменилось, но это означает "до свидания красивый API".
  • А что, если новые изменения делаются глядя на старое состояние.. Тогда вам надо держать под рукой старое состояние task'и внутри метода transform. Это в очередной раз означает клонирование ВСЕГО состояния.
  • Обновили часть состояния, получили эксепшн... у вас транзакционная память? Нет? Печалька: теперь ваша структура в полурабочем виде.
  • И так далее, и тому подобное. А если кто-то думает, что всё это решается хорошим стилем программирования, дисциплиной, документацией... То я вам завидую, вы живете в другом мире.
Перечислять можно долго. После того, как я набрал вышесказанное, я попытался найти в интернете цитату Joshua Bloch (автора Effective Java), которую когда-то где-то видел, чтобы привести её буквально, вот она: "Classes should be immutable unless there's a very good reason to make them mutable.... If a class cannot be made immutable, limit its mutability as much as possible." (перевод: Классы должны иметь неизменное состояние, если для обратного нет очень хорошей причины... Если класс невозможно сделать неизменным, ограничьте его изменчивость настолько, насколько сможете) Цитату нашёл по первой же ссылке и обнаружил ещё больше аргументов на эту тему. В общем, кто сомневается - интернет в помощь. Эта тема разжёвана весьма прилично (в отличии от той, ради которой я вообще это пишу). Итак императивный подход нам не подходит. Посмотрим на альтернативу, на...

... функциональный подход

Вообще, строго говоря, изменчивость не является критерием функциональности или императивности. Но частота, с которой неизменность данных применяется при этих подходах, отличается кардинально.

Итак наша модель:
    case class Artist(name: String, website: String, id: Option[Int] = None)
    case class Song(title: String, year: Int, artists: Set[Artist] = Set.empty, id: Option[Int] = None)
    case class Compilation(title: String, songs: List[Song] = List.empty, id: Option[Int] = None)

    case class Task(artists: Set[Artist] = Set.empty,
                    songs: Set[Song] = Set.empty,
                    compilations: Set[Compilation] = Set.empty)
Теперь наша функция transform принимает в качестве аргумента Task и возвращает результат как Task.
Несмотря на то, что функцию transform я не намерен здесь реализовывать, я покажу, как она может выглядеть изначально:
    def transform(original: Task): Task = original
это можно прочитать как:
  • функция transform принимает аргумент типа Task и возвращает результат типа Task. Результатом будет значение из аргумента. (после знака равно следует определение функции)
или это можно прочитать вот так:
  • значение transform является функцией из-значения-типа-Task-в-значение-типа-Task, т.е. Task => Task
впрочем, это и записать так можно:
        val transform = (original : Task) => original
или так:
        val transform : Function1[Task, Task] = original => original
хотя, например, Java программисту вот такая запись должна показаться очень даже родной (разве что public нет, но он тут по умолчанию):
        val transform = new Function1[Task, Task] () {
            def apply(original: Task): Task = {
                return original
            }
        }
и это как раз то, во что компилируется (грубо говоря) любая функция, которая не является методом класса. Для полноты замечу, что return нужен только, если выход из функции осуществляется в середине её тела (например, по условию), а результатом и так будет последнее выражение в теле функции или конструкции. Также можно не указывать тип возвращаемого значения. Скала это выведет сама, зная лишь только тип аргумента метода apply. Ну и напоследок:
        val transform = new Function1[Task, Task] {
            def apply(original: Task) = original
        }
Можно придумать, как записать функцию иначе, в каждом случае удобно по-разному, но хватит пока про функции. Далее это пригодится.


Неизменность состояния устраняет все минусы, имеющиеся в императивном подходе. Но поговорим мы про сложности использования функционального подхода.
  • Если вы привыкли к императивному подходу, то функциональный может показаться сложным или вообще не реализуемым (некоторые сходу не могут список просуммировать без использования цикла)
  • Если один объект, свойство которого необходимо изменить, используется множество раз в пределах модели, то появляется проблема "старого состояния", имеющая прямую связь с проблемой эквивалентности и зависящая от намерений модификации состояния.

Проблема "старого состояния"

Пускай у нас есть такой граф данных:
    val finntroll = Artist(name = "Finntroll", website = "www.finntroll.net")
    val svampfest = Song(title = "Svampfest", artists = Set(finntroll), year = 0)
    val skog      = Song(title = "Skog", artists = Set(finntroll), year = 0)
    val songs     = List(skog, svampfest)
И ВНЕЗАПНО мы хотим поменять www.finntroll.net на http://www.finntroll.net. Сделать так:
    finntroll.website = "http://www.finntroll.net"
мы не можем: все наши объекты неизменяемые. Очевидно, что надо сделать так:
    val newFinntroll = finntroll.copy (website = "http://www.finntroll.net")
И вот на руках у нас есть newFinntroll, именующий (т.е. ссылающийся на) объект идентичный тому, который именует (т.е. ссылается) имя finntroll за исключением значения в поле website. Но песни svampfest и skog в нашем списке как ссылались на старую версию исполнителя, так и ссылаются. Давайте создадим новые экземпляры песен, которые будут использовать новую версию исполнителя:
    val newSvampfest = svampfest.copy (artists = Set(newFinntroll))
    val newSkog      = skog.copy (artists = Set(newFinntroll))
    val newSongs     = List(newSkog, newSvampfest)
Теперь, наконец-то, у нас есть newSong, в которой граф полностью соответствует тому, что мы хотим. Но есть одна проблема. Пример больно уж простой. В реальности при попытке обновить граф у нас будет:
  • songs
  • finntroll
  • newFinntroll
и на основе этого нам надо получить newSongs. Вобщем-то это не сложно: надо всего лишь пробежаться по всем песням списка и для каждой песни создать (возможно) обновлённую версию, после чего положить её в новый список:
    val newSongs = songs.map (song => song.copy(artists = song.artists.replace(finntroll, newFinntroll)))
(Можно было бы и избежать ненужных копирований, но это, для данного случая, усложнило бы код ради экономии на спичках. Также я использовал функцию replace, которой на самом деле на Set'ах нет. Но, во-первых, не трудно добавить, а, во-вторых, не относится к делу.)
Если код выше понятен, то этот текст серым цветом можно пропустить. Если нет, то поясняю:
        song => song.copy(artists = song.artists.replace(finntroll, newFinntroll))
это анонимная функция, где "song" является аргументом функции, а всё, что после стрелочки => является телом функции. То есть анонимная функция принимает одну переменную и возвращает значение, вычисленное вот этим выражением:
        song.copy(artists = song.artists.replace(finntroll, newFinntroll))
Про метод copy я уже писал выше. Если кратко, то наша анонимная функция создает копию песни, переданной ей в виде аргумента, но с полем artists таким, что в коллекции исполнителей этой песни все finntroll заменены на newFinntroll. Определить такую же анонимную функцию на Java можно примерно так:
        new Function1<Song, Song>() {
            public Song apply(Song song) {
                return song.artists.replace(finntroll, newFinntroll);
            }
        }
(при условии, что наша song.artists.replace не изменяет оригинальный список). Итак, у нас есть анонимная функция, которая возвращает новую версию песни. Т. е. с новым исполнителем, если он там был. Эта анонимная функция передается в метод map списка songs. Метод map вызывает функцию для каждого элемента списка, генерируя новый список, состоящий из результатов работы переданной в map функции. Т.е.
        List(7, 2, 5, 9).map(x => x * 10)
эквивалентно
        List(7*10, 2*10, 5*10, 9*10)
С одной стороны ничего сложного, обошлись одной строчкой, а, с другой стороны, для модели с очень маленькой вложенностью нам пришлось копировать... всю модель! И так для любого поля любого объекта. Более того, надо всегда помнить, в каком месте какие поля куда ссылаются, чтобы случайно не забыть обновить нужное значение. А если рассмотреть нашу модель целиком?
    case class Artist(name: String, website: String, id: Option[Int] = None)
    case class Song(title: String, year: Int, artists: Set[Artist] = Set.empty, id: Option[Int] = None)
    case class Compilation(title: String, songs: List[Song] = List.empty, id: Option[Int] = None)

    case class Task(artists: Set[Artist] = Set.empty,
                    songs: Set[Song] = Set.empty,
                    compilations: Set[Compilation] = Set.empty)
При модификации исполнителя обновлять придётся всё, вплоть до корневого объекта (т.е. до Task). Кстати, в природе, в Haskell мире, существует подход с названием "Scrap your boilerplate", который позволяет независимо от структуры данных, очень грубо говоря, обновлять все поля всех объектов, в пределах заданного графа, определённым образом при выполнении определённого условия (обновлять здесь и далее подразумевает создание новых данных, а не модификация существующих). В scala такой подход реализовать тоже возможно, но без помощи derive это очень уныло.. Но я отвлекся. Существует ещё одна проблема. Считать ли newFinntroll эквивалентным finntroll? Интуитивно - да. А практически - это два разных объекта, если мы будем сравнивать по полям (website у них отличается). Как быть? Использовать какой-то id'и тем более, что он у нас есть в качестве поля каждого объекта. По такому принципу собственно и работают ссылки. В качестве id объекта выступает адрес объекта (грубо говоря номер байта в массиве памяти) и, соответственно, в переменных у нас хранятся адреса объектов. И потому, когда в императивном программировании мы пишем song.website = "blah", мы используем адрес объекта из переменной song для того, чтобы найти в памяти структуру объекта и записать по определённому смещению в структуре новый адрес, ведущий на объект "blah"... А когда делаем song2 = song, то мы не копируем объект, а копируем адрес этого объекта (я не говорю обо всех языках). Аналогично и базы данных с их ключами. Объекты валяются по таблицам, а граф строится с помощью ключей. Получается ссылки у нас есть всегда и везде. Попробуем посмотреть на то, как работает база данных. Пусть мы, как и в примере выше, обновляем исполнителя. При этом на этого исполнителя имеются ссылки из таблицы песен. Что происходит? (очень грубое и приближённое описание с морем допущений и упрощений)
  • Начинается транзакция.
  • Берем строку таблицы Artists, соответствующую записи finntroll.
  • Создаем полную копию этой строки и добавляем в свободное место пространства таблицы (мы ведь не хотим обновлять данные там где они сейчас, ибо в случае падения не откатимся)
  • (1) Делаем требуемые модификации в новом месте.
  • (2) У нас есть массив соответствия id и положения строки для этого id в пространстве таблицы. Модифицируем массив так, чтобы id для finntroll указывала на новую запись.
  • Транзакция окончена.
Если посмотреть внимательно, то при таком подходе лишь в одном месте реально происходит смена состояния (то, чего мы избегаем). Это шаг 2. Шаг 1 это копирование с подменой (наш copy метод). В шаге 2 у нас меняется соответствие между id объекта и физической ссылкой на объект. Или другими словами, мы создаем новое соответствие! Вот оно! Из одной Map мы делаем другую Map. Взяв идею из баз данных, переложим её на нашу модель:
    case class Artist(name: String, website: String, id: Option[Int] = None)
    case class Song(title: String, year: Int, artists: Set[Int] = Set.empty, id: Option[Int] = None)
    case class Compilation(title: String, songs: List[Int] = List.empty, id: Option[Int] = None)
В модели выше нет коллекций объектов, в ней нет способа найти нужный объект по id. Для этого нужна "база данных". Вот она:
    case class Task(artistMap: Map[Int, Artist] = Map.empty,
                    songMap: Map[Int, Song] = Map.empty,
                    compilationMap: Map[Int, Compilation] = Map.empty) {
        def withArtist(assoc: (Int, Artist)) = this.copy(artistMap = artistMap + assoc)
        def withSong(assoc: (Int, Song)) = this.copy(songMap = songMap + assoc)
        def withCompilation(assoc: (Int, Compilation)) = this.copy(compilationMap = compilationMap + assoc)
    }
Выше я определил удобные методы для класса Task. Так, например, метод withArtist принимает в качестве аргумента пару (кортеж), первый элемент которой типа Int, а второй типа Artist. Тоже самое можно было бы записать вот так:
        def withArtist(assoc: Tuple2[Int, Artist]) = this.copy(artistMap = artistMap + assoc)
Кстати, в scala, существует красивый способ создать кортеж с помощью оператора стрелочка: ->
        val x = "a" -> 2
        val y = ("a", 2)
В примере выше результат созданий кортежей будет одинаковым, т.е. x == y. Выражение вида artistMap + assoc является красивостью для вызова artistMap.+(assoc), т.е для вызова метода с именем 'плюс' у объекта artistMap. В некоторых случаях точку можно опускать. Скобки можно опускать только, если у метода всего один аргумент. Метод + из класса Map возвращает новую Map имеющую все те же ассоциации между ключами и значениями плюс новая ассоциация. Операция эта относительно дешёвая: копируется намного меньше, чем вы думаете.


Итак, вспомним всё ту же проблему, только теперь у нас есть task типа Task, а также finntroll и newFinntroll. Только теперь всё проще:
    val newTask = task withArtist (finntroll.id.get -> newFinntroll)
Обращаю внимание, что finntroll.id.get, а не finntroll.id, т.к. id у нас типа Option[Int], а не Int. Делать так плохо, но об этом ниже.
Казалось бы все хорошо и жили они долго и счастливо, но есть ряд проблем:
  • 1. Id может не быть. То есть вообще не быть. Совсем. Объект ещё не лежит в базе данных и вероятно не собирается туда ложиться.
  • 2. В качестве ключей используются любые числа типа Int. Никто не мешает использовать ключ от Song, занося объект в Artist..
  • 3. Когда мы обрабатываем текстовый файл с описанием музыкальной коллекции, логично позволять пользователю обозначать элементы коллекции строковыми идентификаторами такими, какими ему будет удобно пользоваться при создании связей между элементами. Все-таки человек не компьютер и запомнит слово finntroll лучше, чем число 1721.
Попробуем устранить все эти проблемы и начнём с конца. Третья проблема подразумевает, что неплохо бы нам использовать строки. Но ведь нам иногда удобно использовать числа в качестве ключей! Иногда числа.. иногда строки. Напрашивается абстракция. Пусть наша модель будет параметризована типом ключа.
Чем функция отличается от значения? Много чем, и в тоже время вообще ничем не отличается. Все зависит от того, в чем мы заинтересованы. По сути функция является отображением множества своих аргументов в множество результатов. Отображение чего-то во что-то можно рассматривать как значение (мы же рассматриваем объекты типа Map как значения). Соответственно функции от значений ничем не отличаются. С другой стороны, если мы заинтересованы не в самом отображении, а в результате отображения, то само отображение не катит. Другими словами, для получения результата отображения нам необходимы аргументы. Получается функция - это значение, параметризованное аргументом, как бы странно это не звучало. В общем, к чему я клоню... а клоню я к тому, что у нас есть просто типы данных, а есть параметризованные типы данных. Параметризованный тип данных - это как функция. Только функция отображает значения в другие значения, а параметризованные типы отображают одни типы в другие. Например, List[T] - это тип List (зовётся конструктором типа), параметризованный типом T. Отображает множество типов T (таких как Int, String, ...) в множество типов List[T] (таких как List[Int], List[String], ...). Как известно, для функции мы умеем сужать возможную область аргументов (используем типы аргументов), а также мы умеем сужать отображаемую область (результат). Для параметризованных типов все тоже самое. Мы можем наложить ограничение на тип T, или даже на результат аппликации T к List. Запись между функцией и параметризованным типом похожа (напишу я тут не слишком канонично, по канонам оно будет дальше):
        f: Int => String
-- это функция f с аргументом Int и результатом String (проецирует числа в строки)
        List: T => List[T]
-- это конструктор типа List проецирующий множество типов T в множество типов List[T].

Получается что-то такое:
    case class Artist[R](name: String, website: String, id: Option[Int] = None)
    case class Song[R](title: String, year: Int, artists: Set[R] = Set.empty, id: Option[Int] = None)
    case class Compilation[R](title: String, songs: List[R] = List.empty, id: Option[Int] = None)

    case class Task[R](artistMap: Map[R, Artist[R]] = Map.empty,
                       songMap: Map[R, Song[R]] = Map.empty,
                       compilationMap: Map[R, Compilation[R]] = Map.empty) {
        def withArtist(assoc: (R, Artist[R])) = this.copy(artistMap = artistMap + assoc)
        def withSong(assoc: (R, Song[R])) = this.copy(songMap = songMap + assoc)
        def withCompilation(assoc: (R, Compilation[R])) = this.copy(compilationMap = compilationMap + assoc)
    }
Как видно, я параметризовал все по R (первая буква слова Reference - ссылка). Теперь там, где был тип Int, у нас какой-то тип R. С этого момента мы не можем говорить Artist, говоря о конкретном типе данных. Теперь мы обязаны говорить Artist[T], когда говорим про конкретный тип. Ибо Artist теперь является конструктором типа и чтобы стать типом (с нулевым конструктором), ему нужен аргумент (так же как функции, чтобы стать значением, нужен аргумент). К примеру, Map[K, V] (где K - Key, ключ, а V - Value, значение) это тип, а Map - конструктор типа. Следует отметить, что K и V - это какие-то типы. А раз типы, то мы не можем написать Map[R, Artist], ибо Artist - конструктор типа, а не тип! Поэтому мы пишем Map[R, Artist[R]]. Впрочем, это все пока ясно на уровне интуиции, но лучше понять это глубже, чем интуиция, а то...
Вобщем-то параметризация по типу решает проблему номер (3) из нашего списка. Но как быть, если мы хотим параметризовать тип ссылки, чтобы ссылка на исполнителя являлась несовместимой по типу со ссылкой на песню. Очевидно, что нет другого выхода, кроме как параметризовать саму ссылку по типу, на который ссылка ссылается.
Итого, функция без аргументов вообще (с нулевым количеством аргументов) является значением, константой. Функции, которые принимают другие функции в качестве аргументов или возвращают функции как результат, называются функциями высшего порядка. С типами все тоже самое. Есть просто типы (с нулевым конструктором), а есть типы параметризованные другим типом (т.е. являющиеся конструктором типа). Аналогично, конструктор типа, который использует в качестве параметра другой конструктор типа, является типом высшего порядка. Так, например, функция, которая возвращает Nothing, а принимает в качестве аргумента функцию, которая принимает в качестве аргумента Int, а возвращает String, запишется вот так:
        f: (Int => String) => Nothing
Соответственно, если есть функция g и значение v:
        g: Int => String
        v: Int
то мы можем писать, что
        f(g): Nothing
        g(v): String
То совершенно аналогично и с типами. К примеру в выражении
        MyList: (R => Container[R)) => List[Container[T]]
мы описали конструктор типа List, который в качестве аргумента принимает другой конструктор типа. Причём мы описали форму того конструктора, который принимает наш конструктор List. А именно мы говорим, что форма у нас такая: R => Container[R], где R - это тип, а Container - собственно какой-то конструктор типа. Ещё один способ это осознать, это записать все вот так (где звёздочка у нас олицетворяет конкретный тип, а (* => *) это конструктор типа):
        MyList: (* => *) => *
Это очень важно понять и уметь отличать где тип, а где конструктор типа, иначе будут ошибки компиляции при попытке использовать конструктор типа там, где ожидается тип, и наоборот.

Получается вот такое:
    case class Artist[R[_]](name: String, website: String, id: Option[Int] = None)
    case class Song[R[_]](title: String, year: Int, artists: Set[R[Artist[R]]] = Set.empty, id: Option[Int] = None)
    case class Compilation[R[_]](title: String, songs: List[R[Song[R]]] = List.empty, id: Option[Int] = None)

    case class Task[R[_]](artistMap: Map[R[Artist[R]], Artist[R]] = Map.empty,
                          songMap: Map[R[Song[R]], Song[R]] = Map.empty,
                          compilationMap: Map[R[Compilation[R]], Compilation[R]] = Map.empty) {
        def withArtist(assoc: (R[Artist[R]], Artist[R])) = this.copy(artistMap = artistMap + assoc)
        def withSong(assoc: (R[Song[R]], Song[R])) = this.copy(songMap = songMap + assoc)
        def withCompilation(assoc: (R[Compilation[R]], Compilation[R])) = this.copy(compilationMap = compilationMap + assoc)
    }
Красиво? Да, только в глазах рябит от R. Дальше упростим ;-)
На самом деле параметризация Artist вообще здесь чисто для красоты, так как R в определении класса Artist не используется. Но чтобы все было унифицировано, пусть будет. Посмотрим на класс Song. Сразу после имени класса идёт перечисление параметров типа. Если раньше единственным параметром типа был параметр R, то теперь параметр этот поменял свою форму и теперь он выглядит как R[_], что говорит нам о том, что теперь он не тип, а конструктор типа! Теперь посмотрим на вот эту запись Set[R[Artist[R]]]. Почему так? Потому что класс Set параметризован типом элементов, которые лежат в этом контейнере. В нашем случае в контейнере лежат ссылки на исполнителя. Ссылка у нас R. Но просто R написать мы не можем, так как, во-первых, у нас конкретная ссылка - ссылка на исполнителя, а, во-вторых, R - это конструктор типа, а Set параметризована типом, а не конструктором. Соответственно пишем Set[R[Artist... а дальше? Все? Нет. R параметризована типом, а Artist у нас не тип а конструктор типа. Поэтому, чтобы удовлетворить R, надо указать тип. А как из Artist сделать тип? Подставить параметр в конструктор типа, параметром для Artist является ссылка, т.е. мы пишем Set[R[Artist[R.. Все? Смотрим: конструктор типа Artist параметризован конструктором типа и в тоже время R является конструктором типа, совпало! Можно закрывать скобочки.
Упрощаем:
    type RefMap[R[_], T[_[_]]] = Map[R[T[R]], T[R]]
    type Assoc[R[_], T[_[_]]] = (R[T[R]], T[R])

    case class Artist[R[_]](name: String, website: String, id: Option[Int] = None)
    case class Song[R[_]](title: String, year: Int, artists: Set[R[Artist[R]]] = Set.empty, id: Option[Int] = None)
    case class Compilation[R[_]](title: String, songs: List[R[Song[R]]] = List.empty, id: Option[Int] = None)

    case class Task[R[_]](artistMap: RefMap[R, Artist] = Map.empty,
                          songMap: RefMap[R, Song] = Map.empty,
                          compilationMap: RefMap[R, Compilation] = Map.empty) {
        def withArtist(assoc: Assoc[R, Artist]) = this.copy(artistMap = artistMap + assoc)
        def withSong(assoc: Assoc[R, Song]) = this.copy(songMap = songMap + assoc)
        def withCompilation(assoc: Assoc[R, Compilation]) = this.copy(compilationMap = compilationMap + assoc)
    }
Ключевое слово type, очевидно, используется для присвоения какому-то типу имени. Так я присвоил имя RefMap[...] типу Map[R[T[R]], T[R]]. Мне кажется, не нужно быть гением, чтобы прочитать первую строчку нового определения как "определяем тип RefMap, параметризованный R (конструктором типов) и T (конструктором конструкторов типа), эквивалентный типу Map, в котором типом ключа является R[T[R]], а типом значения является T[R]". Аналогично определяем тип Assoc[..]. Это позволяет нам упростить тип Task[_[_]] и сделать его понятным даже тем, кто считает параметризованные типы аналогом шаблонов C++!
Попробуем использовать:
    case class IntRef[T](id: Int)

    val finntroll       = Artist[IntRef](name = "Finntroll", website = "www.finntroll.net")
    val finntrollRef    = IntRef[Artist[IntRef]](1)
    val svampfest       = Song(title = "Svampfest", artists = Set(finntrollRef), year = 0)
    val svampfestRef    = IntRef[Song[IntRef]](1)
    val skog            = Song(title = "Skog", artists = Set(finntrollRef), year = 0)
    val skogRef         = IntRef[Song[IntRef]](2)
    val task            = Task(artistMap = Map(finntrollRef -> finntroll),
                               songMap = Map(svampfestRef -> svampfest),
                               compilationMap = Map[IntRef[Compilation[IntRef]], Compilation[IntRef]]())
                           .withSong(skogRef -> skog)

    val finntroll2 = finntroll.copy[IntRef](website = "http://www.finntroll.net")
    val task2 = task.withArtist(finntrollRef -> finntroll2)

    println(task)
    println(task2)
Выдаст (я поставлю переносы строк где надо, а то оно без переносов и отступов выдает):
    Task(Map(IntRef(1) -> Artist(Finntroll,www.finntroll.net,None))
         Map(IntRef(1) -> Song(Svampfest,0,Set(IntRef(1)),None),
             IntRef(2) -> Song(Skog,0,Set(IntRef(1)),None))
         Map())

    Task(Map(IntRef(1) -> Artist(Finntroll,http://www.finntroll.net,None))
         Map(IntRef(1) -> Song(Svampfest,0,Set(IntRef(1)),None),
             IntRef(2) -> Song(Skog,0,Set(IntRef(1)),None)),
         Map())
Неплохо. Работает. Но может быть лучше. В частности меня не устраивает, что ссылки на объект находятся отдельно от объекта. В итоге, имея на руках Song, сказать, как на него ссылаться, нельзя. Попробуем сделать лучше. Давайте объявим трэйт с названием UsingRef (ИспользующийСсылку):
    trait UsingRef[R[_], T[_[_]]] {
        self: T[R] =>

        def ref : R[T[R]]
        def withRef : (R[T[R]], T[R]) = (this.ref, this)
    }
Если коротко, то трэйт является mix-in'ом или чем-то похожим на интерфейс в джава в том смысле, что, в отличии от класса, мы можем унаследовать несколько трэйтов, но в тоже время в отличии от интерфейса джавы трэйт может иметь реализации методов и много чего ещё (при этом не имея проблемы множественного наследования). Трэйт UsingRef параметризован ссылкой R[_] и типом, на который эта ссылка ссылается T[_[_]]. В то время, как R является конструктором типа, а T является конструктором конструкторов типа, T[R] является вполне себе каким-то конкретным типом! А если конкретно, то типом, в качестве ссылки в котором используется конструктор типа R. Если это кажется сложным, то запишите всё через "звёздочки" и просветление не заставит себя ждать. Следует также отметить, что запись вида:
        self: T[R] =>
накладывает ограничение на то, где данный трэйт может быть использован. А именно мы говорим, что накладывать его можно только на типы, которые являются (под)типами T[R]. Что нам такое ограничение дает? Много что. Но конкретно в этом случае наш this внутри методов трэйта становится типом T[R]. Это вполне логично, т.к. мы сказали, что использовать наш трэйт можно только вместе с типом T[R]. Смотрим дальше. Дальше мы объявляем абстрактный метод БЕЗ АРГУМЕНТОВ (то есть вообще, даже без пустых скобочек). Это значит, что внешне метод неотличим от значения. Это дает нам одно преимущество: при написании конкретной реализации такого абстрактного метода мы можем реализовать её как: метод (def), значение (val), переменная (var) или ленивое значение (lazy val), которое будет вычислено при первом обращении к нему. В следующей строке наш трэйт определяет конкретный метод withRef, возвращающий кортеж (пару) из ссылки на себя (используя абстрактный метод ref) и собственно себя.

Смысл этого трэйта в том, чтобы показать, что наш объект имеет ссылку ref и имеет удобный метод withRef, возвращающий кортеж из ссылки и указателя на себя, что идеально подходит для добавления объекта в Map. Неплохо бы определить ещё один трэйт:
    trait RefBuilder[R[_]] {
        def makeArtistRef(artist: Artist[R]): R[Artist[R]]
        def makeCompilationRef(compilation: Compilation[R]) : R[Compilation[R]]
        def makeSongRef(song: Song[R]): R[Song[R]]
    }
Трэйт RefBuilder определяет интерфейс всех классов, которые умеют возвращать ссылки для объектов. Идея та же, что и у type class'ов в Haskell, т.е. мы собираемся ввести категорию ссылок R[_], для которых определён билдер. Трэйт параметризован типом ссылки, которую данный билдер умеет возвращать. Сразу же определим архиудобный билдер IdRefBuilder. Удобный он тем, что связывает объекты по их айди из базы данных и нужен для случаев, когда объекты загружены из БД и мы точно знаем, что айди там есть. Итак:
    implicit object idRefBuilder extends RefBuilder[IntRef] {
        def makeArtistRef(artist: Artist[IntRef]) = IntRef(artist.id.get)
        def makeCompilationRef(compilation: Compilation[IntRef]) = IntRef(compilation.id.get)
        def makeSongRef(song: Song[IntRef]) = IntRef(song.id.get)
    }
Да, в scala можно сразу же создавать объект (синглетон). Такая запись эквивалентна:
        implicit lazy val idRefBuilder = new RefBuilder[IntRef] {
            def makeArtistRef(artist: Artist[IntRef]) = IntRef(artist.id.get)
            def makeCompilationRef(compilation: Compilation[IntRef]) = IntRef(compilation.id.get)
            def makeSongRef(song: Song[IntRef]) = IntRef(song.id.get)
        }
... за исключением того, что объекты могут являться жителями пакета (package), в то время как значения жителями пакета быть не могут.

Определим ещё два билдера. Первый билдер будет создавать уникальные ссылки для каждого объекта.
    case class UuidRef[T](id : String = java.util.UUID.randomUUID.toString)
    implicit object UuidRefBuilder extends RefBuilder[UuidRef] {
        def makeArtistRef(artist : Artist[UuidRef]) = UuidRef()
        def makeCompilationRef(compilation : Compilation[UuidRef]) = UuidRef()
        def makeSongRef(song : Song[UuidRef]) = UuidRef()
    }
А второй билдер будет использовать сами объекты в качестве ссылок o_O
    case class ValueRef[T](value : T)
    implicit object ValueRefBuilder extends RefBuilder[ValueRef] {
        def makeArtistRef(artist : Artist[ValueRef]) = ValueRef(artist)
        def makeCompilationRef(comp : Compilation[ValueRef]) = ValueRef(comp)
        def makeSongRef(song : Song[ValueRef]) = ValueRef(song)
    }
Итак, у нас есть все, чтобы улучшить Artist:
    case class Artist[R[_]](name: String,
                            website: String,
                            id: Option[Int] = None)(
                        implicit rb: RefBuilder[R]) extends UsingRef[R, Artist] {
        lazy val ref = rb makeArtistRef this
    }
... Song:
    case class Song[R[_]](title: String,
                          year: Int,
                          artists: Set[R[Artist[R]]] = Set.empty,
                          id: Option[Int] = None)(
                        implicit rb: RefBuilder[R]) extends UsingRef[R, Song] {
        lazy val ref = rb makeSongRef this
    }
... Compilation:
    case class Compilation[R[_]](title: String,
                                 songs: List[R[Song[R]]] = List.empty,
                                 id: Option[Int] = None)(
                        implicit rb: RefBuilder[R]) extends UsingRef[R, Compilation] {
        lazy val ref = rb makeCompilationRef this
    }
Если вы читаете это не по диагонали, то наверное заметили, что во все классы добавилась новая группа аргументов. Да, в Scala групп аргументов может не быть, может быть одна (как это обычно бывает), а может быть более, чем одна. Это дает громадное количество новых возможностей. Перенос аргументов (curring), блоки... В нашем случае, новая группа везде помечена модификатором implicit (неявный). Тем самым мы говорим компилятору, что возможно мы хотим опустить эти аргументы полностью и в таком случае просим компилятор найти нам такой объект в области видимости вызова (то есть в области видимости того места, где мы создаем экземпляры класса Song, Compilation, Artist, а не там, где они объявлены). Если в области видимости присутствует значение (или метод, или объект), который имеет нужный тип и также помечен как implicit, то scala будет использовать его в качестве отсутствующего аргумента. Если такого объекта нет или есть, но больше, чем один, то компилятор ругнется и не даст скомпилировать такую программу. Ещё одним важным моментом является то, что ref имеет модификатор lazy. Это позволяет нам: пользоваться объектом, копировать методом copy, модифицировать и т.д. При этом до тех пор, пока мы не обратимся к методу ref, выражение для ref не будет вычислено (т.е. объект вероятно умрёт, а обращение к ref не произойдет совсем). Это очень важный момент. Это дает нам экономию ресурсов процессора и позволяет писать достаточно интересные билдеры ссылок.
Сделаем ещё одну удобную штуку. Сделаем так, что на основе любой последовательности объектов, имеющих трэйт UsingRef, можно было легко создать Map из-ключей-этих-объектов-в-сами-объекты:
    implicit class RichUsingRefIterable[R[_], T[_[_]]](val iterable : Iterable[UsingRef[R, T]]) extends AnyVal {
        def toRefMap: RefMap[R, T] =
            Map(iterable.map(_.withRef).toSeq : _*)
    }
Я не буду вдаваться во все тонкости value class'ов и т.д., но предположим у нас есть
        val list = List(song1, song2, song3)
если я попробую вызвать list.toRefMap, то казалось бы ничего не должно получиться. У класса List нет метода toRefMap. Но все не так просто. Обломавшись с классом List, Scala поищет в текущей области видимости метод, помеченный как implicit (неявный) и умеющий из нашего List сделать другой объект, в котором будет метод toRefMap! В нашем примере таким методом является конструктор класса RichUsingRefIterable, который создаст одноименный класс. Получается, что встретив list.toRefMap, Scala скомпилирует вместо этого код RichUsingRefIterable(list).toRefMap (без тонкостей value class'ов). Такая возможность позволяет нам расширять существующие типы данных. Запись вида (_.withRef) - это короткий вариант (x => x.withRef), что является анонимной функцией, получающей в качестве аргумента x и возвращающей в качестве результата x.withRef (кортеж: ключ, объект). Соответственно iterable.map(_.withRef) вернет последовательность кортежей (ключ, объект). Вызов toSeq сделает из неизвестной последовательности (просто Iterable) последовательность типа Seq. С помощью : _* мы можем применить последовательность в качестве аргументов для конструктора Map (то есть передать не последовательность как один аргумент, а элементы последовательности в качестве аргументов... это если не вдаваться в то, как это реализовано). Как результат у нас будет Map из ключа в объект.

И, наконец, улучшения добрались и до класса Task. Давайте добавим туда методы artists, songs, compilations, которые будут просто удобным способом получить коллекции объектов из соответствий (Map), лежащих в классе Task. Так же создадим очень удобный метод using, который будет делать из класса Task, параметризованного одним типом ссылок, другую Task параметризованную другим типом ссылок! В результате получаем вот такой код:
    trait RefBuilder[R[_]] {
        def makeArtistRef(artist: Artist[R]): R[Artist[R]]
        def makeCompilationRef(compilation: Compilation[R]): R[Compilation[R]]
        def makeSongRef(song: Song[R]): R[Song[R]]
    }

    case class IntRef[T](id: Int)
    implicit object IdRefBuilder extends RefBuilder[IntRef] {
        def makeArtistRef(artist: Artist[IntRef]) = IntRef(artist.id.get)
        def makeCompilationRef(compilation: Compilation[IntRef]) = IntRef(compilation.id.get)
        def makeSongRef(song: Song[IntRef]) = IntRef(song.id.get)
    }

    case class UuidRef[T](id: String = java.util.UUID.randomUUID.toString)
    implicit object UuidRefBuilder extends RefBuilder[UuidRef] {
        def makeArtistRef(artist: Artist[UuidRef]) = UuidRef()
        def makeCompilationRef(compilation: Compilation[UuidRef]) = UuidRef()
        def makeSongRef(song: Song[UuidRef]) = UuidRef()
    }

    case class ValueRef[T](value: T)
    implicit object ValueRefBuilder extends RefBuilder[ValueRef] {
        def makeArtistRef(artist: Artist[ValueRef]) = ValueRef(artist)
        def makeCompilationRef(comp: Compilation[ValueRef]) = ValueRef(comp)
        def makeSongRef(song: Song[ValueRef]) = ValueRef(song)
    }

    type RefMap[R[_], T[_[_]]] = Map[R[T[R]], T[R]]
    type Assoc[R[_], T[_[_]]] = (R[T[R]], T[R])

    implicit class RichUsingRefIterable[R[_], T[_[_]]](val iterable: Iterable[UsingRef[R, T]]) extends AnyVal {
        def toRefMap: RefMap[R, T] =
            Map(iterable.map(_.withRef).toSeq: _*)
    }

    trait UsingRef[R[_], T[R[_]]] {
        self: T[R] =>

        def ref: R[T[R]]
        def withRef: (R[T[R]], T[R]) = (this.ref, this)
    }

    case class Artist[R[_]](name: String,
                            website: String,
                            id: Option[Int] = None)(
                                    implicit rb: RefBuilder[R]) extends UsingRef[R, Artist] {
        lazy val ref = rb makeArtistRef this
    }

    case class Song[R[_]](title: String,
                          year: Int,
                          artists: Set[R[Artist[R]]] = Set.empty,
                          id: Option[Int] = None)(
                                  implicit rb: RefBuilder[R]) extends UsingRef[R, Song] {
        lazy val ref = rb makeSongRef this
    }

    case class Compilation[R[_]](title: String,
                                 songs: List[R[Song[R]]] = List.empty,
                                 id: Option[Int] = None)(
                                         implicit rb: RefBuilder[R]) extends UsingRef[R, Compilation] {
        lazy val ref = rb makeCompilationRef this
    }

    case class Task[R[_]](artistMap: RefMap[R, Artist],
                          songMap: RefMap[R, Song],
                          compilationMap: RefMap[R, Compilation]) {
        def withArtist(assoc: Assoc[R, Artist]) = this.copy(artistMap = artistMap + assoc)
        def withSong(assoc: Assoc[R, Song]) = this.copy(songMap = songMap + assoc)
        def withCompilation(assoc: Assoc[R, Compilation]) = this.copy(compilationMap = compilationMap + assoc)

        def artists: Iterable[Artist[R]] = artistMap.values
        def songs: Iterable[Song[R]] = songMap.values
        def compilations: Iterable[Compilation[R]] = compilationMap.values

        def using[NR[_]](implicit refBuilder: RefBuilder[NR]): Task[NR] = {
            val newArtistByOldKey = artistMap.mapValues(_.copy[NR]()).iterator.toMap

            val newSongByOldKey =
                songMap.mapValues {
                    song =>
                        val newSongArtistRefs = song.artists map (newArtistByOldKey(_).ref)
                        song.copy[NR](artists = newSongArtistRefs)
                }.iterator.toMap

            val newCompilationByOldKey =
                compilationMap.mapValues {
                    comp =>
                        val newCompilationSongRefs = comp.songs map (newSongByOldKey(_).ref)
                        comp.copy[NR](songs = newCompilationSongRefs)
                }.iterator.toMap

            Task[NR](
                artistMap = newArtistByOldKey.values.toRefMap,
                songMap = newSongByOldKey.values.toRefMap,
                compilationMap = newCompilationByOldKey.values.toRefMap
            )
        }
    }
Я думаю к этому моменту повествования добавлять больше деталей синтаксиса и семантики смысла нет. Единственное, что стоит сказать... метод using получает билдер либо явно, либо не явно, а методы copy, используемые в методе using, находят этот билдер неявным способом. Стоит обратить внимание на метод mapValues у Map, который применяет функцию ко всем значениям соответствия. Подвох в том, что функция применяется не сразу, а при попытке получить значение по ключу. Это значит, что если вы 5 раз получаете одно и то же значение из соответствия, то функция вычисляется 5 раз. Это не было бы проблемой, если бы язык был бы полностью ленивым! Это не было бы проблемой, если бы у нас была обязательная монада IO для операций с побочным эффектом. У нас же ленивость опциональная, да и монада опциональная, потому будет правильным принудительно из вьюшки поверх соответствия сделать нормальное, честное соответствие. Для этого, как раз я и написал .iterator.toMap.
Попробуем в деле?
    val finntroll = Artist[IntRef](name = "Finntroll", website = "www.finntroll.net", id = Some(1))
    val svampfest = Song(title = "Svampfest", artists = Set(finntroll.ref), year = 0, id = Some(1))
    val skog = Song(title = "Skog", artists = Set(finntroll.ref), year = 0, id = Some(2))

    val task = Task(artistMap = List(finntroll).toRefMap,
                    songMap = List(svampfest, skog).toRefMap,
                    compilationMap = Map(): RefMap[IntRef, Compilation])

    val finntroll2 = finntroll.copy[IntRef](website = "http://www.finntroll.net")
    val task2 = task withArtist finntroll2.withRef
Лучше? Я считаю, что намного! А работает? Попробуем:
    println(task)
    println(task2)

    Task(Map(IntRef(1) -> Artist(Finntroll,www.finntroll.net,Some(1))),
         Map(IntRef(1) -> Song(Svampfest,0,Set(IntRef(1)),Some(1)),
             IntRef(2) -> Song(Skog,0,Set(IntRef(1)),Some(2))),
         Map())

    Task(Map(IntRef(1) -> Artist(Finntroll,http://www.finntroll.net,Some(1))),
         Map(IntRef(1) -> Song(Svampfest,0,Set(IntRef(1)),Some(1)),
             IntRef(2) -> Song(Skog,0,Set(IntRef(1)),Some(2))),
         Map())
Попробуем ещё раз, но уже так:
    val finntroll = Artist[UuidRef](name = "Finntroll", website = "www.finntroll.net", id = Some(1))
    val svampfest = Song(title = "Svampfest", artists = Set(finntroll.ref), year = 0, id = Some(1))
    val skog      = Song(title = "Skog", artists = Set(finntroll.ref), year = 0, id = Some(2))

    val task      = Task(artistMap = List(finntroll).toRefMap,
                         songMap = List(svampfest, skog).toRefMap,
                         compilationMap = Map() : RefMap[UuidRef, Compilation])

    val task2 = task.using[UuidRef]
    val task3 = task2.using[IntRef]
    val task4 = task3.using[ValueRef]
println(task) выдаст (если отформатировать для красоты):
    Task(Map(UuidRef(32180846-89ed-4fe7-a9c1-11b4f4562a0a) -> Artist(Finntroll,www.finntroll.net,Some(1))),
         Map(UuidRef(94331b40-b9bb-4e58-b840-32fbfa639048) -> Song(Svampfest,0,Set(UuidRef(32180846-89ed-4fe7-a9c1-11b4f4562a0a)),Some(1)),
             UuidRef(0e717a3e-ea6b-437a-acd6-267f01110c98) -> Song(Skog,0,Set(UuidRef(32180846-89ed-4fe7-a9c1-11b4f4562a0a)),Some(2))),
         Map())
println(task2) выдаст уже другие ключи. Это связано с тем, что UuidTaskBuilder генерирует ключи без использования объекта. Используя побочные эффекты (случайные числа). Это плохо. Но проблема в том, что если ключ нельзя взять из объекта, если ключ нельзя взять из воздуха (через побочный эффект), то откуда его вообще тогда брать?! Неоткуда. Смотрим на test2:
    Task(Map(UuidRef(166b78d7-53a3-44d7-a34b-af7c176d1a70) -> Artist(Finntroll,www.finntroll.net,Some(1))),
         Map(UuidRef(e70a4bd9-3a29-47ec-93f2-885105c2973f) -> Song(Svampfest,0,Set(UuidRef(166b78d7-53a3-44d7-a34b-af7c176d1a70)),Some(1)),
             UuidRef(78a353c7-1515-4d08-8c6d-4b995f03e2bc) -> Song(Skog,0,Set(UuidRef(166b78d7-53a3-44d7-a34b-af7c176d1a70)),Some(2))),
         Map())
println(task3) выдаст уже знакомую нам картинку:
    Task(Map(IntRef(1) -> Artist(Finntroll,www.finntroll.net,Some(1))),
         Map(IntRef(1) -> Song(Svampfest,0,Set(IntRef(1)),Some(1)),
             IntRef(2) -> Song(Skog,0,Set(IntRef(1)),Some(2))),
         Map())
println(task4) может пригодится в определённых ситуациях, хоть и выглядит странным:
    Task(Map(ValueRef(Artist(Finntroll,www.finntroll.net,Some(1))) -> Artist(Finntroll,www.finntroll.net,Some(1))),
         Map(ValueRef(Song(Svampfest,0,Set(ValueRef(Artist(Finntroll,www.finntroll.net,Some(1)))),Some(1))) ->
                 Song(Svampfest,0,Set(ValueRef(Artist(Finntroll,www.finntroll.net,Some(1)))),Some(1)),
             ValueRef(Song(Skog,0,Set(ValueRef(Artist(Finntroll,www.finntroll.net,Some(1)))),Some(2))) ->
                 Song(Skog,0,Set(ValueRef(Artist(Finntroll,www.finntroll.net,Some(1)))),Some(2))),
        Map())
А что обновления изменения? Попробуем. Пускай наш task имеет тип Task[Uuid] и соответственно все остальные объекты аналогично параметризованы:
    val finntroll2 = finntroll.copy[UuidRef](website = "http://www.finntroll.net")
    val task2 = task withArtist finntroll2.withRef

    println (task)
    println (task2)
Пробуем и видим:
    Task(Map(UuidRef(fb0b501d-90d9-4347-8cea-fbaf5bf70771) -> Artist(Finntroll,www.finntroll.net,Some(1))),
         Map(UuidRef(9a029528-46e2-4178-bf1e-bf9e35969e26) -> Song(Svampfest,0,Set(UuidRef(fb0b501d-90d9-4347-8cea-fbaf5bf70771)),Some(1)),
             UuidRef(4f7ec03f-6113-4f29-896f-357483af4f39) -> Song(Skog,0,Set(UuidRef(fb0b501d-90d9-4347-8cea-fbaf5bf70771)),Some(2))),
         Map())

    Task(Map(UuidRef(fb0b501d-90d9-4347-8cea-fbaf5bf70771) -> Artist(Finntroll,www.finntroll.net,Some(1)),
             UuidRef(ee008f8c-dfdf-4aa0-a446-b95eb4644226) -> Artist(Finntroll,http://www.finntroll.net,Some(1))),
         Map(UuidRef(9a029528-46e2-4178-bf1e-bf9e35969e26) -> Song(Svampfest,0,Set(UuidRef(fb0b501d-90d9-4347-8cea-fbaf5bf70771)),Some(1)),
             UuidRef(4f7ec03f-6113-4f29-896f-357483af4f39) -> Song(Skog,0,Set(UuidRef(fb0b501d-90d9-4347-8cea-fbaf5bf70771)),Some(2))),
         Map())
Что за бред? Дело в том, что finntroll.copy как и положено, создает новый объект, используя в конструкторе параметры из оригинального объекта в качестве параметра по умолчанию. Но ref не является параметром конструктора. Неявный билдер тоже не относится к первой группе параметров. Соответственно в новом объекте ref будет заново создана билдером. Если бы билдер был предсказуемой чистой функцией (без побочных эффектов), то и результат был бы более предсказуемым. Не обязательно какой надо, ибо даже чистый билдер может возвращать ссылку, используя поменявшееся значение поля объекта (например новый id в БД), но это было бы куда более ожидаемым. Похожая проблема имеется и у ValueRef билдера. Мы, конечно, можем написать вот так:
    val finntroll2 = finntroll.copy[UuidRef](website = "http://www.finntroll.net")
    val task2 = task withArtist (finntroll.ref -> finntroll2)
Но это лишь замаскирует проблему:
    Task(Map(UuidRef(220d2212-243f-4de1-9a61-909a21279d9b) -> Artist(Finntroll,www.finntroll.net,Some(1))),
         Map(UuidRef(9d25c068-22b4-41f6-9168-7a53ad0255fa) -> Song(Svampfest,0,Set(UuidRef(220d2212-243f-4de1-9a61-909a21279d9b)),Some(1)),
             UuidRef(15f00aee-1f64-4c03-8034-01a01b633832) -> Song(Skog,0,Set(UuidRef(220d2212-243f-4de1-9a61-909a21279d9b)),Some(2))),
         Map())

    Task(Map(UuidRef(220d2212-243f-4de1-9a61-909a21279d9b) -> Artist(Finntroll,http://www.finntroll.net,Some(1))),
         Map(UuidRef(9d25c068-22b4-41f6-9168-7a53ad0255fa) -> Song(Svampfest,0,Set(UuidRef(220d2212-243f-4de1-9a61-909a21279d9b)),Some(1)),
             UuidRef(15f00aee-1f64-4c03-8034-01a01b633832) -> Song(Skog,0,Set(UuidRef(220d2212-243f-4de1-9a61-909a21279d9b)),Some(2))),
         Map())
Внешне все как бы хорошо. Но объект finntroll, известный в структуре под старым именем из старой ссылки, будет называть себя совершенно другим именем... Конечно же, мы можем сделать все чуть более правильно. Мы можем убрать UsingRef с объекта и вместо него использовать вот это, приукрасив это вкусными и удобными методами.
    case class Identity[R[_], T[_[_]]](ref : R[T[R]], value : T[R])
Тем самым мы снова отделим наш доменный объект от ссылки, но при этом будем иметь возможность быстро и с минимум кода манипулировать им вместе со ссылкой (Identity это логический аналог Tuple2 с той лишь разницей, что имеет чёткую специализацию). Ещё одним вариантом может быть использование Tuple2 со специализацией, добавленной через value class'ы и implicit методы. Но об это как-нибудь в другой раз, если вообще... Полученное решение весьма удобно, достаточно рабочее, а количество текста и так уже перевалило за 1000 строк....
Подводя итог, я считаю, что универсального решения не получится, но это не значит, что его не стоит искать. В каждом конкретном случае удобно по-разному. И хорошо, когда есть возможность легко и быстро выбирать ;-)

Буду рад услышать ваше мнение об этой проблеме и подходах к её решению!

P.S. Как же все-таки тяжело писать на русском языке. Я так и не понял, какой в русском аналог для proper types (собственные типы?), nullary constructor и т.д...
P.P.S. Ещё можно смотреть в сторону путезависимых типов. Вешать ковариантность, контравариантность на типы я не стал ради упрощения повествования.
P.P.P.S. В работе, кстати, весьма пригождается вот такое:
    type AnyTask = Task[R] forSome { type R[_] }
    type AnyArtist = Artist[R] forSome { type R[_] }
    type AnySong = Song[R] forSome { type R[_] }
    type AnyCompilation = Compilation[R] forSome { type R[_] }