Functional programming: How to model relationships?

Question

I wonder how to model relationships in functional programming.

Let's take employees, for example: Employees can have friendships with 0..n colleagues. Friendships are always mutual: if A is a friend of B then B is a friend of A.

How can I model this? I had 3 ideas (listed below). Each of them has downsides.

First try:

type Employee =
  { name : string
    friendships : Employee list
  }

// My list is mutable because I want to be able to update employees.
// I suppose the same problems would occur with e. g. Elmish.
let mutable employees : Employee list = [ (* ... *) ]

(* Downsides:
   Friendships are copies. Changes to an employee would have to be propagated manually.
*)

Second try:

type EmployeeId = int

type Employee =
  { id : EmployeeId
    name : string
    friendships : EmployeeId list
  }

let mutable employees : Employee list = [ (* ... *) ]

(* Downsides:
   Friendships are not modeled as mutual.
   When the friendship of an employee changes,
   the friend's friendships don't change accordingly.
*)

Third try:

type EmployeeId = int

type Friendships = list<EmployeeId * EmployeeId>

type Employee =
  { id : EmployeeId
    name : string
  }

let mutable employees : Employee list = [ (* ... *) ]

(* Downsides:
   After deleting an employee from the list,
   employeeFriendships contain invalid "references"
   to the deleted Employee.
*)

Can this be done better? Thank you.

Answer 1

Using let rec/and might be the most direct way. You would need to introduce laziness by changing friendships to an IEnumerable.

type Employee =
    { 
        name : string
        friendships : seq<Employee>
    }

let rec peter = {name="Peter"; friendships=seq {yield paul; yield mary}}
and paul = {name="Paul"; friendships=seq {yield peter; yield mary}}
and mary = {name="Mary"; friendships=seq {yield peter; yield paul}}

However, the compiler gives the following warning:

This and other recursive references to the object(s) being defined will be checked for initialization-soundness at runtime through the use of a delayed reference. This is because you are defining one or more recursive objects, rather than recursive functions. This warning may be suppressed by using '#nowarn "40"' or '--nowarn:40'.

...which points to an arguably better solution:

type Employee =
    { 
        name : string
        friendships : unit -> Employee list
    }

let rec peter = {name="Peter"; friendships=fun () -> [paul; mary]}
and paul = {name="Paul"; friendships=fun () -> [peter; mary]}
and mary = {name="Mary"; friendships=fun () -> [peter; paul]}

Answer 2

The question is not about functional programming as it involves mutation. An Object-Oriented solution would work well because the important thing is encapsulating the logic in one place and hiding it behind a safe API. Fortunately your choice of F# is still good as F# is a very good OO language.

type Employee(id:int, name:string) =
    static let employees = ResizeArray<Employee>[]()
    static let friendships = ResizeArray<int*int>()
    static let getEmployee(eid:EmployeeId) = employees |> Seq.find(fun e -> e.Id = eid)
    member t.Id = id
    member t.Name = name
    member t.Friends =
        let friendIds = friendships ...
        friendIds |> Array.map getEmployee
    static member Employees = employees |> Array.ofSeq
    static member Add = employees.Add
    static member Remove(e:Employee) =
        employees.Remove e |> ignore
        friendships |> Seq.filter (fun (a,b) -> a = e.Id || b = e.Id)
        |> Seq.iter (friendships.Remove >> ignore)
    static member AddFriend(e1:Employee, e2:Employee) = ...

You could do the same with records and/or modules too by making things private.