Difference between revisions of "FP Laboratory 9"

From Marek Běhálek Wiki
Jump to navigation Jump to search
 
(15 intermediate revisions by 2 users not shown)
Line 1: Line 1:
== User defined data types and type classes ==  
+
<translate>
 +
== User defined data types and type classes == <!--T:1-->
 +
</translate>
  
 
<div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/lo0pdwWoSx4]]</div>  
 
<div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/lo0pdwWoSx4]]</div>  
 +
 +
<translate>
 +
<!--T:2-->
 
Consider following representation of expressions
 
Consider following representation of expressions
 +
</translate>
  
 
<syntaxhighlight lang="Haskell">
 
<syntaxhighlight lang="Haskell">
Line 14: Line 20:
 
</syntaxhighlight>
 
</syntaxhighlight>
  
* Create function eval that evaluates expresions. <div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/AvThE0I4Iz8]]</div>  
+
<translate>
 +
<!--T:3-->
 +
* Create function eval that evaluates expresions.  
 +
</translate>
 +
 
 +
<div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/AvThE0I4Iz8]]</div>  
 
<syntaxhighlight lang="Haskell">
 
<syntaxhighlight lang="Haskell">
 
eval :: Expr -> Int
 
eval :: Expr -> Int
Line 38: Line 49:
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>
  
* Create function showExpr that shows expression as a String. <div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/cPL1zEZHLh0]]</div>  
+
<translate>
 +
<!--T:4-->
 +
* Create function showExpr that shows expression as a String.  
 +
</translate>
 +
 
 +
<div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/cPL1zEZHLh0]]</div>  
 
<syntaxhighlight lang="Haskell">
 
<syntaxhighlight lang="Haskell">
 
showExpr :: Expr -> String
 
showExpr :: Expr -> String
 
</syntaxhighlight>
 
</syntaxhighlight>
 
+
<syntaxhighlight lang="Haskell" class="myDark">
 +
*Main> showExpr (Add (Num 1) (Num 2))
 +
"1+2"
 +
*Main> showExpr (Mul (Add (Num 1) (Num 2)) (Num 3))
 +
"(1+2)*3"
 +
*Main> showExpr (Mul (Add (Num 1) (Mul (Num 2) (Var 'x'))) (Mul (Num 3) (Var 'x')))
 +
"(1+2*x)*3*x"
 +
*Main> showExpr (Mul (Num 2) (Mul (Var 'x') (Var 'x')))                           
 +
"2*x*x"
 +
</syntaxhighlight>
 
<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
 
<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
 
<syntaxhighlight lang="Haskell">
 
<syntaxhighlight lang="Haskell">
Line 69: Line 94:
 
     else x
 
     else x
 
showExpr' (Div l r) op = let
 
showExpr' (Div l r) op = let
   x = showExpr' l Hi ++"/"++showExpr' r Hi
+
   x = showExpr' l Hi ++"/"++showExpr' r HiDiv
 
   in if op == HiDiv
 
   in if op == HiDiv
 
     then "(" ++ x ++")"
 
     then "(" ++ x ++")"
Line 78: Line 103:
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>
  
* Extend class Show to be usable with our expressions. <div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/NCAxJx_wJxI]]</div>  
+
<translate>
 +
<!--T:5-->
 +
* Extend class Show to be usable with our expressions.
 +
</translate>
 +
 
 +
<div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/NCAxJx_wJxI]]</div>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*Main> Add (Num 1) (Num 2)
 +
"1+2"
 +
*Main> Mul (Add (Num 1) (Num 2)) (Num 3)
 +
"(1+2)*3"
 +
*Main> Mul (Add (Num 1) (Mul (Num 2) (Var 'x'))) (Mul (Num 3) (Var 'x'))
 +
"(1+2*x)*3*x"
 +
*Main> Mul (Num 2) (Mul (Var 'x') (Var 'x'))         
 +
"2*x*x"
 +
</syntaxhighlight>
  
 
<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
 
<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
Line 89: Line 129:
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>
  
