Εργαστήριο 2 στη Ηaskell

Εξάσκηση (εκφωνήσεις και λύσεις ασκήσεων)

Άσκηση H2E1 Γράψτε τις ακόλουθες αναδρομικές συναρτήσεις που αφορούν αριθμητικές τιμές:

1. doubleFactorial n , που υπολογίζει το διπλό παραγοντικό ενός αριθμού n. Το διπλό παραγοντικό ορίζεται ως το γινόμενο όλων των ακεραίων από το 1 μέχρι και τον αριθμό n που είναι είτε άρτιοι είτε περιττοί, ανάλογα με το εάν το n είναι άρτιο ή περιττό αντίστοιχα (π.χ. το διπλό παραγοντικό του 7 είναι 1 * 3 * 5 * 7 = 105).
2. pow x, y, που υπολογίζει το x^y (με x και y ακέραιες θετικές τιμές)
3. Έστω ότι δίνεται η συνάρτηση plusOne x = x + 1. Χωρίς να χρησιμοποιήσετε τον τελεστή +, ορίστε τη συνάρτηση addition έτσι ώστε η addition x y να προσθέτει τα x και y.
4. log2 x, που υπολογίζει τον ακέραιο λογάριθμο με βάση 2 του ορίσματος που δέχεται (π.χ. log2 1 = 0, log2 16 = 4, log2 11 = 3).

Λύση άσκησης H2E1

doubleFactorial :: (Eq p, Num p) => p -> p
doubleFactorial 0 = 1
doubleFactorial 1 = 1
doubleFactorial n = n * doubleFactorial (n - 2)

pow :: (Eq t, Num t, Num p) => p -> t -> p
pow x 0 = 1
pow x y = x * pow x (y - 1)

plusOne :: (Num a) => a -> a
plusOne x = x + 1

addition :: (Eq t1, Num t1, Num t2) => t2 -> t1 -> t2
addition x 0 = x
addition x y = plusOne (addition x (y - 1))

log2 :: (Num p, Integral t) => t -> p
log2 1 = 0
log2 x = 1 + log2 (x `div` 2)

Μεταγλώττιση και εκτέλεση:

$ ghci h2e1.hs
GHCi, version 9.4.8: https://www.haskell.org/ghc/  :? for help
[1 of 2] Compiling Main             ( h2e1.hs, interpreted )
Ok, one module loaded.
ghci> doubleFactorial 7
105
ghci> pow 2 10
1024
ghci> addition 5 7
12
ghci> log2 1
0
ghci> log2 16
4
ghci> log2 11
3

Άσκηση H2E2 Γράψτε τις ακόλουθες αναδρομικές συναρτήσεις που αφορούν λίστες. Προσέξτε ότι όλες οι ακόλουθες συναρτήσεις υπάρχουν στο Prelude, άρα θα πρέπει να δοθούν διαφορετικά ονόματα για τους ελέγχους σας με το GHCi.

1. replicate :: Int -> a -> [a], που λαμβάνει έναν μετρητή και ένα στοιχείο και επιστρέφει μια λίστα στην οποία το στοιχείο επαναλαμβάνεται count φορές. Για παράδειγμα replicate 3 'a' = "aaa".
2. valueAt :: [a] -> Int -> a, που επιστρέφει το στοιχείο σε μια συγκεκριμένη θέση. Το πρώτο στοιχείο βρίσκεται στη θέση 0, το δεύτερο στη θέση 1, κ.λπ. (π.χ. valueAt [7,8,1,3] 2 = 1). Η συνάρτηση αυτή υπάρχει στο Prelude και είναι η (!!).
3. myZip :: [a] -> [b] -> [(a, b)], που δέχεται δύο λίστες και τις συνδυάζει, έτσι ώστε, στη λίστα που προκύπτει, το πρώτο ζεύγος να σχηματίζεται από τα στοιχεία στην πρώτη θέση των δύο λιστών, το δεύτερο ζεύγος στη λίστα να σχηματίζεται από τα στοιχεία στη δεύτερη θέση των δύο λιστών κ.ο.κ. Για παράδειγμα myZip [1,2,3] "abc" = [(1, 'a'), (2, 'b'), (3, 'c')]. Αν οι δύο λίστες δεν έχουν το ίδιο μέγεθος τότε σταματάμε όταν μια από τις δύο λίστες δεν έχει πλέον στοιχεία. Η συνάρτηση αυτή υπάρχει στο Prelude με όνομα zip.

Λύση άσκησης H2E2

myReplicate :: (Eq t, Num t) => t -> a -> [a]
myReplicate 0 _ = []
myReplicate n x = x : myReplicate (n - 1) x

valueAt :: (Eq t, Num t) => [p] -> t -> p
valueAt [] _ = error "Out of bounds error"
valueAt (x : _) 0 = x
valueAt (x : xs) n = valueAt xs (n - 1)

myZip :: [a] -> [b] -> [(a, b)]
myZip _ [] = []
myZip [] _ = []
myZip (x : xs) (y : ys) = (x, y) : myZip xs ys

Μεταγλώττιση και εκτέλεση:

$ ghci h2e2.hs
GHCi, version 9.4.8: https://www.haskell.org/ghc/  :? for help
ghci> :l h2e2.hs
[1 of 2] Compiling Main             ( h2e2.hs, interpreted )
Ok, one module loaded.
ghci> replicate 3 'a'
"aaa"
ghci> valueAt [7,8,1,3] 2
1
ghci> myZip [1,2,3] "abc"
[(1,'a'),(2,'b'),(3,'c')]

