order of evaluation ?
Konst Sushenko
konsu@microsoft.com
Sun, 17 Feb 2002 20:50:22 -0800
This is a multi-part message in MIME format.
--------------InterScan_NT_MIME_Boundary
Content-Type: multipart/alternative;
boundary="----_=_NextPart_001_01C1B837.C5CE3A92"
------_=_NextPart_001_01C1B837.C5CE3A92
Content-Type: text/plain;
charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
hello,
=20
below is the code that i wrote as an excercise for myself (I am still
learning haskell).
=20
it implements a straighforward way to simplify boolean expressions, and
should be self-explanatory.
=20
my question is, if i have an expression such as ((Const False) :&:
<subexp>), will <subexp> be reduced first (according to the definition
'simplify (x :&: y) =3D simplify' ((simplify x) :&: (simplify y))') or
will laziness do the right thing, and emit (Const False) without looking
into <exp>?
=20
i think the latter, but would appreciate a word from an expert.
=20
thanks
konst
=20
PS: any coding suggestions, etc. are also welcome
=20
=20
=20
infixr 3 :&:
infixr 2 :|:
=20
data Exp =3D Const Bool
| Sym String
| Not Exp
| Exp :&: Exp
| Exp :|: Exp
=20
instance Eq Exp where
(Const x) =3D=3D (Const y) =3D x=3D=3Dy
(Sym x) =3D=3D (Sym y) =3D x=3D=3Dy
(Not x) =3D=3D (Not y) =3D x=3D=3Dy
(x :&: y) =3D=3D (u :&: v) =3D x=3D=3Du && y=3D=3Dv || x=3D=3Dv && =
y=3D=3Du
(x :|: y) =3D=3D (u :|: v) =3D x=3D=3Du && y=3D=3Dv || x=3D=3Dv && =
y=3D=3Du
_ =3D=3D _ =3D False
=20
simplify (x :&: y) =3D simplify' ((simplify x) :&: (simplify y))
simplify (x :|: y) =3D simplify' ((simplify x) :|: (simplify y))
simplify (Not x) =3D simplify' (Not (simplify x))
simplify x =3D x
=20
simplify' (Not (Const True)) =3D Const False
simplify' (Not (Const False)) =3D Const True
=20
simplify' (Not (Not x)) =3D x
=20
simplify' ((Not x) :&: y) | x=3D=3Dy =3D Const False
simplify' (x :&: (Not y)) | x=3D=3Dy =3D Const False
simplify' ((Not x) :|: y) | x=3D=3Dy =3D Const True
simplify' (x :|: (Not y)) | x=3D=3Dy =3D Const True
=20
simplify' ((Const False) :&: _) =3D Const False
simplify' (_ :&: (Const False)) =3D Const False
simplify' ((Const True) :&: x) =3D x
simplify' (x :&: (Const True)) =3D x
=20
simplify' ((Const True) :|: _) =3D Const True
simplify' (_ :|: (Const True)) =3D Const True
simplify' ((Const False) :|: x) =3D x
simplify' (x :|: (Const False)) =3D x
=20
simplify' (x :&: y) | x=3D=3Dy =3D x
simplify' (x :|: y) | x=3D=3Dy =3D x
=20
simplify' x =3D x
=20
------_=_NextPart_001_01C1B837.C5CE3A92
Content-Type: text/html;
charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META HTTP-EQUIV=3D"Content-Type" CONTENT=3D"text/html; =
charset=3Dus-ascii">
<TITLE>Message</TITLE>
<META content=3D"MSHTML 6.00.2713.1100" name=3DGENERATOR></HEAD>
<BODY>
<DIV><SPAN class=3D142474104-18022002><FONT face=3D"Courier New"=20
size=3D2>hello,</FONT></SPAN></DIV>
<DIV><SPAN class=3D142474104-18022002><FONT face=3D"Courier New"=20
size=3D2></FONT></SPAN> </DIV>
<DIV><SPAN class=3D142474104-18022002><FONT face=3D"Courier New" =
size=3D2>below is the=20
code that i wrote as an excercise for myself (I am still learning=20
haskell).</FONT></SPAN></DIV>
<DIV><SPAN class=3D142474104-18022002><FONT face=3D"Courier New"=20
size=3D2></FONT></SPAN> </DIV>
<DIV><SPAN class=3D142474104-18022002><FONT face=3D"Courier New" =
size=3D2>it=20
implements a straighforward way to simplify boolean expressions, and =
should be=20
self-explanatory.</FONT></SPAN></DIV>
<DIV><SPAN class=3D142474104-18022002><FONT face=3D"Courier New"=20
size=3D2></FONT></SPAN> </DIV>
<DIV><SPAN class=3D142474104-18022002><FONT face=3D"Courier New" =
size=3D2>my question=20
is, if i have an expression such as ((Const False) :&: =
<subexp>), will=20
<subexp> be reduced first (according to the definition=20
'</FONT></SPAN><SPAN class=3D142474104-18022002><FONT face=3D"Courier =
New"=20
size=3D2>simplify (x :&: y) =3D simplify' ((simplify x) :&: =
(simplify y))')=20
or will laziness do the right thing, and emit (Const False) without =
looking into=20
<exp>?</FONT></SPAN></DIV>
<DIV><SPAN class=3D142474104-18022002><FONT face=3D"Courier New"=20
size=3D2></FONT></SPAN> </DIV>
<DIV><SPAN class=3D142474104-18022002><FONT face=3D"Courier New" =
size=3D2>i think the=20
latter, but would appreciate a word from an expert.</FONT></SPAN></DIV>
<DIV><SPAN class=3D142474104-18022002><FONT face=3D"Courier New"=20
size=3D2></FONT></SPAN> </DIV>
<DIV><SPAN class=3D142474104-18022002><FONT face=3D"Courier New"=20
size=3D2>thanks</FONT></SPAN></DIV>
<DIV><SPAN class=3D142474104-18022002><FONT face=3D"Courier New"=20
size=3D2>konst</FONT></SPAN></DIV>
<DIV><SPAN class=3D142474104-18022002><FONT face=3D"Courier New"=20
size=3D2></FONT></SPAN> </DIV>
<DIV><SPAN class=3D142474104-18022002><FONT face=3D"Courier New" =
size=3D2>PS: any=20
coding suggestions, etc. are also welcome</FONT></DIV>
<DIV><FONT face=3D"Courier New" size=3D2></FONT><FONT face=3D"Courier =
New"=20
size=3D2></FONT><FONT face=3D"Courier New" size=3D2></FONT><FONT =
face=3D"Courier New"=20
size=3D2></FONT><FONT face=3D"Courier New" size=3D2></FONT><FONT =
face=3D"Courier New"=20
size=3D2></FONT><FONT face=3D"Courier New" size=3D2></FONT> </DIV>
<DIV><FONT face=3D"Courier New" size=3D2></FONT> </DIV>
<DIV><FONT face=3D"Courier New" size=3D2></FONT> </DIV>
<DIV><FONT face=3D"Courier New" size=3D2></FONT><FONT face=3D"Courier =
New"=20
size=3D2></FONT><FONT face=3D"Courier New" size=3D2></FONT><FONT =
face=3D"Courier New"=20
size=3D2></FONT><BR></DIV></SPAN><FONT face=3D"Courier New" =
size=3D2></FONT>
<DIV><FONT face=3D"Courier New" size=3D2></FONT><FONT face=3D"Courier =
New"=20
size=3D2></FONT><FONT face=3D"Courier New" size=3D2></FONT><FONT =
face=3D"Courier New"=20
size=3D2></FONT><FONT face=3D"Courier New" size=3D2></FONT><FONT =
face=3D"Courier New"=20
size=3D2></FONT><FONT face=3D"Courier New" size=3D2></FONT><FONT =
face=3D"Courier New"=20
size=3D2></FONT><FONT face=3D"Courier New" size=3D2></FONT><FONT =
face=3D"Courier New"=20
size=3D2></FONT><FONT face=3D"Courier New" size=3D2></FONT><BR><FONT=20
face=3D"Courier New" size=3D2>infixr 3 :&:<BR>infixr 2 =
:|:</FONT></DIV>
<DIV><FONT face=3D"Courier New" size=3D2></FONT> </DIV>
<DIV><FONT face=3D"Courier New" size=3D2>data Exp =3D Const=20
Bool<BR> | Sym=20
String<BR> | Not=20
Exp<BR> | Exp :&:=20
Exp<BR> | Exp :|:=20
Exp</FONT></DIV>
<DIV><FONT face=3D"Courier New" size=3D2></FONT> </DIV>
<DIV><FONT face=3D"Courier New" size=3D2>instance Eq Exp =
where<BR> =20
(Const x) =3D=3D (Const y) =3D x=3D=3Dy<BR> (Sym =
x) =3D=3D (Sym=20
y) =3D x=3D=3Dy<BR> (Not x) =
=3D=3D (Not=20
y) =3D x=3D=3Dy<BR> (x :&: y) =3D=3D =
(u :&: v) =3D=20
x=3D=3Du && y=3D=3Dv || x=3D=3Dv && =
y=3D=3Du<BR> (x :|: y) =3D=3D=20
(u :|: v) =3D x=3D=3Du && y=3D=3Dv || x=3D=3Dv && =
y=3D=3Du<BR> =20
_ =3D=3D=20
_ =3D False</FONT></DIV>
<DIV><FONT face=3D"Courier New" size=3D2></FONT> </DIV>
<DIV><FONT face=3D"Courier New" size=3D2>simplify (x :&: y) =3D =
simplify'=20
((simplify x) :&: (simplify y))<BR>simplify (x :|: y) =3D simplify' =
((simplify=20
x) :|: (simplify y))<BR>simplify (Not x) =3D simplify' (Not =
(simplify=20
x))<BR>simplify x =3D=20
x</FONT></DIV>
<DIV><FONT face=3D"Courier New" size=3D2></FONT> </DIV>
<DIV><FONT face=3D"Courier New" size=3D2>simplify' (Not (Const=20
True)) =3D Const False<BR>simplify' (Not (Const=20
False)) =3D Const True</FONT></DIV>
<DIV><FONT face=3D"Courier New" size=3D2></FONT> </DIV>
<DIV><FONT face=3D"Courier New" size=3D2>simplify' (Not (Not=20
x)) =3D =
x</FONT></DIV>
<DIV><FONT face=3D"Courier New" size=3D2></FONT> </DIV>
<DIV><FONT face=3D"Courier New" size=3D2>simplify' ((Not x) :&: y) | =
x=3D=3Dy =3D=20
Const False<BR>simplify' (x :&: (Not y)) | x=3D=3Dy =3D Const =
False<BR>simplify'=20
((Not x) :|: y) | x=3D=3Dy =3D Const True<BR>simplify' (x :|: (Not y)) | =
x=3D=3Dy =3D Const=20
True</FONT></DIV>
<DIV><FONT face=3D"Courier New" size=3D2></FONT> </DIV>
<DIV><FONT face=3D"Courier New" size=3D2>simplify' ((Const False) =
:&: _) =3D=20
Const False<BR>simplify' (_ :&: (Const False)) =3D Const=20
False<BR>simplify' ((Const True) :&: x) =3D =
x<BR>simplify' (x=20
:&: (Const True)) =3D x</FONT></DIV>
<DIV><FONT face=3D"Courier New" size=3D2></FONT> </DIV>
<DIV><FONT face=3D"Courier New" size=3D2>simplify' ((Const True) :|: =
_) =20
=3D Const True<BR>simplify' (_ :|: (Const True)) =3D Const=20
True<BR>simplify' ((Const False) :|: x) =3D x<BR>simplify' (x :|: =
(Const=20
False)) =3D x</FONT></DIV>
<DIV><FONT face=3D"Courier New" size=3D2></FONT> </DIV>
<DIV><FONT face=3D"Courier New" size=3D2>simplify' (x :&: y) |=20
x=3D=3Dy =3D x<BR>simplify' (x :|: =
y) |=20
x=3D=3Dy =3D x</FONT></DIV>
<DIV><FONT face=3D"Courier New" size=3D2></FONT> </DIV>
<DIV><FONT face=3D"Courier New" size=3D2>simplify'=20
x =
=20
=3D x</FONT></DIV>
<DIV><FONT face=3D"Courier New" =
size=3D2></FONT> </DIV></BODY></HTML>
------_=_NextPart_001_01C1B837.C5CE3A92--
--------------InterScan_NT_MIME_Boundary--