Haskell WalkSat algorithm implementation

0 down vote favorite


I need some help if possible with the following problem.....The WalkSat algorithm takes a formula, a probability 0 =< p =< 1, and a boundary of maximum flips maxflips and returns a model that satisfies the formula or failure. The algorithm begins by assigning truth values to the atoms randomly, ie. generating a random model. Then it proceeds to flip the value of an atom from one of the unsatisfied clauses until it is able to find a model that satisfies the formula or reaches the maximum number of flips. In order to select which atom from the currently selected clause to flip, it follows two strategies:

1. Either flip any atom randomly.
2. Or flip the atom that maximizes the number of satisfied clauses in the formula. The choice to flip randomly is followed with probability p.

1. atomsClause :: Clause ! [Atom] This function must take a Clause and return the set of Atoms of that Clause. Note that the set should not contain any duplicates.
2. atoms :: Formula![Atom] This function must take a Formula return the set of Atoms of a Formula. Note that the set should not contain any duplicates.
3. isLiteral :: Literal ! Clause ! Bool This function returns True if the given Literal can be found within the Clause.
4. flipSymbol :: Model ! Atom ! Model This function must take a Model and an Atom and flip the truth value of the atom in the model.

Here is the code:

module Algorithm where

import System.Random
import Data.Maybe
import Data.List

type Atom = String
type Literal = (Bool,Atom)
type Clause = [Literal]
type Formula = [Clause]
type Model = [(Atom, Bool)]
type Node = (Formula, ([Atom], Model))

atomsClause :: Clause -> [Atom]
atomsClause = undefined

atoms :: Formula -> [Atom]
atoms = undefined

isLiteral :: Literal -> Clause -> Bool
isLiteral = undefined

flipSymbol :: Model -> Atom -> Model
flipSymbol = undefined

Thank you.


I've done the first onet like this and it returns ok....atomsClause xs =nub [a|(b,a)<-xs]...thank you for the reply...but I really need some advice for the second and third one one

 

I am shocked that anyone would think anyone on DP would have even heard of Haskell, much less know how to solve such a problem.

 

well I've done the first 3...I'm looking for some help with the last one.......What on earth do you mean "I am shocked that anyone would think anyone on DP would have even heard of Haskell"?

 

Exactly what is says. The number of people on DP who can do anything more than copy/paste PHP are few and far between. Of all the places to ask Haskell question, it's just bizarre.