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 (.) и, выполняя по одной редукции за шаг, найдите нормальную

-- форму этого терма.