Задание на лабораторную работу 3.
1. Используя функции а) any и б) all, проверьте условия в интерпретаторе. Запишите функции в файле, решающие те же задачи, используя частичное применение функции.
2. Запишите функцию, решающую задачу
а) обычную рекурсивную функцию;
б) функцию с использованием функции map;
в) функцию с использованием функции map и лямбда-фнкциии.
Приветствуется частичное применение функций в пунктах б) и/или в).
3. Запишите функции, решающие задачи с использованием
а) функции filter;
б) функций filter, zip, unzip;
в) функций takeWhile, dropWhile, break, span, splitAt
4. Для заданного отображения Р найти
5.Проверить указанное свойство операций над указанным множеством. Входные аргументы функции должны быть списком функций или списком кортежей функций и содержать необходимое число входных аргументов из множества (см. в таблице пример).
6. Отсортировать список кортежей двух целочисленных элементов по указанному признаку.
7. Дан список предикатов двух переменных:
Р1(х,у)=”x+y – четное число”,
P2 (х,у)=”x>y”,
P3 (х,у)=”x и y имеют одинаковые остатки от деления на 4”,
P4 (х,у)=”x+2y<8”,
P5 (х,у)=”max{x,y} – нечетное число”,
и список кортежей [(x,y)]. Написать функцию, имеющую аргументами эти два списка и решающую задачу.
Вариант 1.
1. а) в строке есть цифры,
б) все символы строки – прописные буквы.
|
|
2. Функция заменяет каждый элемент списка остатком его деления на 3.
3. а) удаляет из строки все элементы, кроме букв и цифр;
б) возвращает список индексов гласных букв в строке;
в) удаляет из строки все элементы, следующие за последней точкой
(«abc. 123. F5? 6» -> «abc. 123.»)
4.
5.
Множество | Свойство | Пример |
R | дистрибутивности справа | foo [(/,*),(*,+),(**,*),(**,+)] 2 3 4 -> [False,True,False,False] |
6. По сумме элементов.
|
|
7. Возвращает список логических значений выражения для каждого из предикатов.
Вариант 2.
1. а) в списке есть числа, кратные 6,
б) все числа в списке меньше 100
2. Функция заменяет список кортежей двух чисел списком их сумм.
3. а) удаляет из числового списка все кратные 6 элементы;
б) возвращает сумму индексов четных элементов списка;
в) возвращает кортеж двух строк – в первой все символы до первой прописной буквы, во второй – все оставшиеся символы исходной строки.
4.
5.
Множество | Свойство | Пример |
множеств | ассоциативности | foo [union, \\, intersect] [1..5] [3..6] [2..10] -> [True,False,True] |
6. По минимальному элементу.
7. Возвращает список логических значений выражения для каждого из предикатов.
Вариант 3.
1. а) в списке есть четные числа б) в списке нет чисел, превышающих 10
2. Функция возвращает список, в котором фиксируется сравнение каждого элемента с заданным числом (указание: можно использовать функцию compare)
3. а) функция удаляет из строки все цифры;
б) функция возвращает максимальный из индексов элементов числового списка, не превышающих 8;
в) считая, что в числовом списке все числа различны, получить кортеж двух списков – в первый входят элементы до минимального, во второй – после максимального элементов списка. ([5,6,2,1,4,3] -> ([5,6,2],[2,1,4,3]))
|
|
4.
5.
Множество | Свойство | Пример |
Целых чисел | Дистрибутивности слева | foo [(max,+),(+,max),(lcm,*)] 5 2 4 -> [False, False, True] |
6.По первому элементу.
7. Получить список кортежей, на котором истинны все предикаты.
Вариант 4.
1. а) в списке есть нечетные числа б) в списке нет чисел, кратных 15
2. Функция заменяет каждый символ строки предыдущим символом.
3. а) функция удаляет из целочисленного списка все элементы, кратные 5;
б) функция находит первый индекс вхождения в строки гласной буквы
в) функция возвращает из строки все символы до первой цифры
4.
5.
Множество | Свойство | Пример |
Целых чисел | Коммутативности | foo [+,div,*,lcm] 10 12 -> [True, False, True, True] |
|
|
6. По разности между первым и вторым элементами.
7. Возвращает список логических значений выражения для каждого из предикатов.
Вариант 5.
1. а) в строке есть символы - знаки пунктуации б) все гласные в строке - прописные
2. Функция из списка строк получает список двух последних символов каждой строки.
3. а) функция удаляет из строки все строчные буквы;
б) функция находит последний индекс четного элемента в числовом списке;
в) функция преобразует целочисленный список в список списков подряд идущих нечетных элементов. ([2,5,7,1,4,9,3,8] - >[[5,7,1],[9,3]])
4.
5.
Множество | Свойство | Пример |
N | дистрибутивности справа | foo [(+,*),(*,+),(*,^),(+,^)] 2 3 4 -> [True,False,True,False] |
6. По второму элементу.
7. Возвращает список логических значений выражения для каждого из предикатов.
.
Вариант 6.
1. а) в списке кортежей есть нечетные вторые элементы б) элементы кортежа в списке отличаются не более, чем на 2.
2. Функция удваивает нечетные элементы числового списка.
3. а) функция удаляет из строки все цифры;
б) функция подсчитывает количество элементов целочисленного списка, совпадающих со своими индексами;
в) функция преобразует список в кортеж двух списков – в первом списке количество элементов равно последнему элементу списка, во втором – все оставшиеся ([4,3,1,5,2] - > ([4,3],[1,5,2]))
4.
5.
Множество | Свойство | Пример |
R | foo [(sqrt,*),(sqrt,+),(sin,*)] 2 3 -> [True,False,False] |
6. По среднему арифметическому элементов.
7. Возвращает список кортежей, на которых истинен хотя бы один из пяти предикатов.
Вариант 7.
1. а) в списке символов есть знаки арифметических операций б) в списке символов нет заглавных латинских букв
2. Функция для заданного целочисленного списка составляет список остатков от деления на 5 элементов списка.
3. а) удаляет из строки все буквы;
б) находит сумму индексов элементов, кратных 3;
в) удаляет из списка все элементы, начиная с первого, встречавшегося ранее.
4.
5.
Множество | Свойство | Пример |
множеств | дистрибутивности справа | foo [(union,\\) , (intersect,union), (\\,union)] [1..5] [3..6] [2..10] -> [True,True,False] |
6. По разности между вторым и первым элементами.
7. Возвращает список логических значений выражения для каждого из предикатов.
Вариант 8.
1. а) в списке кортежей есть кортеж с равными элементами (первым и вторым) б) все вторые элементы в кортежах нечетные
2. Функция для заданного списка строк в каждой строке удаляет символы, начиная с k-го.
3. а) удаляет из списка кортежей двух чисел все кортежи с четной суммой;
б) находит все элементы, кратные своему индексу (считая с 1);
в) удаляет из строки все элементы до последнего вхождения цифры.
4.
5.
Множество | Свойство | Пример |
R | Дистрибутивности слева | foo [(log,+),(+,/),(/,*)] 5 2 4 -> [False, False, True] |
6. По минимальному элементу.
7. Возвращает список логических значений выражения для каждого из предикатов.
Вариант 9.
1. а) в строке есть гласные буквы, б) в строке нет цифр
2. Функция преобразует список кортежей двух чисел в список их сумм.
3. а) удаляет из списка все элементы, равные последнему;
б) преобразует числовой список в список, в котором четные элементы сложены со своими индексами ([1,2,3,4]->[2+1,4+3]->[3,7])
в) удаляет из строки все элементы до первой цифры и после последней.
4.
5.
Множество | Свойство | Пример |
R | ассоциативности | foo [logBase,/,+] 4 5 1 -> [False,False,True] |
6. По НОК элементов
7. Возвращает список вторых элементов кортежей из списка, на которых истинны все предикаты.
Вариант 10.
1. а) в списке есть числа кратные 4, б) все числа в списке четные.
2. Функция в заданной строке меняет каждую строчную букву на прописную и наоборот, другие символы не изменяет.
3. а) удаляет из списка все элементы, не кратные первому элементу;
б) находит в списке индекс первого вхождения минимального элемента;
в) удаляет из строки все элементы до первой прописной буквы.
4.
5.
Множество | Свойство | Пример |
множеств | Коммутативности | foo [//,union,intersect] [1,2] [1..5] -> [False, True, True] |
.
6. По НОД элементов.
7. Возвращает список первых элементов кортежей из списка, на которых истинен хотя бы 1 предикат.
Пример выполнения лабораторной работы 3.
1. Используя функции а) any и б) all, проверьте условия в интерпретаторе. Запишите функции в файле, решающие те же задачи, используя частичное применение функции.
а) в списке кортежей есть элементы с четными первыми элементами;
б) в списке кортежей сумма чисел каждого кортежа не превышает 10.
Решение.
Проверка в интерпретаторе:
а)
б)
Функции , использующие частичное применение:
Использование этих функций:
2. Запишите функцию, решающую задачу
а) обычную рекурсивную функцию;
б) функцию с использованием функции map;
в) функцию с использованием функции map и лямбда-функции.
Приветствуется частичное применение функций в пунктах б) и/или в).
Функция уменьшает четные элементы списка на 1, а нечетные удваивает
Решение.
а)
б)
в)
Использовано частичное применение функции.
Пример работы функций б) и в):
3. Запишите функции, решающие задачи с использованием
а) функции filter;
б) функций filter, zip, unzip;
в) функций takeWhile, dropWhile, break, span, splitAt
а) удаляет из строки все знаки пунктуации;
б) находит произведение индексов четных элементов, считая с 1;
в) возвращает кортеж двух списков, первый список содержит все элементы до первого четного, второй – элементы после последнего нечетного.
Решение.
а)
б)
Рассмотрим эту функцию подробнее. Сначала к исходному списку l «прицепим» список индексов с помощью функции zip. Например,
.
Затем с помощью функции filter оставим в списке кортежей только пары с четными первыми элементами:
.
Затем «расцепим» список кортежей на кортеж двух списков – в первом будут только элементы, во втором их индексы, с помощью функции unzip:
.
Из полученного кортежа берем только второй список – список индексов с помощью функции snd и находим произведение элементов этого списка с помощью функции product:
Пример работы функции:
в) Приведем код без подробных объяснений:
4. Для заданного отображения Р найти
((z,x),(x,x),(y,z),(x,y)).
Решение:
Напомним, как вычисляются данные выражения в дискретной математике:
Для нахождения обратного отображения используйте функцию map, для нахождения проекций композицию функции unzip с соответствующей кортежной функцией, для вычисления композиции и декартова произведения – генераторы списков.
Покажем только пример композиции . Вот математическое определение композиции отображений:
.
А вот наша функция на Haskell:
Не правда ли, очень компактно и изящно? Функция nub добавлена для отсечения повторяющихся элементов, так как мы работаем с множеством.
5. Проверить указанное свойство операций над указанным множеством. Входные аргументы функции должны быть списком функций или списком кортежей функций и содержать необходимое число входных аргументов из множества (см. в таблице пример).
Множество | Свойство | Пример |
N | ассоциативности | foo [(+),(*),(/)] 4 5 1 -> [True, True, False] |
Решение .
Код функции:
Пример вызова:
6. Отсортировать список кортежей двух целочисленных элементов по указанному признаку.
По абсолютному значению разности элементов.
Решение:
Как было написано выше, в этом случае необходимо использовать функцию sortBy из модуля List, написав самостоятельно функцию сравнения элементов. Стандартная функция sort использует для сравнения элементов функцию compare с результатом LT (less than), GT (greater than) и EQ (equal). Напишем функцию сравнения также с использованием compare, и укажем её как аргумент нашей функции:
Пример выполнения:
7. Дан список предикатов двух переменных:
Р1(х,у)=”x+y – четное число”,
P2 (х,у)=”x>y”,
P3 (х,у)=”x и y имеют одинаковые остатки от деления на 4”,
P4 (х,у)=”x+2y<8”,
P5 (х,у)=”max{x,y} – нечетное число”,
и список кортежей [(x,y)]. Написать функцию, имеющую аргументами эти два списка и решающую задачу.
Возвращает список логических значений выражения для каждого из предикатов.
Решение.
Сначала решим задачу в терминах алгебры предикатов. - означает, что найдется такой х, что при любом y предикат будет истинным. В нашем случае x – элементы из множества первых элементов кортежа, а у – вторых. То есть, например, для списка кортежей L=[(1,3),(2,4),(4,3),(1,4),(4,4)] множество
X={1,2,4}, а множество Y={3,4}. Для вычисления выражения необходимо найти (пример для списка L):
P(1,3)&P(1,4) | (проверяем, может для x=1 при всех y P истинно )
P(2,4) | (или для х=2)
P(4,3)&P(4,4) | (или для х=4).
Перейдем к решению задачи на Haskell. Безусловно, существует много способов решения. Предлагаю следующий, для лучшего усвоения я буду писать маленькие функции, решающие отдельные задачи (при желании потом можно все свернуть в одну функцию) :
1) список кортежей отсортировать по первым элементам. Это можно сделать с помощью встроенной функции sort (не забываем подключить модуль List).
2) теперь я попытаюсь разбить список на несколько списков с совпадающими первыми элементами, вторыми и т.д. То есть из списка
[(1,3),(2,4),(4,3),(1,4),(4,4)] я хочу получить список
[[(1,3),(1,4)],
[(2,4)],
[(4,3),(4,4)]
(переход на новую строку просто для удобства восприятия)
Имеется встроенная функция group, которая делит список на список списков по совпадающим подряд идущим элементам. Но нам необходимо работать с кортежами. Поэтому я пишу собственную функцию сравнения кортежей по первому элементу:
myEq (x,_) (y,_) = x==y
и использую теперь эту функцию во встроенной функции groupBy
mygroup l = groupBy (myEq) l
Пишем функцию foo1, которая сортирует и разбивает список по первым элементам кортежей:
foo1 l = mygroup (sort l)
(сортировка нужна, чтобы «собрать рядом» элементы с одинаковыми первыми элементами кортежей). Проверяем работу функции:
3) Теперь нам полученный список списков надо преобразовать в список булевских значений, применив предикат. Пусть сначала будем получать значение для предиката 1. Определим его:
p1 (x,y) = even (x+y)
Теперь определим функцию, которая применяет этот предикат к одному простому списку кортежей:
foo2 l = map p1 l
Но у нас список списков, нам надо к каждому элементу (списку) применить поочередно функцию foo2. Пишем функцию foo3:
foo3 l = map foo2 (foo1 l)
Вторым аргументом здесь, естественно, полученный нами ранее список списков. Проверяем работу функции:
4) Теперь для каждого из списков надо найти их конъюнкцию. Можно использовать встроенную функцию and в следующей функции foo4:
foo4 l = map (and) (foo3 l)
Проверяем работу функции:
5) Найдем теперь дизъюнкцию полученного списка булевских значений. Можно использовать встроенную функцию or, а можно еще вот так:
foo5 l = foldr (||) False (foo4 l)
Проверяем работу функции:
6) Итак, мы научились вычислять выражение для предиката
Р1(х,у)=”x+y – четное число”. Осталось определить оставшиеся предикаты и вычислить для каждого из них. Предлагаем решить эту уже несложную задачу самостоятельно:)
Лабораторная работа 4.
Дата добавления: 2019-03-09; просмотров: 802; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!