Geek asks and answers

Recursively modifying parts of a data structure in Haskell

Hi guys, I'm new to Haskell, I would like to create a Haskell program that can apply DeMorgan laws for logical expressions. The problem is that I cannot change this expression to a new expression (after applying DeMorgan laws)

To be specific here, my data structure

data LogicalExpression = Var Char
        | Neg LogicalExpression
        | Conj LogicalExpression LogicalExpression
        | Disj LogicalExpression LogicalExpression
        | Impli LogicalExpression LogicalExpression
        deriving(Show)

I would like to create a function that takes a "Boolean expression" and returns a "Boolean expression" after applying the laws of DeMorgan.

For example, when I find this pattern: Neg (Conj (Var 'a') (Var 'b')) in a logical expression, I need to convert it to Conj (Neg (Var 'a') Neg (Var 'b')) .

The idea is simple, but so hard to implement in haskell, it seems to be trying to make a function (let it call Z) that looks for x and converts it to y, so if Z is set to "vx", it converts it instead of "vy" instead of strings it takes a “logical expression” in the data structure, and instead of x it takes the template that I mentioned, and again spits out the entire logical expression, but with the template changed.

PS: I want the function to take any logical expression Complex and simplify it using the laws of DeMorgan

Any clues?

Thanks in advance.

+3
source share
4 answers

(luqui) , , . , , , .

, , . 2- , , , :

data LogicalExpression
    = Var Char
    | Neg LogicalExpression
    | Conj LogicalExpression LogicalExpression
    | Disj LogicalExpression LogicalExpression
    | Impl LogicalExpression LogicalExpression
deriving (Show)

, - :

class Compos a where
    compos' :: (a -> a) -> a -> a

instance Compos LogicalExpression where
    compos' f (Neg e)    = Neg (f e)
    compos' f (Conj a b) = Conj (f a) (f b)
    compos' f (Disj a b) = Disj (f a) (f b)
    compos' f (Impl a b) = Impl (f a) (f b)
    compos' _ t = t

, :

elimImpl :: LogicalExpression -> LogicalExpression
elimImpl (Impl a b) = Disj (Not (elimImpl a)) (elimImpl b)
elimImpl t = compos' elimImpl t -- search deeper

, luqui, . , , , , , (, )

nnf :: LogicalExpression -> LogicalExpression
nnf (Neg (Conj a b)) = Disj (nnf (Neg a)) (nnf (Neg b))
nnf (Neg (Disj a b)) = Conj (nnf (Neg a)) (nnf (Neg b))
nnf (Neg (Neg a))    = nnf a
nnf t                = compos' nnf t -- search and replace

- , , , , , , . , Neg , , , , Neg , .

import Control.Applicative
import Control.Monad.Identity

class Compos a where
    compos :: Applicative f => (a -> f a) -> a -> f a

compos' :: Compos a => (a -> a) -> a -> a
compos' f = runIdentity . compos (Identity . f) 


instance Compos LogicalExpression where
    compos f (Neg e)    = Neg <$> f e
    compos f (Conj a b) = Conj <$> f a <*> f b
    compos f (Disj a b) = Disj <$> f a <*> f b
    compos f (Impl a b) = Impl <$> f a <*> f b
    compos _ t = pure t

, , , IO .

, , , , deMorgan , , .

, , , , , , compos .

+7

, , . :

-- no need to call self on the top-level structure,
-- since deMorgan is never applicable to its own result
deMorgan (Neg (a `Conj` b))  =  (deMorgan $ Neg a) `Disj` (deMorgan $ Neg b)
deMorgan (Neg (a `Disj` b))  =  (deMorgan $ Neg a) `Conj` (deMorgan $ Neg b)
deMorgan (Neg a)             =  Neg $ deMorgan a
deMorgan (a `Conj` b)        =  (deMorgan a) `Conj` (deMorgan b)
-- ... etc.

- , , Haskell.

(Btw., , P -> Q not P or Q Impli. .)

+6

. , , :

deMorgan (Neg (Var x)) = Neg (Var x)
deMorgan (Neg (Neg a)) = deMorgan a
deMorgan (Neg (Conj a b)) = Disj (deMorgan (Neg a)) (deMorgan (Neg b))
-- ... etc. match Neg against every constructor
deMorgan (Conj a b) = Conj (deMorgan a) (deMorgan b)
-- ... etc. just apply deMorgan to subterms not starting with Neg

, Neg Var .

: .. , "" , . , ( ), . , - Apply. SKI Lambda.

+4

deMorgan. ():

 deMorgan' z@(Var x) = z
 deMorgan' (Neg (Conj x y)) = (Disj (Neg x) (Neg y))
 deMorgan' (Neg (Disj x y)) = (Conj (Neg x) (Neg y))
 deMorgan' z@(Neg x) = z
 deMorgan' (Conj x y) = Conj x y
 deMorgan' (Disj x y) = Disj x y

:

 let var <- (Conj (Disj (Var 'A') (Var 'B')) (Neg (Disj (Var 'D') (Var 'E'))))
 *Main> deMorgan' var
 Conj (Disj (Var 'A') (Var 'B')) (Neg (Disj (Var 'D') (Var 'E')))

, subexpressiosn (x ys).

+2

More articles:


All Articles