Difference between revisions of "FP Laboratory 2"

From Marek Běhálek Wiki
Jump to navigation Jump to search
 
(16 intermediate revisions by 2 users not shown)
Line 99: Line 99:
 
factorial'' n = if n==0 then 1 else n * factorial'' (n-1)
 
factorial'' n = if n==0 then 1 else n * factorial'' (n-1)
 
</syntaxhighlight>
 
</syntaxhighlight>
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/DEAQ69276]]
+
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/WRUF28416]]
 
</div>
 
</div>
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>
Line 126: Line 126:
 
   tmp x a b = tmp (x-1) b (a+b)
 
   tmp x a b = tmp (x-1) b (a+b)
 
</syntaxhighlight>
 
</syntaxhighlight>
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/DEAQ69276]]
+
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/WRUF28416]]
 
</div>
 
</div>
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>
Line 156: Line 156:
 
             | otherwise = x `mod` 4 == 0
 
             | otherwise = x `mod` 4 == 0
 
</syntaxhighlight>
 
</syntaxhighlight>
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/DEAQ69276]]
+
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/WRUF28416]]
 
</div>
 
</div>
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>
Line 183: Line 183:
 
max3 x y z = (x `max2` y) `max2` z
 
max3 x y z = (x `max2` y) `max2` z
 
</syntaxhighlight>
 
</syntaxhighlight>
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/DEAQ69276]]
+
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/WRUF28416]]
 
</div>
 
</div>
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>
Line 208: Line 208:
 
combinations' n k = fromIntegral(factorial n) `div` fromIntegral(factorial k * factorial (n-k))
 
combinations' n k = fromIntegral(factorial n) `div` fromIntegral(factorial k * factorial (n-k))
 
</syntaxhighlight>
 
</syntaxhighlight>
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/DEAQ69276]]
+
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/WRUF28416]]
 
</div>
 
</div>
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>
Line 231: Line 231:
 
                       in if d<0 then 0 else if d == 0 then 1 else 2
 
                       in if d<0 then 0 else if d == 0 then 1 else 2
 
</syntaxhighlight>
 
</syntaxhighlight>
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/DEAQ69276]]
+
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/WRUF28416]]
 
</div>
 
</div>
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>
Line 256: Line 256:
 
gcd2 a b = gcd2 b (a `mod` b)
 
gcd2 a b = gcd2 b (a `mod` b)
 
</syntaxhighlight>
 
</syntaxhighlight>
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/DEAQ69276]]
+
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/WRUF28416]]
 
</div>
 
</div>
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>
Line 279: Line 279:
 
                   | otherwise = isPrimeTest n (x-1)
 
                   | otherwise = isPrimeTest n (x-1)
 
</syntaxhighlight>
 
</syntaxhighlight>
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/DEAQ69276]]
+
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/WRUF28416]]
 
</div>
 
</div>
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>
 +
 +
<translate>
 +
== Additional exercises == <!--T:16-->
 +
* Define a function that returns true iff all three arguments are different.
 +
</translate>
 +
 +
<syntaxhighlight lang="Haskell">threeDifferent :: Int -> Int -> Int -> Bool</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*Main> threeDifferent 4 5 6
 +
True
 +
*Main> threeDifferent 6 5 6
 +
False
 +
</syntaxhighlight>
 +
 +
<translate>
 +
<!--T:17-->
 +
* Define a function that returns true iff all four arguments are equal.
 +
</translate>
 +
 +
<syntaxhighlight lang="Haskell">fourEqual :: Int -> Int -> Int -> Int-> Bool</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*Main> fourEqual 4 5 6 7
 +
False
 +
*Main> fourEqual 4 4 4 4
 +
True
 +
</syntaxhighlight>
 +
 +
<translate>
 +
<!--T:18-->
 +
* Define a function that computes the average of three integers.
 +
</translate>
 +
 +
<syntaxhighlight lang="Haskell">averageThree :: Int -> Int -> Int -> Float</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*Main> averageThree 4 10 20
 +
11.333333
 +
</syntaxhighlight>
 +
 +
<translate>
 +
<!--T:19-->
 +
* Define a function that returns how many of its inputs are larger than their average value.
 +
</translate>
 +
 +
<syntaxhighlight lang="Haskell">howManyAboveAverage :: Int -> Int -> Int -> Int</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*Main> howManyAboveAverage 5 5 5
 +
