Difference between revisions of "FP Laboratory 6"

From Marek Běhálek Wiki
Jump to navigation Jump to search
(Marked this version for translation)
(Marked this version for translation)
 
(2 intermediate revisions by one other user not shown)
Line 1: Line 1:
 
<translate>
 
<translate>
== Operators == <!--T:1-->
+
== 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.  
Line 121: Line 121:
 
</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]]