Haskell function help

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

Haskell function help

Houdini
This post was updated on .
CONTENTS DELETED
The author has deleted this message.
Reply | Threaded
Open this post in threaded view
|

Re: Haskell function help

Daniel Fischer
Let me see if I understand that correctly.

On Tuesday 01 February 2011 12:18:06, Houdini wrote:
>  module Algorithm where
>
> import System.Random import Data.Maybe import Data.List
>
> type Atom = String
> type Literal = (Bool,Atom)

(True "P") correspnds to "P", (False, "P") to "not P"?

> type Clause = [Literal]

A Clause is the disjunction of the literals appearing in it?
So [(True,"P"),(False,"Q")] translates to (p || not q) ?

> type Formula = [Clause]

A Formula is the conjunction of its Clauses?
[[(True,"P"),(False,"Q")],[(True,"R")]] translates to
(p || not q) && r ?

> type Model = [(Atom, Bool)]

> type Node = (Formula, ([Atom], Model))

No idea what that would mean

>
> atomsClause :: Clause -> [Atom]
> --This function takess a Clause and return the set of Atoms of that
Clause.
> atomsClause = nub . map snd
>
> atoms :: Formula -> [Atom]
> atoms = nub . map snd

Doesn't type check, should be

atoms = nub . map snd . concat

> --This function takes a Formula returns the set of Atoms of a Formula
>
> isLiteral :: Literal -> Clause -> Bool
> isLiteral = isLiteral = any . (==)
> --This function returns True if the given Literal can be found within the
Clause.
>
> flipSymbol :: Model -> Atom -> Model
> flipSymbol m a = map f m
>   where
>     f (atom, value) =
>         if a == atom
>              then (atom, not value) else (atom, value)
> -- this function takes a Model and an Atom and flip the truthvalue of the
atom in the model
>
> assign :: (Atom,Bool)->Formula->Formula
> assign = undefined--------any advice here? Thank you

You have to find what should happen on
- Literals
- Clauses
- Formulae
(not necessarily in that order)

If the Formula is empty, I suppose nothing should be done,

assign _ [] = []

if there are Clauses,

assign (atom,value) (clause:rest)

should do the assignment in the Clause and depending on the outcome, remove
the (modified) Clause and assign in the rest, or prepend the modified
Clause to the result of assigning in the rest,

assign (atom,value) (clause:rest) =
  case assignClause (atom,value) clause of
    Nothing -> assign (atom,value) rest
    Just cl -> cl : assign (atom,value) rest

Now for assigning in a Clause. You get a trivially satisfied Clause, which
we'll indicate by a Nothing return value, or a reduced Clause (which may be
empty and hence unsatisfiable).

assignClause :: (Atom,Bool) -> Clause -> Maybe Clause
assignClause (atom,value) clause =
  case partition ((== atom) . snd) clause of
       -- the atom doesn't appear in the clause, nothing to do
    ([],_) -> Just clause
       -- the atom appears in the clause, we have see whether
       -- assigning produces a True or only False
    (ms,cs)
       -- a True, clause is satisfied
       | any (satisfied value) (map fst ms) -> Nothing
       -- all occurrences lead to a False, we have to keep the other
Literals
       | otherwise -> Just cs

Now, what happens for Literals? We only call this for matching Atoms, so we
need only care for the Bools. If the Literal has the form (True,p), we get
value, otherwise we get (not value):

satisfied :: Bool -> Bool -> Bool
satisfied value True = value -- Literal in positive form
staisfied value False = not value -- the Literal was negated

Now we can write satisfied shorter: satisfied = (==)
Or better, now we know what it is supposed to do, remove it altogether and
make the guard condition in assignClause

     (ms,cs)
       | any (== value) (map fst ms) -> Nothing
       | otherwise -> Just cs


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Haskell function help

Daniel Fischer
In reply to this post by Houdini
Just a few further remarks,
- partition requires the import of Data.List
- with an import of Data.Maybe, assign can be much shorter stated as

assign (atom,value) formula =
    catMaybes (map (assignClause (atom,value)) formula)


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Haskell function help

Houdini
This post was updated on .
In reply to this post by Daniel Fischer
CONTENTS DELETED
The author has deleted this message.
Reply | Threaded
Open this post in threaded view
|

Re: Haskell function help

Houdini
This post was updated on .
CONTENTS DELETED
The author has deleted this message.
Reply | Threaded
Open this post in threaded view
|

Re: Haskell function help

Houdini
This post was updated on .
CONTENTS DELETED
The author has deleted this message.
Reply | Threaded
Open this post in threaded view
|

Re: Haskell function help

Carsten Schultz
Am 01.02.11 14:05, schrieb Houdini:
>
> that is really.....complicated...hmm

Maybe you find


assign :: (Atom,Bool)->Formula->Formula

assign _ [] = []
assign (a,b) (c:cs)
       | (b,a) `elem` c = cs'
       | otherwise = filter ((/= a).snd) c : cs'
       where cs' = assign (a,b) cs


easier to read.  With


example :: Formula
example = [[p,q,r],[n p,q,n r],[p,n q]]
    where p = l "P"
          q = l "Q"
          r = l "R"
          l a = (True, a)
          n (b,a) = (not b, a)


we get

*Algorithm> example
[[(True,"P"),(True,"Q"),(True,"R")],[(False,"P"),(True,"Q"),(False,"R")],[(True,"P"),(False,"Q")]]
*Algorithm> assign ("P", True) example
[[(True,"Q"),(False,"R")]]
*Algorithm> assign ("P", False) example
[[(True,"Q"),(True,"R")],[(False,"Q")]]

But note that we also get

*Algorithm> assign ("P", False)
[[(True,"P"),(True,"Q"),(True,"R")],[(False,"P"),(True,"Q"),(False,"R")],[(True,"P")]]
[[(True,"Q"),(True,"R")],[]]

So this is not reduced to [[]].

hth C.



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Haskell function help

Houdini
This post was updated on .
CONTENTS DELETED
The author has deleted this message.
Reply | Threaded
Open this post in threaded view
|

Re: Haskell function help

Carsten Schultz
Am 01.02.11 22:17, schrieb Houdini:
>
> How about this...?
> assign :: (Atom,Bool) -> Formula -> Formula
> assign (a,b) = map . (map f) where
>    f (x,b) = (x,(x==a)&&b)

How about testing it?


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Haskell function help

Houdini
This post was updated on .
CONTENTS DELETED
The author has deleted this message.
Reply | Threaded
Open this post in threaded view
|

Re: Haskell function help

Carsten Schultz
Am 01.02.11 23:39, schrieb Houdini:
>
> I did,obvioulsy....and it works,...

Are you sure?


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Haskell function help

Houdini
This post was updated on .
CONTENTS DELETED
The author has deleted this message.