module Unison.Util.TransitiveClosure where

import Data.Set qualified as Set
import Unison.Prelude

transitiveClosure ::
  forall m a.
  (Monad m, Ord a) =>
  (a -> m (Set a)) ->
  Set a ->
  m (Set a)
transitiveClosure :: forall (m :: * -> *) a.
(Monad m, Ord a) =>
(a -> m (Set a)) -> Set a -> m (Set a)
transitiveClosure a -> m (Set a)
getDependencies Set a
open =
  let go :: Set a -> [a] -> m (Set a)
      go :: Set a -> [a] -> m (Set a)
go Set a
closed [] = Set a -> m (Set a)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Set a
closed
      go Set a
closed (a
h : [a]
t) =
        if a -> Set a -> Bool
forall a. Ord a => a -> Set a -> Bool
Set.member a
h Set a
closed
          then Set a -> [a] -> m (Set a)
go Set a
closed [a]
t
          else do
            Set a
deps <- a -> m (Set a)
getDependencies a
h
            Set a -> [a] -> m (Set a)
go (a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
Set.insert a
h Set a
closed) (Set a -> [a]
forall a. Set a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList Set a
deps [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a]
t)
   in Set a -> [a] -> m (Set a)
go Set a
forall a. Set a
Set.empty (Set a -> [a]
forall a. Set a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList Set a
open)

transitiveClosure' :: (Ord a) => (a -> Set a) -> Set a -> Set a
transitiveClosure' :: forall a. Ord a => (a -> Set a) -> Set a -> Set a
transitiveClosure' a -> Set a
f Set a
as = Identity (Set a) -> Set a
forall a. Identity a -> a
runIdentity (Identity (Set a) -> Set a) -> Identity (Set a) -> Set a
forall a b. (a -> b) -> a -> b
$ (a -> Identity (Set a)) -> Set a -> Identity (Set a)
forall (m :: * -> *) a.
(Monad m, Ord a) =>
(a -> m (Set a)) -> Set a -> m (Set a)
transitiveClosure (Set a -> Identity (Set a)
forall a. a -> Identity a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Set a -> Identity (Set a))
-> (a -> Set a) -> a -> Identity (Set a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Set a
f) Set a
as

transitiveClosure1 ::
  forall m a.
  (Monad m, Ord a) =>
  (a -> m (Set a)) ->
  a ->
  m (Set a)
transitiveClosure1 :: forall (m :: * -> *) a.
(Monad m, Ord a) =>
(a -> m (Set a)) -> a -> m (Set a)
transitiveClosure1 a -> m (Set a)
f a
a = (a -> m (Set a)) -> Set a -> m (Set a)
forall (m :: * -> *) a.
(Monad m, Ord a) =>
(a -> m (Set a)) -> Set a -> m (Set a)
transitiveClosure a -> m (Set a)
f (a -> Set a
forall a. a -> Set a
Set.singleton a
a)

transitiveClosure1' :: (Ord a) => (a -> Set a) -> a -> Set a
transitiveClosure1' :: forall a. Ord a => (a -> Set a) -> a -> Set a
transitiveClosure1' a -> Set a
f a
a = Identity (Set a) -> Set a
forall a. Identity a -> a
runIdentity (Identity (Set a) -> Set a) -> Identity (Set a) -> Set a
forall a b. (a -> b) -> a -> b
$ (a -> Identity (Set a)) -> a -> Identity (Set a)
forall (m :: * -> *) a.
(Monad m, Ord a) =>
(a -> m (Set a)) -> a -> m (Set a)
transitiveClosure1 (Set a -> Identity (Set a)
forall a. a -> Identity a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Set a -> Identity (Set a))
-> (a -> Set a) -> a -> Identity (Set a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Set a
f) a
a