Difference between revisions of "FP Laboratory 6"

From Marek Běhálek Wiki
Jump to navigation Jump to search
(Marked this version for translation)
 
(6 intermediate revisions by 2 users not shown)
Line 1: Line 1:
== Operators ==  
+
<translate>
 +
== Operators == <!--T:1-->
 
*Define following functions that performs corresponding logic operations: <code>not', and', or', nand', xor', impl', equ'</code>
 
*Define following functions that performs corresponding logic operations: <code>not', and', or', nand', xor', impl', equ'</code>
 
*Define the 'standard' priority for all these functions, if they are used as operators.  
 
*Define the 'standard' priority for all these functions, if they are used as operators.  
 
*Create a function that prints the truth table of a given logical expression for two variables.
 
*Create a function that prints the truth table of a given logical expression for two variables.
 +
</translate>
 +
 
<syntaxhighlight lang="Haskell">table :: (Bool -> Bool -> Bool) -> IO ()</syntaxhighlight>
 
<syntaxhighlight lang="Haskell">table :: (Bool -> Bool -> Bool) -> IO ()</syntaxhighlight>
 
<syntaxhighlight lang="Haskell" class="myDark">
 
<syntaxhighlight lang="Haskell" class="myDark">
 
table (\a b -> (and' a (or' a b)))                                                                               
 
table (\a b -> (and' a (or' a b)))                                                                               
True True True
+
True True True
True False True
+
True False True
False True False
+
False True False
 
False False False
 
False False False
 
</syntaxhighlight>
 
</syntaxhighlight>
Line 46: Line 49:
 
equ' x y = x == y
 
equ' x y = x == y
 
infixl 7 `equ'`  
 
infixl 7 `equ'`  
 +
 +
table :: (Bool -> Bool -> Bool) -> IO ()
 +
table expr = putStr (concat [nicePrint [x,y,(expr x y)] |x<-[True,False], y<-[True,False]])
 +
 +
nicePrint :: [Bool] -> String
 +
nicePrint xs = concat [show x++"\t"| x<-xs] ++ "\n"
 
</syntaxhighlight>
 
</syntaxhighlight>
 +
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/GWCM50489]]
 
</div>
 
</div>
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>
  
 +
<translate>
 +
<!--T:2-->
 
*Extend the previously defined function to accept any number of variables (the number of variables will be given as a first parameter).
 
*Extend the previously defined function to accept any number of variables (the number of variables will be given as a first parameter).
 +
</translate>
 +
 
<syntaxhighlight lang="Haskell">tablen :: Int -> ([Bool] -> Bool) -> IO ()</syntaxhighlight>
 
<syntaxhighlight lang="Haskell">tablen :: Int -> ([Bool] -> Bool) -> IO ()</syntaxhighlight>
 
<syntaxhighlight lang="Haskell" class="myDark">
 
<syntaxhighlight lang="Haskell" class="myDark">
Line 74: Line 88:
 
   nicePrint xs = concat [show x++"\t"| x<-xs]
 
   nicePrint xs = concat [show x++"\t"| x<-xs]
 
</syntaxhighlight>
 
</syntaxhighlight>
 +
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/IDZIG48578]]
 
</div>
 
</div>
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>
  
 +
<translate>
 +
== Complex function - Huffman Codes == <!--T:3-->
 +
*Create a function that will compute [https://en.wikipedia.org/wiki/Huffman_coding Huffman codes] for a given list of characters and their frequencies.
 +
</translate>
  
== Complex function - Huffman Codes ==
+
<div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/HWYQZtbxMhc]]</div>  
 
 
*Create a function that will compute [https://en.wikipedia.org/wiki/Huffman_coding Huffman codes] for a given list of characters and their frequencies. <div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/HWYQZtbxMhc]]</div>  
 
 
<syntaxhighlight lang="Haskell">huffman :: [(Char, Int)] -> [(Char, String)]</syntaxhighlight>
 
<syntaxhighlight lang="Haskell">huffman :: [(Char, Int)] -> [(Char, String)]</syntaxhighlight>
 
<syntaxhighlight lang="Haskell" class="myDark">
 
<syntaxhighlight lang="Haskell" class="myDark">
Line 101: Line 118:
 
                 in step ((a1+b1, [(x,'0':a2)|(x,a2)<-as2]++[(x,'1':b2)|(x,b2)<-bs2])  : rest)
 
                 in step ((a1+b1, [(x,'0':a2)|(x,a2)<-as2]++[(x,'1':b2)|(x,b2)<-bs2])  : rest)
 
</syntaxhighlight>
 
</syntaxhighlight>
 +
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/PSSTZ19890]]
 
</div>
 
</div>
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>
 +
 +
<translate>
 +
== Additional exercises == <!--T:4-->
 +
* Create a function that divides a list of elements into the list lists using a separator.
 +
</translate>
 +
 +