* Create function derivation representing symbolic derivation of a given expression.  
+
<translate>
 +
<!--T:6-->
 +
* Create function derivation representing symbolic derivation of a given expression.
 +
</translate>
 +
 
<syntaxhighlight lang="Haskell">
 
<syntaxhighlight lang="Haskell">
deriv :: Expr-> Char -> Expr
+
deriv :: Expr -> Char -> Expr
 +
</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*Main> deriv (Add (Num 1) (Num 2)) 'x'
 +
0+0
 +
*Main> deriv (Mul (Num 2) (Mul (Var 'x') (Var 'x'))) 'x'
 +
0*x*x+2*(1*x+x*1)
 +
*Main> deriv (Mul (Num 2) (Mul (Var 'x') (Var 'x'))) 'x'
 +
0*x*x+2*(1*x+x*1)
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Line 111: Line 163:
 
</div>
 
</div>
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>
 +
 +
<translate>
 +
== Additional exercises ==
 +
* Define a function that counts the number of operators in an expression.
 +
</translate>
 +
 +
<syntaxhighlight lang="Haskell">
 +
size :: Expr -> Int
 +
</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*Main> size (Add (Num 1) (Num 2))
 +
1
 +
*Main> size (Mul (Add (Num 1) (Mul (Num 2) (Var 'x'))) (Mul (Num 3) (Var 'x')))
 +
4
 +
</syntaxhighlight>
 +
 +
<translate>
 +
* It is possible to extend the type Expr so that it contains conditional expressions. Consider the following representation of boolean expressions:
 +
</translate>
 +
<syntaxhighlight lang="Haskell">
 +
data BExpr = Val Bool
 +
        | And BExpr BExpr
 +
        | Not BExpr
 +
        | Equal Expr Expr
 +
        | Greater Expr Expr
 +
    deriving (Eq)
 +
</syntaxhighlight>
 +
 +
<translate>
 +
* Define a function that evaluates boolean expressions.
 +
</translate>
 +
<syntaxhighlight lang="Haskell">
 +
bEval :: BExpr -> Bool
 +
</syntaxhighlight>
 +
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*Main> bEval (And (Equal (Num 4) (Num 5)) (Greater (Num 5) (Num 1)))
 +
False
 +
*Main> bEval (And (Equal (Add (Num 1) (Num 4)) (Num 5)) (Greater (Num 5) (Num 1)))
 +
True
 +
</syntaxhighlight>
 +
 +
<translate>
 +
* Define a function that shows a boolean expression as a string. Use symbols "/\","!","=",">" for logical conjunction, negation, equality, and comparison respectively.
 +
</translate>
 +
<syntaxhighlight lang="Haskell">
 +
showBExpr :: BExpr -> String
 +
</syntaxhighlight>
 +
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*Main> showBExpr((And (Val True) (Not (Greater (Num 5) (Num 1)))))
 +
"(True/\\!(5>1))"
 +
*Main> showBExpr(And (Equal (Add (Num 1) (Num 4)) (Num 5)) (Greater (Num 5) (Num 1)))
 +
"(((1+4)=5)/\\(5>1))"
 +
</syntaxhighlight>
 +
 +
<translate>
 +
* Extend class Show to be usable with our boolean expressions.
 +
</translate>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*Main> (And (Val True) (Not (Greater (Num 5) (Num 1))))
 +
(True/\!(5>1))
 +
*Main> And (Equal (Add (Num 1) (Num 4)) (Num 5)) (Greater (Num 5) (Num 1))
 +
(((1+4)=5)/\(5>1))
 +
</syntaxhighlight>
 +
 +
<translate>
 +
* Extend the Expr type with the If-Then-Else statement as follows:
 +
</translate>
 +
<syntaxhighlight lang="Haskell">
 +
data Expr = Num Int
 +
          | Add Expr Expr
 +
          | Sub Expr Expr
 +
          | Mul Expr Expr
 +
          | Div Expr Expr
 +
          | If BExpr Expr Expr
 +
