Data.DCFL

Documentation

data Distribution

Probability distribution; generally associated with a Variable.

Constructors

Distribution

Fields

probab :: [Double]

Instances

Show Distribution

NFData Distribution

data Values

The integer values a Variable can take on.

Constructors

Values [Integer]

Instances

Show Values

data Variable

Each variable has a finite set of possible values, a value it holds at a given point and a probability distribution over the set of possible values.

Constructors

Variable

Fields

possible :: [Int]

valueIndex :: Int

distr :: Distribution

Instances

Show Variable

NFData Variable

data ConstraintEl

Each constraint function ([Int] -> Bool) is associated with a certain set of variables. ConstraintEl represents this relationship for a constraint function.

Constructors

ConstraintEl

Fields

variableIndices :: [Int]

constraint :: [Int] -> Bool

Instances

Show ConstraintEl

data Solved

Return value of solve.

Constructors

Solved

Fields

variables :: [Variable]

iterationCount :: Int

width :: Num b => Distribution -> b

Returns the number of finite values that a Distribution is over.

b :: Double

Constant, as defined in the research paper "Decentralized Constraint Satisfaction" Duffy, et al.

oneIfEqual :: (Num a1, Eq a) => a -> a -> a1

Internally called function.

replicateDouble :: Int -> Double -> [Double]

initDistribution :: Int -> Distribution

Initialize a distribution with each possible value having the same probability. For example, initDistribution 5 gives Distribution [0.2, 0.2, 0.2, 0.2, 0.2].

failureCurrProb :: t -> Double -> Double

Adjust probability for the value which has just failed a constraint.

failureOtherProb :: Double -> Double -> Double

Adjust probability for values other than the one that just failed a constraint.

failureProb :: Eq a => Double -> a -> Double -> a -> Double

Adjust probability of taking on a value for a certain Variable given that a constraint was just failed.

updateProb :: (Num a, Eq a, Enum a) => Distribution -> a -> Bool -> Distribution

Given a distribution, update it based on the value of success. If successful, then set the probability of the current value to 1.0 and the probability for every other value to 0.0. Otherwise, update it with failureProb.

updateVariableProb :: Variable -> Bool -> Variable

Same as updateProb, but rather than returning a Distribution, this function returns a Variable.

cummDistributionIter :: Distribution -> Int -> Double -> [Double]

Internal iteration function used by cummDistribution.

cummDistribution :: Distribution -> Distribution

Creates a cummulative Distribution out of a given Distribution.

getValueIndex :: Distribution -> Double -> Int

Given a cummulative Distribution, this function returns the where a random value should be "placed" within the Distribution.

randomNum :: IO Double

Returns a single random number between 0.0 and 1.0.

randomizeVariable :: Variable -> IO Variable

Randomize the value of a Variable.

evalConstraint :: ([Int] -> Bool) -> [Int] -> Bool

Evaluate one constraint with a list of values.

evalConstraints :: [[Int] -> Bool] -> [Int] -> Bool

Evaluate the set constraint functions constraints with a list of values.

applyAt :: (Num b1, Eq b1, Enum b1) => (b -> b) -> b1 -> [b] -> [b]

Apply a function at only one index of a list. Internal function.

getConstraintsFor :: Int -> [ConstraintEl] -> [[Int] -> Bool]

Get the Constraints associated with a Variable of index n in the list of Variables.

justConstraints :: [ConstraintEl] -> [[Int] -> Bool]

Get the constraint functions out of a list of ConstraintEls.

getValues :: [Variable] -> [Int]

Get a list of values from a list of Variables.

randomizeSingle :: Int -> [Variable] -> [IO Variable]

Randomizes the value of a single Variable in a list of Variable.

randomize :: [Variable] -> [IO Variable]

Randomize all the variables in a list.

printVariables :: Show a => [a] -> [IO ()]

Print variables.

update :: Int -> [Variable] -> [ConstraintEl] -> IO [Variable]

Either randomize or let a variable stay, depending on what the constraint check tells us.

updateEach' :: [Variable] -> [ConstraintEl] -> [Int] -> IO [Variable]

Update each variable in the indices list once. Internal function used by updateEach.

updateEach :: [Variable] -> [ConstraintEl] -> IO [Variable]

Update each variable in the variable set based on the constraint set value.

updateEachTimes :: [Variable] -> [ConstraintEl] -> Int -> IO [Variable]

Update the variable set n number of times.

checkDistrSolved :: Distribution -> Bool

Checks if every probability in the distribution is either 0 or 1. If it is, then, all constraints have been satisfied.

checkSolved :: [Variable] -> Bool

Check if the constraints have been solved by looking at the distributions of each Variable.

solve :: [Variable] -> [ConstraintEl] -> IO Solved

This is the moost important function within this library. Given a list of Variable and a list of ConstraintEl, the library uses the Communcation Free Learning Algorithm to return a Solved value. Note that the implementation is not parallelized./

updateMapF :: [Variable] -> [ConstraintEl] -> Int -> IO Variable

updateEachThreaded :: Int -> [Variable] -> [ConstraintEl] -> IO [Variable]

Updates each variable in the variable set a number of times and does each variable's update in a separate thread.

updateEachTimesThreaded :: Int -> [Variable] -> [ConstraintEl] -> Int -> IO [Variable]

solveThreaded :: Int -> [Variable] -> [ConstraintEl] -> IO Solved

Solve the constraint set in parallel using Haskell threads. In order for the solution to be parallelized, the program using DCFL must be compiled with GHC's '-threaded' option.