Написать функцию cat n, вычисляющую n-ое число Каталана по рекуррентной формуле (формулу можно выбрать любую, но должно считаться C_50 например без проблем).
Для решения я использую формулу с Википедии:
Написать функцию, соединяющую конечное (n) количество списков, которые могут быть бесконечными так, чтобы для любого n и любого k нашлось m такое, чтобы для списка ls вызов take m ls вывел результат, в котором было бы хотя бы по k элементов из каждого списка. Иными словами, объединить списки так, чтобы можно было просматривать каждый из списков в объединённом.
Будем брать первый элемент каждого списка и последовательно добавлять в список-ответ, после чего, будем удалять этот элемент из исходного списка и повторять операцию, пока не опустошим все списки. При этом не забываем после каждой итерации чистить пустые списки.
Рассмотрим граф, задаваемый следующим образом (списками смежности):
type Graph = [(Int, [Int])] . Вершины пронумерованы от 1 до n. В каждом кортеже в списке выше указан номер вершины и список номеров вершин, у которых с ней общее ребро.
а) Проверить, корректно ли заданное описание графа (имеется в виду, что граф неориентированный)
б) Проверить, состоит ли граф (корректно заданный) из одной компоненты связности
а) Для каждой вершины графа A для каждого его ребра, ведущего в вершину B попытаемся найти парное ребро из B в A. Если у каждого ребра есть пара - граф задан верно, иначе неверно.
б) Запустим bfs из вершины 1 и посчитаем количество вершин, которые мы посетим. Если количество посещенных вершин равно количесту вершин графа, то компонента связности одна.
Получить бесконечный список знаков после запятой числа е. П.С. это никак не связано с аппроксимацией, примерными вычислениями, точностями и тому подобным. Результатом выполнения программы должен быть бесконечный список в хаскелевской терминологии!
Воспользуемся рядом Тейлора для экспоненты
В нашем случае x = 1.
Создадим бесконечный список, в котором будем хранить сумму ряда до i-ого элемента. Обращаясь к элементам этого списка, можно получить i-ую цифру после запятой числа e. Для того, чтобы избежать погрешность, так как сумма ряда, например, для 2 элементов не сможет соответствовать 2-ой цифре после запятой. Начнем считать ряд с какой-то начальной суммы. Я выбрал сумму до 10-ого элемента.
Итого, для вычисления i + 1-ой цифры числа e будет вычисляться сумма ряда для i + 11-ого элемента и из нее будет браться необходимая цифра.
Описать тип данных Board, который представляет двумерную доску, в которой каждая клетка может быть чёрной или белой (для простоты доска всегда будет 4*4, в описании типа эти числа не нужны). Пример заданной доски [[True, True, False, True], [False, True, True, False], [True, True, False, True], [False, True, True, False]]. Нужно реализовать класс Show для Board так, чтобы вывод show x состоял из символов █ и ░ и в данном примере был таким:
██░█
░██░
██░█
░██░
P.S. Большинство, вероятно, не работало с FlexibleInstances и т.д., так что вы столкнётесь с невозможностью реализовать класс для Type. Чтобы это обойти, оберните этот Type в Data с единственным значением.
"repl.it" почему-то не дает мне использовать utf-8. Вместо данных символов печатаются вопросики. Если пытаюсь заимпортить Data.ByteString.UTF8, код не комплируется с ошибкой: "Could not find module Data.ByteString.UTF8". Я узнал, что поумолчанию в консоли "repl.it" стоит ASCII. Поэтому заменил символы на + и -.
- Найдите все β- и δ-редексы в заданном выражении и укажите самые внешние и самые внутренние.
(λh.(λx.h (x x))(λx.h (x x)))((λy.y)(+ 1 5)) - Для выражения из предыдущего задания выполните редукцию выражения до НФ и СЗНФ в аппликативном и нормальном порядках
- Определите для чистого лямбда-исчисления логическую функцию
XOR(исключающее ИЛИ). - В чистом лямбда-исчислении определите функцию вычисления длины заданного списка
- самый внутренний:
(+ 1 5)
(λy.y)(+ 1 5)- самый внутренний:
(λx.h (x x))(λx.h (x x)) - самый внешний:
(λh.(λx.h (x x))(λx.h (x x)))((λy.y)(+ 1 5))
(λh.(λx.h (x x))(λx.h (x x)))((λy.y)(+ 1 5))
(λh.h ((λx.h (x x)) (λx.h (x x))))((λy.y)(+ 1 5))
(λh.h (h ((λx.h (x x)) (λx.h (x x)))))((λy.y)(+ 1 5)) и т.д.
Делаем вывод, что этим способом привести к СЗНФ и НФ не представляется возможным.
(λh.(λx.h (x x))(λx.h (x x)))((λy.y)(+ 1 5))
(λx.((λy.y)(+ 1 5)) (x x))(λx.((λy.y)(+ 1 5)) (x x))
((λy.y)(+ 1 5)) ((λx.((λy.y)(+ 1 5)) (x x)) (λx.((λy.y)(+ 1 5)) (x x)))
(+ 1 5) ((λx.((λy.y)(+ 1 5)) (x x)) (λx.((λy.y)(+ 1 5)) (x x)))
6 ((λx.((λy.y)(+ 1 5)) (x x)) (λx.((λy.y)(+ 1 5)) (x x)))
(λh.(λx.h (x x))(λx.h (x x))) - Y комбинатор неподвижной точки, тогда, используя нормальный порядок, также нельзя привести к СЗНФ или НФ.
False = λx.λy.y
True = λx.λy.x
xor = λx.λy.x (y (λx.λy.y) (λx.λy.x)) y
(λx.λy.x (y (λx.λy.y) (λx.λy.x)) y) (λx.λy.x) (λx.λy.y)
(λx.λy.x) ((λx.λy.y) (λx.λy.y) (λx.λy.x)) (λx.λy.y)
(λx.λy.y) (λx.λy.y) (λx.λy.x)
(λx.λy.x) = True
(λx.λy.y) ((λx.λy.x) (λx.λy.y) (λx.λy.x)) (λx.λy.x)
(λx.λy.x) = True
(λx.λy.x) ((λx.λy.x) (λx.λy.y) (λx.λy.x)) (λx.λy.x)
(λx.λy.x) (λx.λy.y) (λx.λy.x)
(λx.λy.y) = False
(λx.λy.y) ((λx.λy.y) (λx.λy.y) (λx.λy.x)) (λx.λy.y)
(λx.λy.y) = False
Непустой лист: λs.s h t
Пустой лист: nil = λx.True
suc = λn.λf.λx.f (n f x)
tail = λx.x False
length = Y (λxλyλz. nil z y (x (suc y) (tail z))) 0
Рассматриваем упрощённый eval/apply-интерпретатор:
data Expr =
Integral Integer | -- целые константы
Function String | -- идентификаторы примитивных функций
Variable String | -- переменная
Lambda String Expr | -- лямбда-выражение
Application Expr Expr -- применение функцииТо есть в нём нет boolean-ов и блоков (let, letrec). Задание - написать функцию, которая по заданному выражению выдаёт список имён всех встроенных (константных) функций, встречающихся в нём.
Раскрываем Expr:
Integral Integer=[]Function String=StringVariable String=[]Lambda String Expr= РаскрытиюExprApplication Expr Expr= РаскрытиюExpr1 соединеммым с раскрытиемExpr2
После исключим дупликаты и получим список искомых функций.
Нужно реализовать несложную арифметическую систему для работы с многочленами. Что должно быть в вашей программе:
- тип данных для одночлена (одночлен представляется коэффициентом из любого множества, которое вам нравится, но является полем, и переменными A, B, C, D, E, F)
- тип данных для многочлена
- функции сложения и умножения одночленов
- функции сложения и умножения многочленов
- операции упрощения данных типов (одночлен
4 * A^2 * A^4упрощается до4 * A^6. многочлен упрощается путём приведения подобных слагаемых) - реализация show для одночленов и многочленов (должно приводится в адекватный читаемый вид типа
4 * A^3 * B^4 - 8 * C^5 * F) - для одночлена или многочлена x должна быть возможность написать в коде программы например
x ^ 3. для этого необходимо реализовать классNum
Класс для хранения названия переменной и степени, в которою возведена эта переменная.
data VarPow = VarPow {
getVariable :: Char,
getPower :: Integer
}Класс для одночлена. Хранит константу и список пар (Переменная, степень)
data Monomial = Monomial {
constant :: Integer,
variables :: [VarPow]
}Функция упрощения одночлена. Складывает все степени одинаковых перменных и кладет в новый список
simplify :: Monomial -> Monomial
simplify monomial = Monomial (constant monomial) (simplify2 [] (variables monomial)) where
simplify2 :: [VarPow] -> [VarPow] -> [VarPow]
simplify2 stack [] = stack
simplify2 stack (current:list) = simplify2 (if contains (getVariable current) stack then stack else stack ++ [combine (getVariable current) (getPower current) list]) listВспомогательная функция, проверяет содержится ли пара с искомой переменной в списке пар (Переменная, степень)
contains :: Char -> [VarPow] -> Bool
contains variable [] = False
contains variable (current:list) = if variable == (getVariable current) then True else contains variable listВспомогательная функция, собирает складывает все степени из списка пар с одинаковыми переменными и возвращает пару (переменная, сумма степеней)
combine :: Char -> Integer -> [VarPow] -> VarPow
combine variable power [] = VarPow variable power
combine variable power (current:list) = combine variable (power + if variable == (getVariable current) then (getPower current) else 0) listВспомогательная функция, проверяет одночлены на равнество, одночлены должны быть заранее упрощены
simplifiedEquals :: Monomial -> Monomial -> Bool
simplifiedEquals (Monomial c1 vp1) (Monomial c2 vp2) = (c1 == c2) && (varPowListEquals vp1 vp2)Вспомогательная функция. Проверяет списки пар (Переменная, степень) на то, что они содержат одни и те же пары.
varPowListEquals :: [VarPow] -> [VarPow] -> Bool
varPowListEquals vp1 vp2 = (all (\vp -> elem vp vp2) vp1) && (all (\vp -> elem vp vp1) vp2)Функция для суммы двух одночленов. Сумма одночленов может быть многочленом, поэтому возвращается многочлен.
sumMonomial :: Monomial -> Monomial -> Polynomial
sumMonomial m1 m2 = (Polynomial [m1]) + (Polynomial [m2])Функция для упрощения многочлена. Идея алгоритма такая же, как в упрощении одночлена
simplifyPolynomial :: Polynomial -> Polynomial
simplifyPolynomial (Polynomial p) = simplify2 [] (map simplify p)
where simplify2 :: [Monomial] -> [Monomial] -> Polynomial
simplify2 stack [] = Polynomial stack
simplify2 stack (current:list) = simplify2 (if containsMonomial current stack then stack else stack ++ [combineMonomials current list]) listВспомогательная функция. Проверяет, содержится ли одночлен в списке одночленов, игнорируя множитель(Проверка на подобие).
containsMonomial :: Monomial -> [Monomial] -> Bool
containsMonomial m [] = False
containsMonomial m (current:list) = if varPowListEquals (variables m) (variables current) then True else containsMonomial m listВспомогательная функция. Складывает подобные одночлены внутри списка одночленов.
combineMonomials :: Monomial -> [Monomial] -> Monomial
combineMonomials m [] = m
combineMonomials m (current:list) = combineMonomials (Monomial (if varPowListEquals (variables m) (variables current) then (constant m) + (constant current) else (constant m)) (variables m)) list