Smap

Choose the version you want to view.

Current version:Version message:

Program created.

Click on a tag to show all related programs.

curry functional logic constraints

Click on the badge to open the comment window for viewing and writing comments.

No comments yet.

Created by mh on April 8, 2014

0 users favorited this

Description: A functional logic solution to the graph coloring problem.

Source code (Latest version):

-- Constraint solving (via simple generate and test) in Curry:
-- graph coloring

{-
 This is our actual map:

--------------------------
 |       |        |       |
 |       |   L2   |       |
 |       |        |       |
 |  L1   |--------|  L4   |
 |       |        |       |
 |       |   L3   |       |
 |       |        |       |
 --------------------------
-}

-- The available colors:
data Color = Red | Green | Yellow | Blue

-- Predicate "is the argument a color?"
isColor :: Color -> Success
isColor Red    = success
isColor Yellow = success
isColor Green  = success
isColor Blue   = success

-- The potential solutions: each country must have a color
coloring :: Color -> Color -> Color -> Color -> Success
coloring l1 l2 l3 l4 = isColor l1 & isColor l2 & isColor l3 & isColor l4

-- The correct coloring solutions:
-- adjacent countries myst be have different colors:
correct :: Color -> Color -> Color -> Color -> Success
correct l1 l2 l3 l4
   = diff l1 l2 & diff l1 l3 & diff l2 l3 & diff l2 l4 & diff l3 l4

-- Auxiliary function: negation of ==:
diff :: a -> a -> Success
diff x y = (x == y) =:= False

-- generate+test style solution:
goal1 l1 l2 l3 l4 = coloring l1 l2 l3 l4 & correct l1 l2 l3 l4

-- test+generate style solution:
goal2 l1 l2 l3 l4 = correct l1 l2 l3 l4 & coloring l1 l2 l3 l4

main = goal1 l1 l2 l3 l4 &> (l1,l2,l3,l4)
  where l1,l2,l3,l4 free

Options

Versions

1 version

Tags

4 tags

Comments

0 comments »

Graph coloring

implemented in Curry