deriving (Eq)
 +
</syntaxhighlight>
 +
 +
<translate>
 +
* Modify function eval to evaluate If-Then-Else statements.
 +
</translate>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*Main> eval (If (Greater (Num 5)(Num 1)) (Num 5) (Num 6))   
 +
5
 +
*Main> eval (Mul (If (Greater (Add (Num 0) (Num 1))(Num 1)) (Num 5) (Num 6)) (Num 7))
 +
42
 +
</syntaxhighlight>
 +
 +
<translate>
 +
* Modify function showExpr to show If-Then-Else statements as a string.
 +
</translate>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*Main> showExpr (If (Greater (Num 5)(Num 1)) (Num 5) (Num 6))
 +
"(If (5>1) then 5 else 6)"
 +
*Main> showExpr (Mul (If (Greater (Add (Num 0) (Num 1))(Num 1)) (Num 5) (Num 6)) (Num 7))
 +
"((If ((0+1)>1) then 5 else 6)*7)"
 +
</syntaxhighlight>

Latest revision as of 08:12, 21 August 2023

User defined data types and type classes

Video logo.png

Consider following representation of expressions

data Expr = Num Int
          | Add Expr Expr
          | Sub Expr Expr
          | Mul Expr Expr
          | Div Expr Expr
          | Var Char
	  deriving (Eq)
  • Create function eval that evaluates expresions.
Video logo.png
eval :: Expr -> Int
*Main> eval (Add (Num 1) (Num 2))
3
*Main> eval (Mul (Add (Num 1) (Num 2)) (Num 3))
9
eval :: Expr -> Int
eval (Num x) = x
eval (Add l r) =  (eval l) + (eval r)
eval (Sub l r) =  (eval l) - (eval r)
eval (Mul l r) =  (eval l) * (eval r)
eval (Div l r) =  (eval l) `div` (eval r)
Try it!
  • Create function showExpr that shows expression as a String.
Video logo.png
showExpr :: Expr -> String
*Main> showExpr (Add (Num 1) (Num 2))
"1+2"
*Main> showExpr (Mul (Add (Num 1) (Num 2)) (Num 3))
"(1+2)*3"
*Main> showExpr (Mul (Add (Num 1) (Mul (Num 2) (Var 'x'))) (Mul (Num 3) (Var 'x')))
"(1+2*x)*3*x"
*Main> showExpr (Mul (Num 2) (Mul (Var 'x') (Var 'x')))                            
"2*x*x"
showExpr :: Expr -> String
showExpr expr = showExpr' expr NoOp

data Operation = Hi | HiDiv | Lo | LoSub | NoOp deriving (Eq)

showExpr' :: Expr -> Operation -> String
showExpr' (Num x) _ = show x
showExpr' (Var x) _ =  [x]
showExpr' (Add l r) op = let
  x = showExpr' l Lo ++"+"++showExpr' r Lo
  in if op == Hi || op == HiDiv || op==LoSub 
     then "(" ++ x ++")"
     else x
showExpr' (Sub l r) op = let
  x = showExpr' l Lo ++"-"++showExpr' r LoSub
  in if op == Hi || op == HiDiv || op==LoSub 
     then "(" ++ x ++")"
     else x     
showExpr' (Mul l r) op = let
  x = showExpr' l Hi ++"*"++showExpr' r Hi
  in if op == HiDiv
     then "(" ++ x ++")"
     else x
showExpr' (Div l r) op = let
  x = showExpr' l Hi ++"/"++showExpr' r HiDiv
  in if op == HiDiv
     then "(" ++ x ++")"
     else x
Try it!
  • Extend class Show to be usable with our expressions.
Video logo.png
*Main> Add (Num 1) (Num 2)
"1+2"
*Main> Mul (Add (Num 1) (Num 2)) (Num 3)
"(1+2)*3"
*Main> Mul (Add (Num 1) (Mul (Num 2) (Var 'x'))) (Mul (Num 3) (Var 'x'))
"(1+2*x)*3*x"
*Main> Mul (Num 2) (Mul (Var 'x') (Var 'x'))           
"2*x*x"
instance (Show Expr) where
  show = showExpr
