7 небольших задач Haskell
Ниже приведено само задание. Срок до воскресенья(26.09.2021)
{-# LANGUAGE FlexibleContexts #-}
import Data.Semigroup ( Max, Min, Endo(Endo, appEndo) )
import Data.Monoid
import Control.Monad.Writer
-- 1. Prelude говорит, то значением выражения div x y для целых x и y
-- является частное x и y, округленное вниз (то есть к минус бесконечности).
-- Однако выражение
-- -7 `div` 3
-- возвращает -2, а не -3, как можно было ожидать. Объясните подробно,
-- почему так получается и как можно получить правильный результат
-- целочисленного деления -7 на 3.
-- Указание. Можно пользоваться командой :i интерпретатора GHCi,
-- печатающей информацию о введенных именах. Полезная информация также
-- содержится в Prelude и разделах 3.4 и 4.4.2 Haskell 2010 Language
-- Report.
-- 2. Следующая задача была предложена на контрольной в середине
-- весеннего семестра, однако все решения были излишне сложными.
-- Без использования рекурсии напишите функцию abbrev :: [String] -> String,
-- которая в заданном списке имен людей выполняет сокращение всех
-- имен, кроме фамилии, до инициалов. Фамилией считается последнее
-- слово. Например:
-- > putStrLn $ abbrev ["Синицин"]
-- "Синицин"
-- > putStrLn $ abbrev ["Сергей", "Есенин"]
-- "С.Есенин"
-- putStrLn $ abbrev ["Игорь", "Федорович", "Поддубный"]
-- "И.Ф.Поддубный"
-- putStrLn $ abbrev ["Иоганн", "Хризостом", "Вольфганг", "Амадей", "Моцарт"]
-- "И.Х.В.А.Моцарт"
-- Решение должно удовлетворять следующим условиям.
-- (а) Оно должно состоять из одной строчки, не считая объявления типа.
-- (б) Следует использовать правую свертку для непустых списков.
-- (в) Функция должна иметь временную сложность O(n), где n — длина
-- списка, но не общая длина слов в списке.
-- (г) Не следует использовать функцию (++) там, где можно обойтись
-- более простыми функциями.
abbrev :: [String] -> String
abbrev = undefined
-- 3. Напишите рекурсивную функцию
-- foldMapList :: Monoid m => (a -> m) -> [a] -> m
-- которая может использоваться для объявления членства типа списков
-- в классе Foldable.
-- 4. В Prelude функции foldr определена через foldMap следующим образом.
-- foldr f z t = appEndo (foldMap (Endo . f) t) z
-- С учетом вашего ответа на предыдущий вопрос объясните, как работает
-- это определение, если t — список, и почему оно эквивалентно
-- обычному определению из лекции 5.
--foldr f z [] = z
--foldr f z (x:xs) = f x (foldr f z xs)
-- 5. Рассмотрим следующие определения.
l :: [String]
l = ["ab", "cd", "ef"]
f1 :: [String] -> String -> String
f1 = mconcat . map showString
f2 :: [String] -> String -> String
f2 = appEndo . mconcat . map (Endo . showString)
-- Объясните, что возвращают f1 и f2, в чем между ними разница и какова ее причина.
-- Указание. Определение моноидных операций на различных типах, в том
-- числе на типе функций (a -> b) и типе эндоморфизмов (Endo a),
-- находятся в модуле Data.Semigroup.
-- 6. Напишите функцию
minMax :: [Int] -> (Int, Int)
minMax = undefined
-- которая возвращает пару, состоящую из минимального и максимального
-- элементов непустого списка. Она должна использовать следующую
-- рекурсивную функцию, которая выполняет основную работу.
minMaxLoop :: [Int] -> Writer (Min Int, Max Int) ()
minMaxLoop = undefined
-- Определения типов Min a и Max a, являющихся моноидами с операциями
-- min и max, соответственно, находятся в модулях Data.Semigroup и
-- Data.Monoid. Они аналогичны моноидам Sum a и Product a,
-- рассмотренным на лекциях.
-- Функция minMaxLoop не должна явно использовать операторы сравнения, а также
-- функции min, max, minimum и maximum. В определении minMax можно использовать
-- функцию execWriter, определенную в Control.Monad.Writer.
-- 7. Подставьте определения функций flip и (.) из Prelude в терм
-- flip (.) и, выполняя по одной редукции за шаг, найдите нормальную
-- форму этого терма.
