Министерство науки и высшего образования Российской Федерации федеральное государственное автономное образовательное учреждение высшего образования
«Национальный исследовательский университет ИТМО»
ФПИиКТ, Системное и Прикладное Программное Обеспечение
Лабораторная работа №1
по Функциональному программированию
Выполнил: Лавлинский М. С.
Группа: P34112
Преподаватель: Пенской Александр Владимирович
```
-- check that given number is palindrome
isPalindrome :: Int -> Bool
isPalindrome n = let s = show n in s == reverse s
-- return largest palindrome product for x * [999.100]
largestPalindrome :: Int -> Int -> Int
largestPalindrome x y =
if | x > 999 -> (-1)
| y <= 99 -> 0
| isPalindrome (x*y) -> x * y
| otherwise -> largestPalindrome x (y-1)
```
-
монолитная реализация
- хвостовая рекурсия
-- tail recursive solution -- return largest palindrome product for [x..999] * [999.100] largestPalindromeProduct :: Int -> Int-> Int largestPalindromeProduct x acc = if x == 1000 then acc else largestPalindromeProduct (x+1) (max (largestPalindrome x 999) acc) -- return largest palindrome product for [100..999] * [999.100] solution4TailRec :: Int solution4TailRec = largestPalindromeProduct 100 0- рекурсия
-- return largest palindrome product for [x..999] * [y..999] largestPalindrome' :: Int -> Int -> Int largestPalindrome' x y = let curr = if x <= 999 && y <= 999 && isPalindrome (x*y) then x*y else 0 in if | x > 999 -> curr | y > 999 -> max curr $ largestPalindrome' (x+1) 100 | otherwise -> max curr $ largestPalindrome' x (y+1) -- return largest palindrome product for [100..999] * [999.100] solution4Rec :: Int solution4Rec = largestPalindrome' 100 100 -
модульная реализация
generateProducts :: [Int] -> Int -> Int -> [Int] generateProducts list x y = if | y > 999 -> generateProducts list (x+1) 100 | x > 999 -> list | otherwise -> generateProducts ((x*y) : list) x (y+1) -- filter our products, return palindromes filterProducts :: [Int] -> [Int] filterProducts = filter isPalindrome -- get maximal palindrome solution4ModuleImpl :: Int solution4ModuleImpl = foldl max 0 $ filterProducts $ generateProducts [] 100 100 -
генерация последовательности при помощи отображения (map)
solution4Map :: Int solution4Map = maximum $ map (`largestPalindrome` 999) [100..999] -
работа с бесконечными списками для языков поддерживающих ленивые коллекции или итераторы как часть языка
-- handle one by one element from infinite list, while number less than 999 largestPalindromeProduct :: [Int] -> [Int] -> [Int] largestPalindromeProduct input palindromes = let x = largestPalindrome (head input) 999 in if x == (-1) then palindromes else largestPalindromeProduct (tail input) (x : palindromes) solution4InfList :: Int solution4InfList = maximum $ largestPalindromeProduct [1..] [] -
реализация на любом удобном языке программировании
int LargestPalindromeProduct() { int largest = 0, num, mod, numCopy, reversed; for(int i = 1; i <= 999; i++) { for(int j = 1; j <= i; j++) { reversed = 0; num = i*j; numCopy = num; do { mod = num % 10; reversed = (reversed * 10) + mod; num = num / 10; } while (num > 0); if(reversed == numCopy && reversed > largest) { largest = reversed; } } } return largest; }
Функция перебирает все пары чисел в диапазоне [1..999] и возвращает наибольшее произведение, являющееся палиндромом
-- return list of factors
factors :: Int -> [Bool]
factors x =
if x <= 0 then [True] else map (\y -> (x `mod` y) == 0) [2..x-1]
or' :: Bool -> Bool -> Bool
or' x y = x || y
-- check that given number is prime
isPrime :: Int -> Bool
isPrime x = not (foldl or' False (factors x))
-- calculate formula - x^2 + a*x + b
calcFormula :: Int -> Int -> Int -> Int
calcFormula a b x = x*x + a*x + b
-- get the size of the sequence
calcPrimes :: Int -> Int -> Int -> Int
calcPrimes a b x =
let n = calcFormula a b x
in
if isPrime n then calcPrimes a b (x+1) else x
-
монолитная реализация
- хвостовая рекурсия
quadraticPrimes :: Int -> Int -> Int -> Int -> Int -> Int -> Int quadraticPrimes a b x result product maxR = let maxRes = if result > maxR then result else maxR newProduct = if result > maxR then a*b else product n = calcFormula a b x in if | isPrime n -> quadraticPrimes a b (x+1) (result+1) newProduct maxRes | a < (-10) -> newProduct | b <= (-10) -> quadraticPrimes (a-1) 10 0 0 newProduct maxRes | otherwise -> quadraticPrimes a (b-1) 0 0 newProduct maxRes solution27TailRec :: Int solution27TailRec = quadraticPrimes 9 10 0 0 0 0- рекурсия
-- quadraticPrimes' :: Int -> Int -> Int -> Int -> Int quadraticPrimes' a b result product' = let amount = calcPrimes a b 0 newResult = if a < 10 && b <= 10 && amount > result then amount else result newProduct = if a < 10 && b <= 10 && amount > result then a*b else product' in if | a >= 10 -> newProduct | b > 10 -> quadraticPrimes' (a + 1) (-10) newResult newProduct | otherwise -> quadraticPrimes' a (b+1) newResult newProduct solution27Rec :: Int solution27Rec = quadraticPrimes' (-9) (-10) 0 0 -
модульная реализация
-- generating a sequence of the number of primes for all a and b generateSeq :: [(Int, Int)] -> Int -> Int -> [(Int, Int)] generateSeq list a b = if | a < (-9) -> list | b < (-10) -> generateSeq ((a*b, calcPrimes a b 0) : list) (a-1) 10 | otherwise -> generateSeq ((a*b, calcPrimes a b 0) : list) a (b-1) max' :: (Int, Int) -> (Int, Int) -> (Int, Int) max' x y = if snd x > snd y then x else y solution27ModuleImpl :: Int solution27ModuleImpl = let generated = generateSeq [] 9 10 in fst $ foldl1 max' generated -
генерация последовательности при помощи отображения (map)
-- generating a sequence of the number of primes for all a and b generateSeq :: [[(Int, Int)]] generateSeq = map (\a -> map (\b -> (a*b,calcPrimes a b 0)) [(-10)..10] ) [(-9)..9] -- compare two pairs by the number of primes max' :: (Int, Int) -> (Int, Int) -> (Int, Int) max' x y = if snd x > snd y then x else y -- get maximal element from list, using max' for compare maxInList :: [(Int, Int)] -> (Int, Int) maxInList = foldl1 max' solution27Map :: Int solution27Map = fst $ foldl max' (0,0) $ map maxInList generateSeq -
работа с бесконечными списками для языков поддерживающих ленивые коллекции или итераторы как часть языка
-- returns the number of first sequental primes calcPrimes' :: [Int] -> Int -> Int -> Int calcPrimes' input a b = let x = head input n = if x <= 1000 then calcFormula a b x else (-1) in if isPrime n then calcPrimes' (tail input) a b else x -- recursive change a and b and return a*b for maximal calcPrimes' quadraticPrimes' :: Int -> Int -> Int -> Int -> Int quadraticPrimes' a b result product' = let amount = calcPrimes' [0..] a b newResult = if a < 1000 && b <= 1000 && amount > result then amount else result newProduct = if a < 1000 && b <= 1000 && amount > result then a*b else product' in if | a >= 1000 -> newProduct | b > 1000 -> quadraticPrimes' (a+1) (-1000) newResult newProduct | otherwise -> quadraticPrimes' a (b+1) newResult newProduct solution27InfList :: Int solution27InfList = quadraticPrimes' (-999) (-1000) 0 0 -
реализация на любом удобном языке программировании
bool isPrime(int x) { if(x < 0) return false; for(long long i = 2; i * i <= x ; i++) { if(x % i == 0) { return false; } } return true; } int result(int a, int b, int x) { return x*x + a*x + b; } int MaxAB() { int max = 0; int maxA = 0, maxB = 0; for(int a = -999; a <= 999; a++) { for(int b = -1000; b <= 1000; b++ ) { int localCounter = 0; for(int x = 0; ; x++) { if(isPrime(result(a, b, x))) { localCounter++; } else { break; } } if(max < localCounter) { max = localCounter; maxA = a; maxB = b; } } } return maxA * maxB; }
В ходе выполнения лабораторной работы мною были изученые основные конструкции языка haskell, различные виды записи if, функции свертки и фильтрации foldl, filter, функция отображения map, работа со списками в т.ч с бесконечными. Также мною была применена рекурсия и хвостовая рекурсия в языке haskell.