Graph tie the knot

linkGraph.hs

module LinkGraph where
import Data.IntMap
import Data.Function
import Data.Maybe
import Prelude hiding (lookup)

data Fix f = Rec { unRec :: f (Fix f)}

unsafeLinkGraph :: Functor f => IntMap (f Int) -> IntMap (Fix f)
unsafeLinkGraph g =
  fix $ \res -> fmap (Rec . (fmap (fromJust . flip lookup res))) g

isCompleteGraph :: Foldable f => IntMap (f Int) -> Bool
isCompleteGraph g = all (all (isJust . flip lookup g)) g

linkGraph :: (Foldable f, Functor f) => IntMap (f Int) -> Maybe (IntMap (Fix f))
linkGraph m | isCompleteGraph m = Just $ unsafeLinkGraph m
linkGraph _ = Nothing