Normalized and immutable data model

Question

How does Haskell solve the "normalized immutable data structure" problem?

For example, let's consider a data structure representing ex girlfriends/boyfriends:

data Man = Man {name ::String, exes::[Woman]}

data Woman = Woman {name :: String, exes::[Man]}

What happens if a Woman changes her name and she had been with 13 man? Then all the 13 man should be "updated" (in the Haskell sense) too? Some kind of normalization is needed to avoid these "updates".

This is a very simple example, but imagine a model with 20 entities, and arbitrary relationships between them, what to do then?

What is the recommended way to represent complex, normalized data in an immutable language?

For example, a Scala solution can be found here (see code below), and it uses references. What to do in Haskell?

class RefTo[V](val target: ModelRO[V], val updated: V => AnyRef) {
  def apply() = target()
}

I wonder, if more general solutions like the one above (in Scala) don't work in Haskell or they are not necessary? If they don't work, then why not? I tried to search for libraries that do this in Haskell but they don't seem to exist.

In other words, if I want to model a normalized SQL database in Haskell (for example to be used with acid-state) is there a general way to describe foreign keys? By general I mean, not hand coding the IDs as suggested by chepner in the comments below.

EDIT:

Yet in other words, is there a library (for Haskell or Scala) that implements an SQL/relational database in memory (possibly also using Event Sourcing for persistence) such that the database is immutable and most of the SQL operations (query/join/insert/delete/etc.) are implemented and are type-safe ? If there is not such a library, why not ? It seems to be a pretty good idea. How should I create such a library ?

EDIT 2:

Some related links:

• https://realm.io/news/slug-peter-livesey-managing-consistency-immutable-models/
• https://tonyhb.gitbooks.io/redux-without-profanity/content/normalizer.html
• https://github.com/agentm/project-m36
• https://github.com/scalapenos/stamina
• http://www.haskellforall.com/2014/12/a-very-general-api-for-relational-joins.html

Answer 1

The problem is you are storing data and relationships in the same type. To normalise, you need to separate. Relational databases 101.

newtype Id a = Id Int -- Type-safe ID.
data Person = Person { id :: Id Person, name :: String }
data Ex = Ex { personId :: Id Person, exId :: Id Person }

Now if a person changes their name, only a single Person value is affected. The Ex entries don't care about peoples' names.

Answer 2

Project M63 comes pretty close to what I was looking for. It is written in Haskell.

A more lightweight Haskell solution is outlined in Gabriel Gonzalez's post "A very general API for relational joins".