0
 +
*Main> howManyAboveAverage 10 50 50
 +
2
 +
</syntaxhighlight>
 +
 +
<translate>
 +
<!--T:20-->
 +
* Using the multiplication over the integer numbers, implement a recursive function that realizes the n-th power of an integer number.
 +
</translate>
 +
<syntaxhighlight lang="Haskell">power :: Int -> Int -> Int</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*Main> power 2 3                   
 +
8
 +
*Main> power 4 2
 +
16
 +
*Main> power 4 3
 +
64
 +
</syntaxhighlight>
 +
 +
<translate>
 +
<!--T:21-->
 +
* Using the addition over the integer numbers, implement a recursive function that realizes the multiplication of integer numbers.
 +
</translate>
 +
<syntaxhighlight lang="Haskell">mult :: Int -> Int -> Int</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*Main> mult 4 5
 +
20
 +
*Main> mult 4 9
 +
36
 +
*Main> mult 4 0
 +
0
 +
</syntaxhighlight>
 +
 +
<translate>
 +
<!--T:22-->
 +
* Define a recursive function that computes the remainder of integer division.
 +
</translate>
 +
<syntaxhighlight lang="Haskell">mod' :: Int -> Int -> Int</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*Main> mod' 40 7
 +
5
 +
*Main> mod' 30 5
 +
0
 +
*Main> mod' 20 7
 +
6
 +
</syntaxhighlight>

Latest revision as of 06:35, 19 September 2023

Types

  • Using the GHCi command :info, learn the type of the following functions (and operators): +, sqrt, succ, max
  • Get the information about the data type of following expressions and evaluate them. it is possible using the command :type. You can switch this option on for all commands by :set +t (removing by :unset +t).
5 + 8 
3 * 5 + 8
2 + 4
sqrt 16 
succ 6
succ 7
pred 9
pred 8
sin (pi / 2)
truncate pi
round 3.5
round 3.4 
floor 3.7 
ceiling 3.3
mod 10 3
odd 3
  • At presentations, we have spoken about some basic types: Int, Double, Bool, Char. For each of previous expressions assign them the most appropriate of these basic data types. You can verify your guess by using ::. For example, for the first expression, let's assume it is Int. We can cast the result to integer and get the following result.
Prelude> :type (5 + 8) :: Int
(5 + 8) :: Int :: Int

If we try incorrect conversion to Char, we get the following result.

Prelude> :type (5 + 8) :: Char

