SHARE
TWEET

Untitled

a guest Jan 24th, 2020 72 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. module Exercises where  -- Вспомогательная строчка, чтобы можно было использовать функции в других файлах.
  2. import Control.Arrow
  3. import Data.Char
  4. import Data.Text(isInfixOf, pack)
  5. import Prelude hiding (sum, concat, foldr, map)
  6. {- HLINT ignore "Use foldr" -}
  7.  
  8. -- 1) Выделение функции высшего порядка.
  9. -- Функция sum' считает сумму чисел в списке при помощи функции sum''.
  10. -- Функция sum'' x xs считает сумму чисел в списке xs плюс x.
  11. -- Реализуйте функцию sum'' рекурсивно, не используя функции, кроме (+).
  12. --
  13. -- >>> sum'' 10 [2, 3]
  14. -- 15
  15. sum' :: [Int] -> Int
  16. sum' = sum'' 0
  17.  
  18. sum'' :: Int -> [Int] -> Int
  19. sum'' ini [] = ini
  20. sum'' ini (x:xs) = x + sum'' ini xs
  21.  
  22. -- Функция concat' принимает на вход список списков и возвращает конкатенацию
  23. -- этих списков. Она использует функцию concat'', которая дополнительно
  24. -- принимает начальное значение, которое дописывается в конец.
  25. -- Реализуйте функцию concat'' рекурсивно, не используя функции, кроме (++).
  26. --
  27. -- >>> concat'' "c" ["a", "b"]
  28. -- "abc"
  29. concat' :: [[a]] -> [a]
  30. concat' = concat'' []
  31.  
  32. concat'' :: [a] -> [[a]] -> [a]
  33. concat'' ini [] = ini
  34. concat'' ini (x:xs) = x ++ concat'' ini xs
  35.  
  36. -- Функция hash' принимает на вход строку s и считает полиномиальный
  37. -- хэш от строки по формуле hash' s_0...s_{n - 1} =
  38. --  s_0 + p * s_1 + ... + p^{n - 1} * s_{n - 1}, где p - константа
  39. -- (в данном случае, 17).
  40. -- Функция hash' использует функцию hash'', которая принимает на вход
  41. -- начальное значение хэша и строку. Реализуйте функцию hash'' рекурсивно,
  42. -- не используя функции, кроме (+), (*) и (^).
  43. --
  44. -- >>> hash'' 10 "AB"
  45. -- 4077
  46. -- >>> (ord 'A') + (ord 'B') * p + 10 * p ^ 2
  47. -- 4077
  48. p :: Int
  49. p = 17
  50.  
  51. hash' :: String -> Int
  52. hash' = hash'' 0
  53.  
  54. hash'' :: Int -> String -> Int
  55. hash'' ini "" = ini
  56. hash'' ini (x:xs) = ord x + p * hash'' ini xs
  57.  
  58. -- Выделите общую логику предыдущих функций и реализуйте функцию высшего порядка foldr',
  59. -- не используя никаких стандартных функций.
  60. foldr' :: (a -> b -> b) -> b -> [a] -> b
  61. foldr' f ini [] = ini
  62. foldr' f ini (x:xs) = f x $ foldr' f ini xs
  63.  
  64. -- Реализуйте функцию map' (которая делает то же самое, что обычный map)
  65. -- через функцию foldr', не используя стандартных функций.
  66. map' :: (a -> b) -> [a] -> [b]
  67. map' f xs = foldr' (map'' f) [] xs
  68.  
  69. map'' :: (a -> b) -> a -> [b] -> [b]
  70. map'' f x y = (f x):y
  71. -- 2) Maybe
  72. -- Maybe a - это специальный тип данных, который может принимать либо
  73. -- значение Nothing, либо значение Just x, где x --- значение типа a.
  74. -- Его удобно использовать для сообщения об ошибке.
  75.  
  76. -- Даны функции tryHead и tryTail, реализованные следующим образом
  77. -- >>> tryHead []
  78. -- Nothing
  79. -- >>> tryHead ["hello"]
  80. -- Just "hello"
  81. -- >>> tryHead [1, 2, 3]
  82. -- Just 1
  83. tryHead :: [a] -> Maybe a
  84. tryHead (x:_) = Just x
  85. tryHead _     = Nothing
  86.  
  87. --
  88. -- >>> tryTail []
  89. -- Nothing
  90. -- >>> tryTail ["hello"]
  91. -- Just []
  92. -- >>> :t tryTail ["hello"]
  93. -- tryTail ["hello"] :: [[Char]]
  94. -- >>> tryTail [1, 2, 3]
  95. -- Just [2,3]
  96. tryTail :: [a] -> Maybe [a]
  97. tryTail (_:xs) = Just xs
  98. tryTail _      = Nothing
  99.  
  100. -- Также предоставлен пример функции, которая возвращает второй элемент
  101. -- списка или Nothing, если второго элемента в списке нет.
  102. --
  103. -- >>> secondElement []
  104. -- Nothing
  105. -- >>> secondElement "a"
  106. -- Nothing
  107. -- >>> secondElement "ab"
  108. -- Just 'b'
  109. secondElement :: [a] -> Maybe a
  110. secondElement xs = case tryTail xs of
  111.                     Just a  -> tryHead a
  112.                     _       -> Nothing
  113.  
  114. -- Используя функции tryHead и tryTail, а также case и сопоставление с
  115. -- образцом (pattern matching) только для Maybe (но не для списков) реализуйте
  116. -- без использования стандартных функций (при этом разрешается заводить свои
  117. -- дополнительные функции, используя where):
  118.  
  119. -- Функцию thirdElementOfSecondList, которая принимает на вход список
  120. -- списков, и возвращает третий элемент второго списка или Nothing, если
  121. -- второго списка или третьего элемента в нём не существует.
  122. --
  123. -- >>> thirdElementOfSecondList []
  124. -- Nothing
  125. -- >>> thirdElementOfSecondList ["abcd"]
  126. -- Nothing
  127. -- >>> thirdElementOfSecondList [[], [1, 2], [3, 4]]
  128. -- Nothing
  129. -- >>> thirdElementOfSecondList [["a"], ["b", "c", "d"]]
  130. -- Just "d"
  131. thirdElementOfSecondList :: [[a]] -> Maybe a
  132. thirdElementOfSecondList xs = case secondElement xs of
  133.                                Just xs -> thirdElement xs
  134.                                _       -> Nothing
  135.    where
  136.        thirdElement xs = case tryTail xs of
  137.                            Just as -> secondElement as
  138.                            _       -> Nothing
  139.  
  140. -- Функцию fifthElement, которая возвращает пятый элемент списка или Nothing,
  141. -- если пятого элемента в списке нет.
  142. -- >>> fifthElement []
  143. -- Nothing
  144. -- >>> fifthElement "abcd"
  145. -- Nothing
  146. -- >>> fifthElement [1, 2, 3, 4, 5]
  147. -- Just 5
  148. fifthElement :: [a] -> Maybe a
  149. fifthElement xs = case tryTail xs of
  150.                        Just as -> fourElement as
  151.                        _           -> Nothing
  152.    where
  153.        fourElement xs = case tryTail xs of
  154.                        Just as -> thirdElement as
  155.                        _       -> Nothing
  156.        thirdElement xs = case tryTail xs of
  157.                            Just as -> secondElement as
  158.                            _       -> Nothing
  159.  
  160. -- Выделите общую логику в оператор ~~>.
  161. (~~>) :: Maybe a -> (a -> Maybe b) -> Maybe b
  162. (~~>) ma f = case ma of
  163.               Just a -> f a
  164.               _       -> Nothing
  165.  
  166. -- Перепишите функцию thirdElementOfSecondList в thirdElementOfSecondList' используя
  167. -- только tryHead, tryTail, применение функций и оператор ~~>, но не используя
  168. -- сопоставление с образом (pattern matching) ни в каком виде, case, if, guards.
  169. thirdElementOfSecondList' :: [[a]] -> Maybe a
  170. thirdElementOfSecondList' xs = tryTail xs ~~> tryHead ~~> tryTail ~~> tryTail ~~> tryHead
  171. -- 3) Несколько упражнений
  172. -- Реализуйте функцию nubBy', которая принимает на вход функцию для сравнения
  173. -- элементов на эквивалентность и список элементов и возвращает список из тех же
  174. -- элементов без повторений. Гарантируется, что функция задаёт отношение
  175. -- эквивалентности. Важно сохранить порядок, в котором элементы встречались впервые.
  176. -- Запрещено использовать стандартные функции, которые решают эту задачу.
  177. --
  178. -- >>> nubBy' (==) []
  179. -- []
  180. -- >>> nubBy' (==) "abaacbad"
  181. -- "abcd"
  182. -- nubBy' (\x y -> x == y || x + y == 10) [2, 3, 5, 7, 8, 2]
  183. -- [2,3,5]
  184. nubBy' :: (a -> a -> Bool) -> [a] -> [a]
  185. nubBy' _ [] = []
  186. nubBy' eq (x:xs) = x: nubBy' eq (filter (not . eq x) xs)
  187.  
  188. -- Реализуйте функцию quickSort, которая принимает на вход список, и
  189. -- возвращает список, в котором элементы отсортированы при помощи алгоритма
  190. -- быстрой сортировки.
  191. -- Рандом или быстрый partition использовать не нужно, выберите максимально
  192. -- простую реализацию.
  193. --
  194. -- Требование Ord a => означает, что для типа a можно использовать знаки
  195. -- сравнения (>, <, == и т.д.).
  196. --
  197. -- >>> [x + 1 | x <- [1..10], x > 5]
  198. -- [7,8,9,10,11]
  199. -- >>> quickSort' []
  200. -- []
  201. -- >>> quickSort' [2, 3, 1, 2]
  202. -- [1,2,2,3]
  203. -- >>> quickSort' "babca"
  204. -- "aabbc"
  205. quickSort' :: Ord a => [a] -> [a]
  206. quickSort' [] = []
  207. quickSort' (x:xs) = quickSort' [y | y <- xs, y < x] ++ [x] ++ quickSort' [y | y <- xs, y >= x]
  208.  
  209. -- Найдите суммарную длину списков, в которых чётное количество элементов
  210. -- имеют квадрат больше 100. Реализация должна быть без использования
  211. -- list comprehension, лямбда-функций, вспомогательных функций или явного
  212. -- упоминания параметра weird': только композиция, частичное применение
  213. -- функций и операторов.
  214. --
  215. -- >>> weird' []
  216. -- 0
  217. -- >>> weird' [[1, 2, 3], [4, 5], [1, 2, 11]]
  218. -- 5
  219. -- >>> weird' [[1, 11, 12], [9, 10, 20]]
  220. -- 3
  221. weird':: [[Int]] -> Int
  222. weird' = sum' . map' length . filter (even . length . filter ((>100) . (^2)))
  223.  
  224.  
  225. -- 4) grep
  226. -- Нужно реализовать несколько вариаций grep'а.
  227. -- Вместо файлов на вход будет подаваться список из структур File,
  228. -- содержащих в себе имя файла и его содержимое (список строк).
  229. -- (Можно считать, что File -- это typedef для кортежа из строки и списка строк).
  230. type File = (String, [String])
  231.  
  232. -- Функция grep' принимает на вход:
  233. -- * Функцию match :: String -> Bool, которая возвращает True,
  234. --   если параметр-строчка файла является искомым
  235. --   (например, содержит подстроку для поиска).
  236. -- * Функцию format :: String -> [String] -> [String], которая
  237. --   по имени файла и списку найденных искомых строк в нём
  238. --   возвращает список строк для вывода на экран.
  239. -- * Список файлов files :: [File].
  240. -- Функция grep' должна вернуть список строк для вывода на экран
  241. -- после поиска искомых строк во всех файлах.
  242. --
  243. -- >>> grep' (\_ s -> s) ((== 'a') . head) [("a.txt", ["ab", "b"]), ("b.txt", ["b", "ac"])]
  244. -- ["ab", "ac"]
  245. --
  246. -- Здесь (\_ s -> s) --- это лямбда-функция, которая игнорирует первый
  247. -- параметр и возвращает второй.
  248. grep' :: (String -> [String] -> [String]) -> (String -> Bool) -> [File] -> [String]
  249. grep' format match files = undefined
  250.  
  251. -- Также вам предоставлена функция для проверки вхождения подстроки в строку.
  252. -- >>> isSubstringOf "a" "bac"
  253. -- True
  254. -- >>> isSubstringOf "ac" "bac"
  255. -- True
  256. -- >>> isSubstringOf "ab" "bac"
  257. -- False
  258. isSubstringOf :: String -> String -> Bool
  259. isSubstringOf n s = pack n `isInfixOf` pack s
  260.  
  261. -- При помощи функций выше реализуйте несколько вариантов grep.
  262. --
  263. -- Вариант, когда ищется подстрока и нужно просто вернуть список подходящих
  264. -- строк.
  265. -- >>> grepSubstringNoFilename "b" [("a.txt", ["a", "b"])]
  266. -- ["b"]
  267. -- >>> grepSubstringNoFilename "c" [("a.txt", ["a", "a"]), ("b.txt", ["b", "bab", "c"]), ("c.txt", ["c", "ccccc"])]
  268. -- ["c", "c", "ccccc"]
  269. grepSubstringNoFilename :: String -> [File] -> [String]
  270. grepSubstringNoFilename needle files = undefined
  271.  
  272. -- Вариант, когда ищется точное совпадение и нужно ко всем подходящим строкам
  273. -- дописать имя файла через ":".
  274. --
  275. -- >>> grepExactMatchWithFilename "b" [("a.txt", ["a", "b"])]
  276. -- ["a.txt:b"]
  277. -- >>> grepExactMatchWithFilename "c" [("a.txt", ["a", "a"]), ("b.txt", ["b", "bab", "c"]), ("c.txt", ["c", "ccccc"])]
  278. -- ["b.txt:c", "c.txt:c"]
  279. grepExactMatchWithFilename :: String -> [File] -> [String]
  280. grepExactMatchWithFilename needle files = undefined
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top