Unique list of interdependent services

Hi all,

I have a set of services, each one having zero or more dependencies on other services from the set. I would like to, given a list of services as input, to calculate the unique list of these services + their dependencies.

What I came up with so far is:

let Prelude = ./Prelude.dhall

let Service = < database | service1 | service2 >

let Service/equals =
      let handlers = { database = False, service1 = False, service2 = False }

      let isDatabase = \(s : Service) -> merge (handlers // { database = True}) s
      let isService1 = \(s : Service) -> merge (handlers // { service1 = True}) s
      let isService2 = \(s : Service) -> merge (handlers // { service2 = True}) s

      let makeEquals =
            \(predicates : List (Service -> Bool))
        ->  \(l : Service)
        ->  \(r : Service)
        ->  let apply = \(predicate : Service -> Bool) -> predicate l && predicate r
            in
            Prelude.Bool.or (
              Prelude.List.map (Service -> Bool) Bool apply predicates
            )

      let equals = makeEquals [ isDatabase, isService1, isService2 ]

      let example0 = assert : equals Service.database Service.service1 === False
      let example1 = assert : equals Service.database Service.service2 === False
      let example2 = assert : equals Service.service1 Service.service2 === False
      let example3 = assert : equals Service.database Service.database === True
      let example4 = assert : equals Service.service1 Service.service1 === True
      let example5 = assert : equals Service.service2 Service.service2 === True

      in  equals

let uniqueServices =
      \(ls : List Service)
  ->  let concatUnique =
            \(s : Service)
        ->  \(rl : List Service)
        ->  if (Prelude.List.any Service (Service/equals s) rl)
            then rl
            else rl # [ s ]
      in  Prelude.List.fold
            Service
            ls
            (List Service)
            concatUnique
            ([] : List Service)

let services =
      { database.dependencies = [] : List Service
      , service1.dependencies = [ Service.database ]
      , service2.dependencies = [ Service.database, Service.service1 ]
      }

let makeServiceList =
      \(ls : List Service)
  ->  uniqueServices
        (Prelude.List.concatMap
          Service
          Service
          (\(s : Service) -> [ s ] # (merge services s).dependencies)
          ls)

let example0 = assert : makeServiceList [ Service.database ] === [ Service.database ]
let example1 = assert : makeServiceList [ Service.service1 ] === [ Service.database, Service.service1 ]
let example2 = assert : makeServiceList [ Service.service2 ] ===
      [ Service.service1, Service.database, Service.service2 ]
let example3 = assert : makeServiceList [ Service.service1, Service.service2 ] ===
      [ Service.service1, Service.database, Service.service2 ]
let example4 = assert : makeServiceList [ Service.database, Service.service2 ] ===
      [ Service.service1, Service.database, Service.service2 ]

in  makeServiceList

(the equality implementation is based on Discussion: Text equality · Issue #164 · dhall-lang/dhall-lang · GitHub)

Note that I don’t need to resolve the dependency ordering, I just need to compute the unique list of services to output (and feed them to e.g., docker-compose which will decide on the startup order).

This feels very inefficient (even though for the number Service's in my use case it shouldn’t be an issue.)

Is this a sane thing to do? Is there a more elegant/efficient way to express this?

Thanks!

Yeah, anything involving equality or sets is going to have this sort of inefficiency. I don’t believe there is a more elegant way to do this with the currently available primitives.