<interactive>:1:2: error:
    * No instance for (Num Char) arising from a use of `+'
    * In the expression: (5 + 8) :: Char

For this expression, also the type Double works.

Prelude> :type (5 + 8) :: Double
(5 + 8) :: Double :: Double

Reasoning about types

For following expression, try to determine:

  • if the expression's type is correct;
  • what will be the type of the result;
  • what will be the result;
  • put the expression into the interpreter, and verify your claims.
5.9/7
(floor 5.9)/7
floor 5.9/7
fromIntegral floor 5.9/7
fromIntegral (floor 5.9)/7
div (floor 5.9) 7
(floor 5.9) div 7
(floor 5.9) `div` 7
mod 10/2 3
mod (floor (10/2)) 3

Simple functions

Implement following functions:

  • Function that computes a factorial of a given number.
    Video logo.png
factorial :: Int -> Int
*Main> factorial 5
120
factorial  :: Int -> Int
factorial  0 = 1
factorial  n = n * factorial  (n-1)

factorial'  :: Int -> Int
factorial' n | n==0 = 1
             | otherwise = n * factorial'' (n-1)

factorial''  :: Int -> Int        
factorial'' n = if n==0 then 1 else n * factorial'' (n-1)
Try it!
  • Function that computes n-th number in Fibonacci sequence.
    Video logo.png
fib :: Int -> Int
*Main> fib 5      
8
fib :: Int->Int
fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

fib' :: Int -> Int
fib' n = tmp n 1 1 where
  tmp 0 a _ = a 
  tmp x a b = tmp (x-1) b (a+b)
Try it!
  • Function that checks if a year is a leap-year (divisible without remainder by 4 and it is not divisible by 100. If it is divisible by 400, it is a leap-year).
leapYear :: Int -> Bool
*Main> leapYear 2000
True
*Main> leapYear 2020
True
*Main> leapYear 2100
False
*Main> leapYear 2019
False
leapYear :: Int -> Bool
leapYear x = x `mod` 4 == 0 && x `mod` 100 /= 0 || x `mod` 400 == 0

leapYear' :: Int -> Bool
leapYear' x | x `mod` 400 == 0 = True
            | x `mod` 100 == 0 = False
            | otherwise = x `mod` 4 == 0
Try it!
  • Implement two functions that returns a maximum from 2 respectively 3 given parameters.
max2 :: Int -> Int -> Int
max3 :: Int -> Int -> Int -> Int
*Main> max2 5 8
8
*Main> max3 5 8 4
8
max2 :: Int -> Int -> Int
max2 x y | x >= y = x
         |otherwise = y

max3 :: Int -> Int -> Int -> Int
max3 x y z = (x `max2` y) `max2` z
Try it!
  • Term combination is a selection of items from a collection, such that (unlike permutations) the order of elements in this selection does not matter. Compute the number of possible combinations if we are taking k things from the collection of n things.
combinations :: Int -> Int -> Int
*Main> combinations 8 5
56
factorial  :: Int -> Int
factorial  0 = 1
factorial  n = n * factorial  (n-1)

combinations :: Int -> Int -> Int
combinations n k = factorial n `div` (factorial k * factorial (n-k))

combinations' :: Int -> Int -> Int
combinations' n k = fromIntegral(factorial n) `div` fromIntegral(factorial k * factorial (n-k))
Try it!
  • Implement a function that computes the number of solutions for a quadratic equation. This quadratic equation will be given using standard coefficients: a, b, c.
numberOfRoots :: Int -> Int -> Int -> Int
-- To simplify the solution, let construct can be used
f x y = let a = x + y
        in a * a
*Main> numberOfRoots 1 4 2
2
numberOfRoots :: Int -> Int -> Int -> Int
numberOfRoots a b c = let d = b*b - 4 * a *c
                      in if d<0 then 0 else if d == 0 then 1 else 2
Try it!
  • Implement a function that computes greatest common divider for two given numbers.
    Video logo.png
gcd' :: Int -> Int -> Int
*Main> gcd' 30 18
6
gcd' :: Int -> Int -> Int
gcd' a b | a > b = gcd' (a-b) b
         | a < b = gcd' a (b-a)
         | a==b = a

gcd2 :: Int -> Int -> Int         
gcd2 a 0 = a
gcd2 a b = gcd2 b (a `mod` b)
Try it!
  • Implement a function that compute, if a given number is a prime number.
    Video logo.png
isPrime :: Int -> Bool
*Main> isPrime 7
True
isPrime :: Int -> Bool
isPrime 1 = False
isPrime y = isPrimeTest y (y-1) where
  isPrimeTest _ 1 = True 
  isPrimeTest n x | n `mod` x ==0 = False
                  | otherwise = isPrimeTest n (x-1)
Try it!

Additional exercises

  • Define a function that returns true iff all three arguments are different.
threeDifferent :: Int -> Int -> Int -> Bool
*Main> threeDifferent 4 5 6
True
*Main> threeDifferent 6 5 6
False
  • Define a function that returns true iff all four arguments are equal.
fourEqual :: Int -> Int -> Int -> Int-> Bool
*Main> fourEqual 4 5 6 7
False
*Main> fourEqual 4 4 4 4
True
  • Define a function that computes the average of three integers.
averageThree :: Int -> Int -> Int -> Float
*Main> averageThree 4 10 20
11.333333
  • Define a function that returns how many of its inputs are larger than their average value.
howManyAboveAverage :: Int -> Int -> Int -> Int
*Main> howManyAboveAverage 5 5 5
0
*Main> howManyAboveAverage 10 50 50 
2
  • Using the multiplication over the integer numbers, implement a recursive function that realizes the n-th power of an integer number.
power :: Int -> Int -> Int
*Main> power 2 3                    
8
*Main> power 4 2
16
*Main> power 4 3
64
  • Using the addition over the integer numbers, implement a recursive function that realizes the multiplication of integer numbers.
mult :: Int -> Int -> Int
*Main> mult 4 5
20
*Main> mult 4 9
36
*Main> mult 4 0
0
  • Define a recursive function that computes the remainder of integer division.
mod' :: Int -> Int -> Int
*Main> mod' 40 7
5
*Main> mod' 30 5
0
*Main> mod' 20 7
6