<syntaxhighlight lang="Haskell">splitByElement :: Eq a => [a] -> a -> [[a]]</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*Main> splitByElement "I love functional programming!" ' '
 +
["I","love","functional","programming!"]
 +
*Main> splitByElement [1,2,1,2,3,4,5,5,6,4,1,2,0,1,4] 1
 +
[[2],[2,3,4,5,5,6,4],[2,0],[4]]
 +
*Main> splitByElement [1,2,1,2,3,4,5,5,6,4,1,2,0,1,4] 5
 +
[[1,2,1,2,3,4],[6,4,1,2,0,1,4]]
 +
</syntaxhighlight>

Latest revision as of 08:02, 26 October 2023

Operators

  • Define following functions that performs corresponding logic operations: not', and', or', nand', xor', impl', equ'
  • Define the 'standard' priority for all these functions, if they are used as operators.
  • Create a function that prints the truth table of a given logical expression for two variables.
table :: (Bool -> Bool -> Bool) -> IO ()
table (\a b -> (and' a (or' a b)))                                                                              
True  True  True
True  False True
False True  False
False False False
not' :: Bool -> Bool
not' True = False
not' False = True
infixl 5 `not'` 

and' :: Bool -> Bool -> Bool
and' True True = True
and' _ _ = False
infixl 4 `and'` 

or' :: Bool -> Bool -> Bool
or' False False = False
or' _ _ = True
infixl 3 `or'` 

nand' :: Bool -> Bool -> Bool
nand' x y = not' (and' x y)
infixl 4 `nand'` 

xor' :: Bool -> Bool -> Bool
xor' x y = x/=y
infixl 3 `xor'` 

impl' :: Bool -> Bool -> Bool
impl' True False = False
impl' _ _ = True
infixl 2 `impl'` 

equ' :: Bool -> Bool -> Bool
equ' x y = x == y
infixl 7 `equ'` 

table :: (Bool -> Bool -> Bool) -> IO ()
table expr = putStr (concat [nicePrint [x,y,(expr x y)] |x<-[True,False], y<-[True,False]])

nicePrint :: [Bool] -> String
nicePrint xs = concat [show x++"\t"| x<-xs] ++ "\n"
Try it!
  • Extend the previously defined function to accept any number of variables (the number of variables will be given as a first parameter).
tablen :: Int -> ([Bool] -> Bool) -> IO ()
 tablen 3 (\[a,b,c] -> a `and'` (b `or'` c) `equ'` a `and'` b `or'` a `and'` c)
True   True   True   => True
True   True   False  => True
True   False  True   => True
True   False  False  => False
False  True   True   => False
False  True   False  => False
False  False  True   => False
False  False  False  => False
tablen :: Int -> ([Bool] -> Bool) -> IO ()
tablen n f = putStr(concat [nicePrint x ++ " => " ++ show(f x) ++ "\n" |x<-allValues n]) where 
  allValues 1 = [[True], [False]]
  allValues n = [x:y| x<-[True,False], y<-allValues (n-1)]

  nicePrint :: [Bool] -> String
  nicePrint xs = concat [show x++"\t"| x<-xs]
Try it!

Complex function - Huffman Codes

  • Create a function that will compute Huffman codes for a given list of characters and their frequencies.
Video logo.png
huffman :: [(Char, Int)] -> [(Char, String)]
*Main>  huffman [('a',45),('b',13),('c',12),('d',16),('e',9),('f',5)]
[('a',"0"),('b',"101"),('c',"100"),('d',"111"),('e',"1101"),('f',"1100")]
import Data.List (sortBy)

huffman :: [(Char, Int)] -> [(Char, String)] 
huffman input = 
  let 
    prep = [ (y, [(x,"")] ) | (x,y)<-input]            
  in sortBy (\ (x,_) (y,_) -> compare x y) (step prep) where
     step :: [(Int, [(Char, String)])] -> [(Char, String)]
     step [(_, result) ] = result
     step list = let ((a1, as2):(b1,bs2):rest) = sortBy (\ (x,_) (y,_) -> compare x y) list
                 in step ((a1+b1, [(x,'0':a2)|(x,a2)<-as2]++[(x,'1':b2)|(x,b2)<-bs2])  : rest)
Try it!

Additional exercises

  • Create a function that divides a list of elements into the list lists using a separator.
splitByElement :: Eq a => [a] -> a -> [[a]]
*Main> splitByElement "I love functional programming!" ' '
["I","love","functional","programming!"]
*Main> splitByElement [1,2,1,2,3,4,5,5,6,4,1,2,0,1,4] 1
[[2],[2,3,4,5,5,6,4],[2,0],[4]]
*Main> splitByElement [1,2,1,2,3,4,5,5,6,4,1,2,0,1,4] 5
[[1,2,1,2,3,4],[6,4,1,2,0,1,4]]