Как инициализировать и "модифицировать" циклическую постоянную структуру данных в Scala?

Question

Я искал и нашел некоторую информацию по этой теме, но ответы либо сбивают с толку, либо не применимы.

У меня есть что-то вроде этого:

class Thing (val name:String, val refs:IndexedSeq[Ref])
class Ref (val name:String, val thing:Thing)

Теперь я хочу сказать, загрузить файл, разобрать его и заполнить эту структуру данных из него. Будучи неизменным и циклическим, как можно это сделать?

Также, скажем, я заполнил эту структуру данных, теперь я хочу ее изменить, например, изменить rootThing.refs(3).name, как можно это сделать?

---

Спасибо за идеи, размещенные здесь. На данный момент я думаю, что если кто-то действительно хочет иметь постоянные структуры данных для чего-то подобного, подумать нестандартно и подумать, какие вопросы клиентскому коду нужно будет задать. Поэтому вместо того, чтобы думать об объектах и ​​полях, думайте о запросах, индексах и тому подобном. Начнем с того, что я думаю с точки зрения: существует ли двунаправленная многокарточная постоянная структура данных?

Answer 1

Для одной циклической ссылки вы можете использовать lazy:

lazy val t: Thing = new Thing("thing", Vector(new Ref("ref", t)))

Однако очевидно, что это усложняется со многими связями.

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

Может быть, использование косвенного обращения - это вариант для вас, скажем, для ссылки на объекты через идентификатор вместо фактической ссылки на объект scala?

case class ThingByID(id: Int, name: String, refs: IndexedSeq[RefByID])
case class RefByID(name: String, thingID: Int)

Затем вы можете после загрузки вашего файла собрать вещи по их идентификатору в неизменяемую карту (например, collection.immutable.IntMap) и найдите их, когда пришли с реф.

РЕДАКТИРОВАТЬ

Майлз прав насчет первого случая lazy val t, Ведь вам нужны параметры по имени, как в его ответе.

class Thing(val name: String, val refs: IndexedSeq[Ref])
class Ref(val name: String, _thing: => Thing) { def thing = _thing }

val t: Thing = new Thing("thing", Vector(new Ref("ref", t)))

Answer 2

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

scala> class Thing (val name:String, refs0: => IndexedSeq[Ref]) { lazy val refs = refs0 } ; class Ref (val name:String, thing0: => Thing) { lazy val thing = thing0 }
defined class Thing
defined class Ref

scala> val names = Vector("foo", "bar", "baz")                                                                                                                       
names: scala.collection.immutable.Vector[java.lang.String] = Vector(foo, bar, baz)

scala> val rootThing : Thing = new Thing("root", names.map { new Ref(_, rootThing) })
rootThing: Thing = Thing@1f7dab1

scala> rootThing.refs(1).name
res0: String = bar

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

Answer 3

Существует альтернативный подход, который требует переосмысления представления ассоциаций объектов: вместо сохранения ассоциаций между объектами внутри самих объектов (как это обычно делается в коде OO) добавьте их впоследствии в отдельный слой в виде Maps.

Поскольку ко времени создания ассоциаций все узлы в графе объектов существуют, неизменные двунаправленные ассоциации могут быть легко созданы с помощью Карт.

scala> class Thing (val name:String)
defined class Thing

scala> class Ref (val name:String)
defined class Ref

scala> new Thing("Thing1")
res0: Thing = Thing@5c2bae98

scala> new Ref("Ref1")
res1: Ref = Ref@7656acfa       

scala> val thing2Ref = Map(res0 -> res1)
thing2Ref: scala.collection.immutable.Map[Thing,Ref] = Map(Thing@5c2bae98 -> Ref
@7656acfa)

scala> val ref2Thing = Map(res1 -> res0)
ref2Thing: scala.collection.immutable.Map[Ref,Thing] = Map(Ref@7656acfa -> Thing
@5c2bae98)

Если задуматься, этот подход похож на работу реляционных баз данных. Многозначные ассоциации между таблицами хранятся не в самих строках, а в отдельных индексах. Даже если индексы ассоциации отсутствуют и запрос разрешен с помощью сканирования таблицы, он использует индексы первичного ключа для поиска всех строк-кандидатов для результата.

Преимущество этого стиля заключается в том, что ассоциации могут добавляться или изменяться, не затрагивая сами объекты, и разные ассоциации могут использоваться для разных аудиторий / сценариев использования. Недостатком является то, что карта ассоциаций напрямую недоступна в тех случаях, когда ассоциации начинаются; это должно быть передано и предоставлено отдельно.

Answer 4

Неизменяемые структуры данных могут быть полностью инициализированы их конструктором, или вы можете согласиться с необходимостью продолжать копировать структуру при изменении ее свойств. Итак, чтобы ответить на первую часть вопроса, вы загружаете данные в неизменяемую структуру данных, определяя конструктор, который принимает всю информацию в вашей базе данных, или гарантируете, что вам известны циклические подграфы:

Я думаю, что циклические структуры данных не обязательно являются полностью циклическими. Если вы представляете сеть указателей, которую содержит один экземпляр / состояние, у вас может быть подграф, содержащий родительский и дочерний элементы, которые указывают друг на друга, но нет других циклических структур. В этом сценарии копирование экземпляра 1 для ленивого создания экземпляра 2 с другим родительским узлом (например) потребует копирования родительского и дочернего узлов, поскольку они образуют циклический подграф. Но ссылки, содержащиеся в дочернем элементе, отличном от родительского, могут по-прежнему быть ссылками на те же неизменяемые структуры, что и первый экземпляр.

Например, мой классный дом имеет ссылку на дверь, окно и крышу. Дверь имеет цвет и ссылку на дом, дом имеет размер, а крыша имеет шаг. Поэтому я создаю дом для бобов с зеленой дверью, большим окном и плоской крышей. Фактически, поскольку все они неизменны, теоретически существует только одно большое окно - все дома с большими окнами имеют одно и то же окно. Второй экземпляр, janes House, похож на bobs House, но с остроконечной крышей. Поэтому, если я скажу janes House = bobs House.withRoof (gabled), то я должен получить новый экземпляр House, с новой (также зеленой) дверью и новой (gabled) крышей, но с тем же окном.

Таким образом, если janes House оценивается лениво, ему нужно только создать новый дом, если на него ссылаются дверь или крыша. Если запрашивается janes House.Window, ему вообще не нужно создавать новый дом - нужен только bobs House.

tl; dr: Вы можете иметь постоянные (ленивые) циклические структуры данных, но только если вы можете найти в них нециклические подграфы, то есть это не цепочка.