DCFL- Communication Free Learning-based constraint solver

Safe HaskellNone





data Distribution Source

Probability distribution; generally associated with a Variable.

data Values Source

The integer values a Variable can take on.


data Variable Source

Each Variable has a finite set of possible values, a value it holds and a probability distribution over the set of possible values.

data ConstraintEl Source

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


data Solved Source

Return value of solve.


initDistribution :: Int -> Distribution Source

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].

cummDistribution :: Distribution -> Distribution Source

Creates a cummulative Distribution out of a given Distribution.

checkSolved :: [Variable] -> Bool Source

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


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

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

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

Randomize all the variables in a list.

printVariables :: [Variable] -> [IO ()] Source

Print variables.


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

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

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

Get the constraint functions out of a list of ConstraintEls.


Serial/Single Threaded

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

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. See solveThreaded for a parallelized implementation.

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

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

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

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

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

Update the variable set n number of times.


solveParallel :: [Variable] -> [ConstraintEl] -> IO Solved Source

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.

updateEachParallel :: [Variable] -> [ConstraintEl] -> IO [Variable] Source

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