Try it!
  • Create function derivation representing symbolic derivation of a given expression.
deriv :: Expr -> Char -> Expr
*Main> deriv (Add (Num 1) (Num 2)) 'x'
0+0
*Main> deriv (Mul (Num 2) (Mul (Var 'x') (Var 'x'))) 'x'
0*x*x+2*(1*x+x*1)
*Main> deriv (Mul (Num 2) (Mul (Var 'x') (Var 'x'))) 'x'
0*x*x+2*(1*x+x*1)
deriv :: Expr-> Char -> Expr
deriv (Num _) _ = (Num 0)     
deriv (Var x) y | x==y = (Num 1)
                | otherwise = (Num 0)
deriv (Add l r) x = Add (deriv l x) (deriv r x)                
deriv (Sub l r) x = Sub (deriv l x) (deriv r x)
deriv (Mul l r) x = Add (Mul (deriv l x) r) (Mul l (deriv r x))
deriv (Div l r) x = 
   Div
    (Sub (Mul (deriv l x) r) (Mul l (deriv r x)))
    (Mul r r)
Try it!

Additional exercises

  • Define a function that counts the number of operators in an expression.
size :: Expr -> Int
*Main> size (Add (Num 1) (Num 2))
1
*Main> size (Mul (Add (Num 1) (Mul (Num 2) (Var 'x'))) (Mul (Num 3) (Var 'x')))
4
  • It is possible to extend the type Expr so that it contains conditional expressions. Consider the following representation of boolean expressions:
data BExpr = Val Bool
        | And BExpr BExpr
        | Not BExpr 
        | Equal Expr Expr
        | Greater Expr Expr
    deriving (Eq)
  • Define a function that evaluates boolean expressions.
bEval :: BExpr -> Bool
*Main> bEval (And (Equal (Num 4) (Num 5)) (Greater (Num 5) (Num 1))) 
False
*Main> bEval (And (Equal (Add (Num 1) (Num 4)) (Num 5)) (Greater (Num 5) (Num 1)))
True
  • Define a function that shows a boolean expression as a string. Use symbols "/\","!","=",">" for logical conjunction, negation, equality, and comparison respectively.
showBExpr :: BExpr -> String
*Main> showBExpr((And (Val True) (Not (Greater (Num 5) (Num 1)))))
"(True/\\!(5>1))"
*Main> showBExpr(And (Equal (Add (Num 1) (Num 4)) (Num 5)) (Greater (Num 5) (Num 1)))
"(((1+4)=5)/\\(5>1))"
  • Extend class Show to be usable with our boolean expressions.
*Main> (And (Val True) (Not (Greater (Num 5) (Num 1))))
(True/\!(5>1))
*Main> And (Equal (Add (Num 1) (Num 4)) (Num 5)) (Greater (Num 5) (Num 1))
(((1+4)=5)/\(5>1))
  • Extend the Expr type with the If-Then-Else statement as follows:
data Expr = Num Int
          | Add Expr Expr
          | Sub Expr Expr
          | Mul Expr Expr
          | Div Expr Expr
          | If BExpr Expr Expr
 deriving (Eq)
  • Modify function eval to evaluate If-Then-Else statements.
*Main> eval (If (Greater (Num 5)(Num 1)) (Num 5) (Num 6))     
5
*Main> eval (Mul (If (Greater (Add (Num 0) (Num 1))(Num 1)) (Num 5) (Num 6)) (Num 7))
42
  • Modify function showExpr to show If-Then-Else statements as a string.
*Main> showExpr (If (Greater (Num 5)(Num 1)) (Num 5) (Num 6)) 
"(If (5>1) then 5 else 6)"
*Main> showExpr (Mul (If (Greater (Add (Num 0) (Num 1))(Num 1)) (Num 5) (Num 6)) (Num 7))
"((If ((0+1)>1) then 5 else 6)*7)"