Skip to content

Instantly share code, notes, and snippets.

@5outh
Created November 13, 2013 17:04
Show Gist options
  • Save 5outh/7452588 to your computer and use it in GitHub Desktop.
Save 5outh/7452588 to your computer and use it in GitHub Desktop.
DeMorgan
{-# LANGUAGE NoMonomorphismRestriction #-}
import Text.ParserCombinators.Parsec
import Text.ParserCombinators.Parsec.Token hiding (parens)
import Text.ParserCombinators.Parsec.Expr
import Control.Applicative hiding ((<|>))
import Control.Monad
import Prelude hiding (not)
data Expr = Not Expr | And Expr Expr | Or Expr Expr | Var Char | SubExpr Expr deriving Eq
not :: Expr -> Expr
not (Not e) = e
not (And e1 e2) = Or (not e1) (not e2)
not (Or e1 e2) = And (not e1) (not e2)
not (Var c) = Not (Var c)
not (SubExpr e) = not e
instance Show Expr where
show (Not e) = "NOT " ++ show e
show (And e1 e2) = show e1 ++ " AND " ++ show e2
show (Or e1 e2) = show e1 ++ " OR " ++ show e2
show (Var c) = [c]
show (SubExpr e) = "(" ++ show e ++ ")"
parseExpr :: String -> Either ParseError Expr
parseExpr = parse expr ""
where expr = buildExpressionParser operators term <?> "compound expression"
term = parens expr <|> variable <?> "full expression"
operators = [ [Prefix (string "NOT" >> spaces >> return Not)]
, [binary "AND" And]
, [binary "OR" Or] ]
where binary n c = Infix (string n *> spaces *> pure c) AssocLeft
variable = Var <$> (letter <* spaces) <?> "variable"
parens p = SubExpr <$> (char '(' *> spaces *> p <* char ')' <* spaces) <?> "parens"
main = mapM_ printNotExpr . lines =<< readFile "inputs.txt"
where printNotExpr e = case parseExpr e of
Right x -> print $ not x
Left e -> error $ show e
@thisiswei
Copy link

@5outh awesome!

@thisiswei
Copy link

man haskell is cool!

@sandermak
Copy link

Shouldn't line 17 be:

not (SubExpr e) = SubExpr $ not e

otherwise invalid trees may arise, e.g. try

(a AND b) OR (c AND d)

as input.

@alogic0
Copy link

alogic0 commented Feb 16, 2016

To compile with GHC 7.10.2, I just added the next line at the beginning:
{-# LANGUAGE FlexibleContexts #-}

@quickdudley
Copy link

The problem pointed out by sandermak could be fixed either by his suggestion or by changing the Show instance to define showsPrec instead of show as done in my fork

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment