{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 8.5 Class and instance declarations"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"```\n",
"class Eq a where\n",
" (==), (/=) :: a -> a -> Bool\n",
" x /= y = not (x == y)\n",
"```"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"```\n",
"instance Eq Bool where\n",
" False == False = True\n",
" True == True = True\n",
" _ == _ = False\n",
"```"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Bool is an instance of the Eq class, with (==) defined as above.\n",
"\n",
"Only types that are defined using the data or newtype mechanisms can be made instances of classes.\n",
"\n",
"Classes can also be extended to form new classes. For example, the class Ord of types whose values are totally ordered is declared as an extension of Eq class."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"class Eq a => Ord a where\n",
" (<), (<=), (>), (>=) :: a -> a -> Bool\n",
" min, max :: a -> a -> a\n",
" min x y | x <= y = x\n",
" | otherwise = y\n",
" max x y | x <= y = y\n",
" | otherwise = x"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"instance Ord Bool where\n",
" False < True = True\n",
" _ < _ = False\n",
" \n",
" b <= c = (b < c) || (b == c)\n",
" b > c = c < b\n",
" b >= c = c <= b"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Derived instances"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"When new types are declared, it is usually appropriate to make them instances of a number of built-in classes using the \"deriving\" clause.\n",
"```\n",
"data Bool = False | True deriving (Eq, Ord, Show, Read)\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"Redundant ==
Redundant ==
"
],
"text/plain": [
"Line 1: Redundant ==\n",
"Found:\n",
"False == False\n",
"Why not:\n",
"not FalseLine 1: Redundant ==\n",
"Found:\n",
"False == False\n",
"Why not:\n",
"not False"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"True"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"False == False"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"False < True"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"\"False\""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"show False"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"False"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"read \"False\" :: Bool"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The use of :: Bool in the above example is necessary as the read function needs to know what type it needs to convert the string \"False\" into.\n",
"\n",
"For the purposes of deriving instances of the Ord type, the ordering of the constructors of a type is determined by the position in the declaration. So, False would be \"less-than\" True"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In the case of constructors that have arguments, the types of these arguments should also be instance of any derived classes."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"For example, in \n",
"```\n",
"data Shape = Circle Float | Rect Float Float\n",
"```\n",
"to derive Shape as an equality type requires Float also as deriving equality type.\n",
"\n",
"or in\n",
"```\n",
"data Maybe a = Nothing | Just a\n",
"```\n",
"to derive Maybe as an equality type, the type argument a should also derive equality."
]
},
{
"cell_type": "code",
"execution_count": 52,
"metadata": {},
"outputs": [],
"source": [
"data Shape = Circle Float | Rectangle Float Float deriving (Eq, Ord, Show)"
]
},
{
"cell_type": "code",
"execution_count": 53,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"False"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"Rectangle 1.0 4.0 == Rectangle 2.0 3.0"
]
},
{
"cell_type": "code",
"execution_count": 57,
"metadata": {},
"outputs": [
{
"ename": "",
"evalue": "",
"header": "MessageHeader {mhIdentifiers = [\"7ef65549-a030-4781-9f9f-03e45bef9854\"], mhParentHeader = Just (MessageHeader {mhIdentifiers = [\"7ef65549-a030-4781-9f9f-03e45bef9854\"], mhParentHeader = Nothing, mhMetadata = Metadata (fromList [(\"recordTiming\",Bool False),(\"deletedCells\",Array [String \"e40b1a39-02b9-4f98-a67b-7a6a143129c4\"]),(\"cellId\",String \"cebb1f30-c090-4e9e-9027-9bb00288f24e\")]), mhMessageId = UUID {uuidToString = \"a843b293-0bbf-4530-a1f5-bd800e3a4a95\"}, mhSessionId = UUID {uuidToString = \"7ef65549-a030-4781-9f9f-03e45bef9854\"}, mhUsername = \"\", mhMsgType = ExecuteRequestMessage, mhBuffers = []}), mhMetadata = Metadata (fromList []), mhMessageId = UUID {uuidToString = \"e36b291b-67a9-4375-ab2b-3f49db6b8cd1\"}, mhSessionId = UUID {uuidToString = \"7ef65549-a030-4781-9f9f-03e45bef9854\"}, mhUsername = \"\", mhMsgType = ExecuteErrorMessage, mhBuffers = []}",
"output_type": "error",
"traceback": [
":1:65-67: No instance nor default method for class operation >"
]
}
],
"source": [
"Rectangle 1.0 4.0 > Rectangle 2.0 3.0\n",
"-- Note this example works in interactive ghci on terminal; has some issues in jupyter lab"
]
},
{
"cell_type": "code",
"execution_count": 58,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"False"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"Circle 3.6 == Circle 5.5"
]
},
{
"cell_type": "code",
"execution_count": 59,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"\"Circle 4.4\""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"show (Circle 4.4)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 8.6 Tautology Checker"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Consider a language of propositions built up from basic values (False, True) and variables (A,B,...,Z) using \"not\", \"and\", \"implication\" and parentheses. For example the following are propositions:\n",
"```\n",
"A and not A\n",
"(A and B) -> A\n",
"A -> (A and B)\n",
"(A and (A -> B)) -> B\n",
"```\n",
"Recall from your Discrete Math class the meaning of such propositions (truth tables)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Step 1: Declare type for propositions"
]
},
{
"cell_type": "code",
"execution_count": 62,
"metadata": {},
"outputs": [],
"source": [
"data Prop = Const Bool\n",
" | Var Char\n",
" | Not Prop\n",
" | And Prop Prop\n",
" | Imply Prop Prop deriving Show"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Note that we do not need to define parentheses as we can use the inbuilt Haskell parentheses. Using this type, we can instantiate above propositions as follows:"
]
},
{
"cell_type": "code",
"execution_count": 63,
"metadata": {},
"outputs": [],
"source": [
"p1 :: Prop\n",
"p1 = And (Var 'A') (Not (Var 'A'))\n",
"\n",
"p2 :: Prop\n",
"p2 = Imply (And (Var 'A') (Var 'B')) (Var 'A')\n",
"\n",
"p3 :: Prop\n",
"p3 = Imply (Var 'A') (And (Var 'A') (Var 'B'))\n",
"\n",
"p4 :: Prop\n",
"p4 = Imply (And (Var 'A') (Imply (Var 'A') (Var 'B'))) (Var 'B')"
]
},
{
"cell_type": "code",
"execution_count": 64,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"\"Imply (And (Var 'A') (Imply (Var 'A') (Var 'B'))) (Var 'B')\""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"show p4"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Step 2: Define substitutions and eval"
]
},
{
"cell_type": "code",
"execution_count": 70,
"metadata": {},
"outputs": [],
"source": [
"type Assoc k v = [(k,v)]\n",
"find :: Eq k => k -> Assoc k v -> v\n",
"find k t = head [v | (k',v) <- t, k == k']\n",
"\n",
"type Subst = Assoc Char Bool"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"for example, the substitution [('A',False),('B',True)] assigns boolean values to variables. We can now define the following function, eval, which given a substitution and a proposition, evaluates the proposition based on the substitution to result in a boolean value."
]
},
{
"cell_type": "code",
"execution_count": 71,
"metadata": {},
"outputs": [],
"source": [
"eval :: Subst -> Prop -> Bool\n",
"eval _ (Const b) = b\n",
"eval s (Var x) = find x s\n",
"eval s (Not p) = not (eval s p)\n",
"eval s (And p q) = eval s p && eval s q\n",
"eval s (Imply p q) = eval s p <= eval s q"
]
},
{
"cell_type": "code",
"execution_count": 72,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"eval [('A',False),('B',True)] p2"
]
},
{
"cell_type": "code",
"execution_count": 73,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"False"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"eval [('A',True),('B',False)] p3"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Step 3: Generate substitutions"
]
},
{
"cell_type": "code",
"execution_count": 74,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"Use String
"
],
"text/plain": [
"Line 2: Use String\n",
"Found:\n",
"Prop -> [Char]\n",
"Why not:\n",
"Prop -> String"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"-- function to return all variables in a proposition\n",
"vars :: Prop -> [Char]\n",
"vars (Const _) = []\n",
"vars (Var x) = [x]\n",
"vars (Not p) = vars p\n",
"vars (And p q) = vars p ++ vars q\n",
"vars (Imply p q) = vars p ++ vars q"
]
},
{
"cell_type": "code",
"execution_count": 75,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"\"AA\""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"\"ABA\""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"\"ABA\""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"\"AABB\""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"vars p1\n",
"vars p2\n",
"vars p2\n",
"vars p4"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Note: We will get rid of duplicates later"
]
},
{
"cell_type": "code",
"execution_count": 82,
"metadata": {},
"outputs": [],
"source": [
"-- function to generate all combinations of False and True for n variables\n",
"-- method: think of each combination as an integer in binary notation with 0=False,1=True\n",
"type Bit = Int\n",
"int2bin :: Int -> [Bit]\n",
"int2bin 0 = []\n",
"int2bin n = n `mod` 2 : int2bin (n `div` 2)\n",
"\n",
"bools1 :: Int -> [[Bool]]\n",
"bools1 n = map (reverse . map conv . make n . int2bin) range\n",
" where \n",
" range = [0..(2^n)-1]\n",
" make n bs = take n (bs ++ repeat 0)\n",
" conv 0 = False\n",
" conv 1 = True"
]
},
{
"cell_type": "code",
"execution_count": 83,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[[False,False,False],[False,False,True],[False,True,False],[False,True,True],[True,False,False],[True,False,True],[True,True,False],[True,True,True]]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"bools1 3"
]
},
{
"cell_type": "code",
"execution_count": 85,
"metadata": {},
"outputs": [],
"source": [
"-- A simpler and recursive definition of bools\n",
"bools :: Int -> [[Bool]]\n",
"bools 0 = [[]]\n",
"bools n = map (False:) bss ++ map (True:) bss\n",
" where bss = bools (n-1)"
]
},
{
"cell_type": "code",
"execution_count": 86,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[[False,False,False],[False,False,True],[False,True,False],[False,True,True],[True,False,False],[True,False,True],[True,True,False],[True,True,True]]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"bools 3"
]
},
{
"cell_type": "code",
"execution_count": 88,
"metadata": {},
"outputs": [],
"source": [
"-- now we generate all possible substitions for variables\n",
"rmdups :: Eq a => [a] -> [a]\n",
"rmdups [] = []\n",
"rmdups (x:xs) = x : filter (/= x) (rmdups xs)\n",
"\n",
"substs :: Prop -> [Subst]\n",
"substs p = map (zip vs) (bools (length vs))\n",
" where vs = rmdups (vars p)"
]
},
{
"cell_type": "code",
"execution_count": 89,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[[('A',False)],[('A',True)]]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"substs p1"
]
},
{
"cell_type": "code",
"execution_count": 90,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[[('A',False),('B',False)],[('A',False),('B',True)],[('A',True),('B',False)],[('A',True),('B',True)]]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"substs p2"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Step 4: Test tautology"
]
},
{
"cell_type": "code",
"execution_count": 93,
"metadata": {},
"outputs": [],
"source": [
"isTaut :: Prop -> Bool\n",
"isTaut p = and [eval s p | s <- substs p]"
]
},
{
"cell_type": "code",
"execution_count": 94,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"False"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"True"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"False"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"True"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"isTaut p1\n",
"isTaut p2\n",
"isTaut p3\n",
"isTaut p4"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 8.7 Abstract Machine"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"data Expr = Val Int | Add Expr Expr\n",
"\n",
"value :: Expr -> Int\n",
"value (Val n) = n\n",
"value (Add x y) = value x + value y"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"9"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"e1 = Add (Add (Val 2) (Val 3)) (Val 4)\n",
"value e1"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"```\n",
" value (Add (Add (Val 2) (Val 3)) (Val 4))\n",
"= value (Add (Val 2) (Val 3)) + value (Val 4)\n",
"= value (Val 2) + value (Val 3) + value (Val 4)\n",
"= (2 + value (Val 3)) + value (Val 4)\n",
"= (2 + 3) + value (Val 4)\n",
"= 5 + value (Val 4)\n",
"= 5 + 4\n",
"= 9\n",
"```"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Note that the definition of ```value``` does not specify the order of operations; So, Haskell selects its own order; in this case left to right.\n",
"\n",
"We introduce a method that uses a ```control stack``` containing operations that introduce a particular order of operation."
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [],
"source": [
"type Cont = [Op]\n",
"data Op = EVAL Expr | ADD Int"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [],
"source": [
"eval :: Expr -> Cont -> Int\n",
"eval (Val n) c = exec c n\n",
"eval (Add x y) c = eval x (EVAL y : c)\n",
"\n",
"exec :: Cont -> Int -> Int\n",
"exec [] n = n\n",
"exec (EVAL y : c) n = eval y (ADD n : c)\n",
"exec (ADD n : c) m = exec c (n + m)\n",
"\n",
"value1 :: Expr -> Int\n",
"value1 e = eval e []"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"9"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"value1 e1"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"```\n",
" value1 (Add (Add (Val 2) (Val 3)) (Val 4))\n",
"= eval (Add (Add (Val 2) (Val 3)) (Val 4)) []\n",
"= eval (Add (Val 2) (Val 3)) [EVAL (Val 4)]\n",
"= eval (Val 2) [EVAL (Val 3), EVAL (Val 4)]\n",
"= exec [EVAL (Val 3), EVAL (Val 4)] 2\n",
"= eval (Val 3) [ADD 2, EVAL (Val 4)]\n",
"= exec [ADD 2, EVAL (Val 4)] 3\n",
"= exec [EVAL (Val 4)] 5\n",
"= eval (Val 4) [ADD 5]\n",
"= exec [ADD 5] 4\n",
"= exec [] 9\n",
"= 9\n",
"```"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Haskell",
"language": "haskell",
"name": "haskell"
},
"language_info": {
"codemirror_mode": "ihaskell",
"file_extension": ".hs",
"name": "haskell",
"pygments_lexer": "Haskell",
"version": "8.6.5"
}
},
"nbformat": 4,
"nbformat_minor": 4
}