HOMEWORK #1 : Task 1, Task 2, Task 3, Task 4, Task 5, Task 6, Task 7

Лабораторная работа
в среде программирования Haskell



Если Вы считаете, что данная страница каким-либо образом нарушает Ваши авторские права, то Вам следует обратиться в администрацию нашего сайта по адресу info@kursovik.com либо через форму обратной связи

Среда программирования: Haskell

Название работы: HOMEWORK #1 : Task 1, Task 2, Task 3, Task 4, Task 5, Task 6, Task 7

Вид работы: Лабораторная работа

Описание: HOMEWORK #1

Task 1
1. Create a module named HW1.T1 and define the following data type in it:
data Day = Monday | Tuesday | ... | Sunday
(Obviously, fill in the ... with the rest of the week days).
2. Implement the following functions:
-- | Returns the day that follows the day of the week given as input.
nextDay :: Day -> Day
-- | Returns the day of the week after a given number of days has passed.
afterDays :: Natural -> Day -> Day
-- | Checks if the day is on the weekend.
isWeekend :: Day -> Bool
-- | Computes the number of days until the next Friday.
daysToParty :: Day -> Natural

Task 2
1. Create a module named HW1.T2 and define the following data type in it:
data N = Z | S N
2. Implement the following operations:
nplus :: N -> N -> N -- addition
nmult :: N -> N -> N -- multiplication
nsub :: N -> N -> Maybe N -- subtraction (Nothing if result is negative)
ncmp :: N -> N -> Ordering -- comparison (Do not derive Ord)
nFromNatural :: Natural -> N
nToNum :: Num a => N -> a
3. (Advanced) Implement the following operations:
nEven, nOdd :: N -> Bool -- parity checking
ndiv :: N -> N -> N -- integer division
nmod :: N -> N -> N -- modulo operation

Task 3
1. Create a module named HW1.T3 and define the following data type in it:
data Tree a = Leaf | Branch !Int (Tree a) a (Tree a)
Functions operating on this tree must maintain the following invariants:
1. Sorted: The elements in the left subtree are less than the head element of a
branch, and the elements in the right subtree are greater.
2. Unique: There are no duplicate elements in the tree (follows from Sorted).
3. CachedSize: The Int field stores the size of the tree.
4. (Advanced) Balanced: For any given Branch _ l _ r, the ratio between the
size of l and the size of r never exceeds 3.
These invariants enable efficient processing of the tree.
2. Implement the following functions:
-- | Size of the tree, O(1).
tsize :: Tree a -> Int
-- | Depth of the tree, O(log n).
tdepth :: Tree a -> Int
-- | Check if the element is in the tree, O(log n)
tmember :: Ord a => a -> Tree a -> Bool
-- | Insert an element into the tree, O(log n)
tinsert :: Ord a => a -> Tree a -> Tree a
-- | Build a tree from a list, O(n log n)
tFromList :: Ord a => [a] -> Tree a
Tip 1: in order to maintain the CachedSize invariant, define a helper function:
mkBranch :: Tree a -> a -> Tree a -> Tree a
Tip 2: the Balanced invariant is the hardest to maintain, so implement it last. Search
for “tree rotation”.

Task 4
1. Create a module named HW1.T4.
2. Using the Tree data type from HW1.T3, define the following function:
tfoldr :: (a -> b -> b) -> b -> Tree a -> b
It must collect the elements in order:
treeToList :: Tree a -> [a] -- output list is sorted
treeToList = tfoldr (:) []
This follows from the Sorted invariant.
You are encouraged to define tfoldr in an efficient manner, doing only a single pass
over the tree and without constructing intermediate lists.

Task 5
1. Create a module named HW1.T5.
2. Implement the following function:
splitOn :: Eq a => a -> [a] -> NonEmpty [a]
Conceptually, it splits a list into sublists by a separator:
ghci> splitOn '/' "path/to/file"
["path", "to", "file"]
ghci> splitOn '/' "path/with/trailing/slash/"
["path", "with", "trailing", "slash", ""]
Due to the use of NonEmpty to enforce that there is at least one sublist in the output, the
actual GHCi result will look slightly differently:
ghci> splitOn '/' "path/to/file"
"path" :| ["to","file"]
Do not let that confuse you. The first element is not in any way special.
3. Implement the following function:
joinWith :: a -> NonEmpty [a] -> [a]
It must be the inverse of splitOn, so that:
(joinWith sep . splitOn sep) ≡ id
Example usage:
ghci> "import " ++ joinWith '.' ("Data" :| "List" : "NonEmpty" : [])
"import Data.List.NonEmpty"

Task 6
1. Create a module named HW1.T6.
2. Using Foldable methods, implement the following function:
mcat :: Monoid a => [Maybe a] -> a
Example usage:
ghci> mcat [Just "mo", Nothing, Nothing, Just "no", Just "id"]
"monoid"
ghci> Data.Monoid.getSum $ mcat [Nothing, Just 2, Nothing, Just 40]
42
3. Using Foldable methods, implement the following function:
epart :: (Monoid a, Monoid b) => [Either a b] -> (a, b)
Example usage:
ghci> epart [Left (Sum 3), Right [1,2,3], Left (Sum 5), Right [4,5]]
(Sum {getSum = 8},[1,2,3,4,5])

Task 7
1. Create a module named HW1.T7.
2. Define the following data type and a lawful Semigroup instance for it:
data ListPlus a = a :+ ListPlus a | Last a
infixr 5 :+
3. Define the following data type and a lawful Semigroup instance for it:
data Inclusive a b = This a | That b | Both a b
4. Define the following data type:
newtype DotString = DS String
Implement a Semigroup instance for it, such that the strings are concatenated with a
dot:
ghci> DS "person" <> DS "address" <> DS "city"
DS "person.address.city"
Implement a Monoid instance for it. Make sure that the laws hold:
mempty <> a &#8801; a
a <> mempty &#8801; a
5. Define the following data type:
newtype Fun a = F (a -> a)
Implement lawful Semigroup and Monoid instances for it

Год: 2021

Данный заказ (лабораторная работа) выполнялся нашим сайтом в 2021-м году, в рамках этого заказа была разработана программа в среде программирования Haskell. Если у Вас похожее задание на программу, которую нужно написать на Haskell, либо на другом языке программирования, пожалуйста заполните форму, приведённую ниже, после чего Ваше задание в первую очередь рассмотрит наш программист, выполнявший в 2021-м году этот заказ, если он откажется, то Ваше задание оценят другие наши программисты в течение 48-и часов, если оценка нужна срочно, просим Вас оставить пометку об этом - напишите в тексте задания фразу "СРОЧНЫЙ ЗАКАЗ".

Купить эту работу

Тел.: +79374242235
Viber: +79374242235
Telegram: kursovikcom
ВКонтакте: kursovikcom
WhatsApp +79374242235
E-mail: info@kursovik.com
Skype: kursovik.com