model.hs

{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE OverloadedStrings #-}

import Data.Map.Strict (Map)
import qualified Data.Map.Strict as Map
import Data.List (nub)
import Data.Maybe (mapMaybe)
import Control.Monad (guard)

-- Basic types

type PackageName = String
type Version     = Int  -- Simplify: just use Ints for versions

data VersionRange = VR [Version]  -- Acceptable versions
  deriving (Show, Eq)

data Dependency = Dependency PackageName VersionRange
  deriving (Show, Eq)

data Package = Package
  { pkgName        :: PackageName
  , availableVers  :: [Version]
  , dependencies   :: Version -> [Dependency]  -- deps depend on version
  }

-- Example database of packages
type PackageDB = Map PackageName Package

-- Assignment: a map of chosen versions
type Assignment = Map PackageName Version

-- Check if a version satisfies a version range
satisfies :: Version -> VersionRange -> Bool
satisfies v (VR vs) = v `elem` vs

-- Solve dependencies recursively
solve :: PackageDB -> Assignment -> [Dependency] -> [Assignment]
solve _  assignment [] = pure assignment
solve db assignment (Dependency name vr : rest)
  | Just v <- Map.lookup name assignment
  = if satisfies v vr
      then solve db assignment rest
      else []
  | otherwise = do
      pkg <- maybeToList (Map.lookup name db)
      v <- availableVers pkg
      guard (satisfies v vr)
      let deps = dependencies pkg v
      solve db (Map.insert name v assignment) (deps ++ rest)

-- Utility
maybeToList :: Maybe a -> [a]
maybeToList (Just x) = [x]
maybeToList Nothing  = []

-- Example package database
exampleDB :: PackageDB
exampleDB = Map.fromList
  [ ("A", Package "A" [1,2] $ \_ -> [Dependency "B" (VR [1,2])])
  , ("B", Package "B" [1,2] $ \v -> case v of
      1 -> []
      2 -> [Dependency "C" (VR [1])]
    )
  , ("C", Package "C" [1] $ \_ -> [])
  ]

-- Example invocation
main :: IO ()
main = do
  let goals = [Dependency "A" (VR [1,2])]
      solutions = solve exampleDB Map.empty goals
  mapM_ print solutions