Άσκηση H2E3 Γράψτε τις ακόλουθες αναδρομικές συναρτήσεις, προσθέτοντας και τις κατάλληλες υπογραφές τύπων:

1. takeInt, επιστρέφει τα πρώτα n στοιχεία μιας λίστας. Για παράδειγμα, η takeInt 4 [11,21,31,41,51,61] θα πρέπει να επιστρέφει [11,21,31,41]. Η συνάρτηση αυτή υπάρχει στο Prelude με όνομα take.
2. dropInt, αφαιρεί τα πρώτα n στοιχεία μιας λίστας και επιστρέφει τα υπόλοιπα. Για παράδειγμα, η dropInt 3 [11,21,31,41,51] θα πρέπει να επιστρέφει [41,51]. Η συνάρτηση αυτή υπάρχει στο Prelude με όνομα drop.
3. sumInt, επιστρέφει το άθροισμα των στοιχείων μιας λίστας. Η συνάρτηση αυτή υπάρχει στο Prelude με όνομα sum.
4. scanSum, προσθέτει τα στοιχεία μιας λίστας και επιστρέφει μια λίστα με τα συσσωρευτικά αθροίσματα. Για παράδειγμα, η scanSum [2,3,4,5] θα πρέπει να επιστρέφει [2,5,9,14].

Λύση άσκησης H2E3

takeInt :: Int -> [a] -> [a]
takeInt _ [] = []
takeInt 0 _ = []
takeInt n (x : xs) = x : takeInt (n - 1) xs

dropInt :: Int -> [a] -> [a]
dropInt 0 x = x
dropInt _ [] = []
dropInt n (x : xs) = dropInt (n - 1) xs

sumInt :: [Int] -> Int
sumInt [] = 0
sumInt (x : xs) = x + sumInt xs

scanSum :: [Int] -> [Int]
scanSum [] = []
scanSum [x] = [x]
scanSum (x : y : xs) = x : scanSum ((x + y) : xs)

Μεταγλώττιση και εκτέλεση:

$ ghci h2e3.hs
GHCi, version 9.4.8: https://www.haskell.org/ghc/  :? for help
[1 of 2] Compiling Main             ( h2e3.hs, interpreted )
Ok, one module loaded.
ghci> takeInt 4 [11,21,31,41,51,61]
[11,21,31,41]
ghci> dropInt 3 [11,21,31,41,51]
[41,51]
ghci> sumInt [1,2,3,4,5]
15
ghci> scanSum [2,3,4,5]
[2,5,9,14]

Άσκηση H2E4 Χρησιμοποιήστε τη συνάρτηση map για να δημιουργήσετε συναρτήσεις που δεδομένης μιας λίστας xs με ακεραίους να επιστρέφει:

• Μια λίστα με το αντίθετο κάθε στοιχείου. Χρησιμοποιήστε τη συνάρτηση negate.
• Μια λίστα με λίστες ακεραίων xss, που για κάθε στοιχείο του xs, να περιέχει τους διαιρέτες του xs. Χρησιμοποιήστε τη συνάρτηση divisors p = [ f | f <- [1..p], mod p f == 0 ] για να λάβετε τους διαιρέτες.

Λύση άσκησης H2E4

negateList :: (Num b) => [b] -> [b]
negateList xs = map negate xs

divisors :: Int -> [Int]
divisors p = [f | f <- [1 .. p], p `mod` f == 0]

divisorsList :: [Int] -> [[Int]]
divisorsList xs = map divisors xs

Μεταγλώττιση και εκτέλεση:

$ ghci h2e4.hs
GHCi, version 9.4.8: https://www.haskell.org/ghc/  :? for help
[1 of 2] Compiling Main             ( h2e4.hs, interpreted )
Ok, one module loaded.
ghci> negateList [1,2,3,4]
[-1,-2,-3,-4]
ghci> divisorsList [9, 15, 20]
[[1,3,9],[1,3,5,15],[1,2,4,5,10,20]]

Άσκηση H2E5 Ο αλγόριθμος του Luhn χρησιμοποιείται ως ένας απλός έλεγχος εγκυρότητας για αριθμούς καρτών που εκδίδουν οι τράπεζες. Οι κανόνες είναι οι ακόλουθοι:

• Από το προτελευταίο ψηφίο και προς τα αριστερά με βήματα 2 ψηφίων, διπλασίασε κάθε ψηφίο.
• Αν το αποτέλεσμα του διπλασιασμού είναι μεγαλύτερο από 9, αφαίρεσε 9.
• Πρόσθεσε όλα τα ψηφία μαζί.
• Αν ο άθροισμα είναι πολλαπλάσιο του 10, η κάρτα είναι έγκυρη.

Για παράδειγμα ο αριθμός 1 7 8 4 είναι έγκυρος διότι:

(2*1) 7 (2*8) 4 -> 2 7 (16-9) 4 -> 2 7 7 4 -> 2 + 7 + 7 + 4 = 20 -> 20 % 10 == 0 

Υλοποιήστε ένα πρόγραμμα που να δέχεται από τον χρήστη έναν αριθμό και να εμφανίζει αν είναι έγκυρος αριθμός πιστωτικής κάρτας ή όχι.