data Prop = Var String
		  | Not Prop
    	  | And [Prop]
    	  | Or [Prop]
		  | Nil
		  deriving (Show, Eq)
 
cutAnd :: Prop -> [Prop]
cutAnd (And ps) = ps
cutAnd  p       = [p]
 
cutOr  :: Prop -> [Prop]
cutOr  (Or  ps) = ps
cutOr   p       = [p]
 
smartOne :: (Prop -> Prop) -> Prop -> Prop
smartOne cons Nil = Nil
smartOne cons p   = cons p
 
smartMany :: ([Prop] -> Prop) -> [Prop] -> Prop
smartMany cons xs = case filter (/= Nil) xs of
	[]  -> Nil
	[x] -> x
	xs' -> cons xs'
 
flatten :: Prop -> Prop
flatten (Not p)  = smartOne  Not $ flatten p
flatten (And ps) = smartMany And $ ps >>= cutAnd . flatten
flatten (Or  ps) = smartMany Or  $ ps >>= cutOr  . flatten
flatten  p       = p
 
vx = Var "x"; vy = Var "y"; vz = Var "z"  
 
main = mapM_ (print . flatten)
    [ And [Or [Nil], Nil, And [Nil]]
        -- Nil
 
    , And [Or [vx, vy], Or [vx, Or [vz, Nil]]]
        -- And [Or [Var "x",Var "y"],Or [Var "x",Var "z"]]
 
    , Or  [Or [vx, vy], Or [vx, Or [vz, Nil]]]
        -- Or [Var "x",Var "y",Var "x",Var "z"]
 
    , Not (And [And [Or [Or [Nil], Or [Not vx]], Nil, And [vy]]])
        -- Not (And [Not (Var "x"),Var "y"])
 
	, And []
		-- Nil        
 
    , Or [And [vx]]
    	-- Var "x"
 
    , And [vx, Or []]
		-- Var "x'
 
	, And [Or [And [vx, Or [], vy, Nil]], And [vz, Or [vx]]]
		-- And [Var "x",Var "y",Var "z",Var "x"]
    ]

ZGF0YSBQcm9wID0gVmFyIFN0cmluZwoJCSAgfCBOb3QgUHJvcAogICAgCSAgfCBBbmQgW1Byb3BdCiAgICAJICB8IE9yIFtQcm9wXQoJCSAgfCBOaWwKCQkgIGRlcml2aW5nIChTaG93LCBFcSkKCmN1dEFuZCA6OiBQcm9wIC0+IFtQcm9wXQpjdXRBbmQgKEFuZCBwcykgPSBwcwpjdXRBbmQgIHAgICAgICAgPSBbcF0KCmN1dE9yICA6OiBQcm9wIC0+IFtQcm9wXQpjdXRPciAgKE9yICBwcykgPSBwcwpjdXRPciAgIHAgICAgICAgPSBbcF0KCnNtYXJ0T25lIDo6IChQcm9wIC0+IFByb3ApIC0+IFByb3AgLT4gUHJvcApzbWFydE9uZSBjb25zIE5pbCA9IE5pbApzbWFydE9uZSBjb25zIHAgICA9IGNvbnMgcAoKc21hcnRNYW55IDo6IChbUHJvcF0gLT4gUHJvcCkgLT4gW1Byb3BdIC0+IFByb3AKc21hcnRNYW55IGNvbnMgeHMgPSBjYXNlIGZpbHRlciAoLz0gTmlsKSB4cyBvZgoJW10gIC0+IE5pbAoJW3hdIC0+IHgKCXhzJyAtPiBjb25zIHhzJwoKZmxhdHRlbiA6OiBQcm9wIC0+IFByb3AKZmxhdHRlbiAoTm90IHApICA9IHNtYXJ0T25lICBOb3QgJCBmbGF0dGVuIHAKZmxhdHRlbiAoQW5kIHBzKSA9IHNtYXJ0TWFueSBBbmQgJCBwcyA+Pj0gY3V0QW5kIC4gZmxhdHRlbgpmbGF0dGVuIChPciAgcHMpID0gc21hcnRNYW55IE9yICAkIHBzID4+PSBjdXRPciAgLiBmbGF0dGVuCmZsYXR0ZW4gIHAgICAgICAgPSBwCgp2eCA9IFZhciAieCI7IHZ5ID0gVmFyICJ5IjsgdnogPSBWYXIgInoiICAKCm1haW4gPSBtYXBNXyAocHJpbnQgLiBmbGF0dGVuKQogICAgWyBBbmQgW09yIFtOaWxdLCBOaWwsIEFuZCBbTmlsXV0KICAgICAgICAtLSBOaWwKCiAgICAsIEFuZCBbT3IgW3Z4LCB2eV0sIE9yIFt2eCwgT3IgW3Z6LCBOaWxdXV0KICAgICAgICAtLSBBbmQgW09yIFtWYXIgIngiLFZhciAieSJdLE9yIFtWYXIgIngiLFZhciAieiJdXQoKICAgICwgT3IgIFtPciBbdngsIHZ5XSwgT3IgW3Z4LCBPciBbdnosIE5pbF1dXQogICAgICAgIC0tIE9yIFtWYXIgIngiLFZhciAieSIsVmFyICJ4IixWYXIgInoiXQoKICAgICwgTm90IChBbmQgW0FuZCBbT3IgW09yIFtOaWxdLCBPciBbTm90IHZ4XV0sIE5pbCwgQW5kIFt2eV1dXSkKICAgICAgICAtLSBOb3QgKEFuZCBbTm90IChWYXIgIngiKSxWYXIgInkiXSkKICAgICAgICAKCSwgQW5kIFtdCgkJLS0gTmlsICAgICAgICAKICAgICAgICAKICAgICwgT3IgW0FuZCBbdnhdXQogICAgCS0tIFZhciAieCIKICAgIAkKICAgICwgQW5kIFt2eCwgT3IgW11dCgkJLS0gVmFyICJ4JwoJCgksIEFuZCBbT3IgW0FuZCBbdngsIE9yIFtdLCB2eSwgTmlsXV0sIEFuZCBbdnosIE9yIFt2eF1dXQoJCS0tIEFuZCBbVmFyICJ4IixWYXIgInkiLFZhciAieiIsVmFyICJ4Il0KICAgIF0=