Skip to content

Instantly share code, notes, and snippets.

@chrislloyd
Created August 14, 2011 07:43
Show Gist options
  • Save chrislloyd/1144680 to your computer and use it in GitHub Desktop.
Save chrislloyd/1144680 to your computer and use it in GitHub Desktop.
eg1 = ['not', ['nor', ['var', 'a'], ['var', 'c']]]
eg2 = ['nor', ['nor', ['var', 'a'], ['var', 'b']], ['var', 'a']]
eg3 = ['not', ['nor', ['var', 'a'], ['var', 'b']]]
findVars = (q) ->
switch q[0]
when 'nor'
# Intersect these two vals
findVars(q[1]) + findVars(q[2])
when 'not' then findVars(q[1])
when 'var' then [q[1]]
console.log findVars(eg1)
console.log findVars(eg2)
transformer = (q) ->
eval = (env) ->
switch q[0]
when 'var' then env[q[1]]
when 'not' then not transformer(q[1])(env)
when 'nor' then not (transformer(q[1])(env) or transformer(q[2])(env))
return eval
console.log transformer(eg3)(a: false, b: false)
console.log transformer(eg3)(a: true, b: false)
simplify = (q) ->
# (not (not (var a))) == (var a)
if q[0] == 'not' and q[1][0] == 'not'
simplify(q[1][1])
else
switch q[0]
when 'not' then ['not', simplify(q[1])]
when 'nor' then ['nor', simplify(q[1]), simplify(q[2])]
when 'var' then q
console.log simplify(['not', ['not', ['var', 'a']]])
import Data.List (union)
import Data.Maybe (fromMaybe)
import Data.Data
import Data.Generics.Schemes (everywhere)
import Data.Generics.Aliases (mkT)
nor = not . or
type VarName = String
data Query = SVar VarName
| SNot Query
| SNor Query Query
deriving (Eq, Show, Typeable, Data)
type Env = [(VarName, Bool)]
findVars :: Query -> [VarName]
findVars (SVar a) = [a]
findVars (SNot a) = findVars a
findVars (SNor a b) = (findVars a) `union` (findVars b)
transformer :: Query -> Env -> Bool
transformer (SVar name) env =
fromMaybe (error ("no var named " ++name)) (lookup name env)
transformer (SNot a) env = not $ transformer a env
transformer (SNor a b) env =
nor [(transformer a env), (transformer b env)]
simplify :: Query -> Query
simplify = everywhere (mkT f)
where
f (SNot (SNot x)) = x
f x = x
@chrislloyd
Copy link
Author

chrislloyd commented Aug 17, 2011 via email

@mwotton
Copy link

mwotton commented Aug 17, 2011 via email

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