close

Вход

Забыли?

вход по аккаунту

?

ООП-26.(Haskell).Списки и функции

код для вставкиСкачать
Лекция
СПИСКИ И ФУНКЦИИ
1
Кортежи
Объявить функцию sum (x, y) все же можно:
sum (x, y) = x + y
Eё тип будет sum:: (Int, Int)->Int, т.е. аргументом такой функции будет кортеж.
Аналог кортежа в C++ - это struct, кроме того, кортежи знакомы нам по Питону.
В С# 4 также появились классы Tuple<T1, T2, T3,…> - кортежи.
Пример. Объявить функцию, которая получает трехэлементный кортеж и
возвращает кортеж с обратным порядком элементов.
invert (x, y, z) = (z, y, x)
2
Списки
Список похож на кортеж, но если кортежи (1, 2) и (1, 2, 3) это данные разных типов,
то списки [1,2] и [1,2,3] имеют один и тот же тип: [Int].
Кортеж: (1, 2) :: (Int, Int)
Список: [1, 2] :: [Int]
Этим объясняются различные роли, которые играют кортежи и списки в
функциональных программах (как различны роли структур и массивов в C#).
3
Конструкторы списков
Пустой список обозначается [ ].
Оператор «:» конструирует список из элемента и другого списка.
1:[2,3] -- то же что [1,2,3]
1:2:3:[] -- то же что [1,2,3]
Еще один конструктор списков создает арифметические прогрессии.
[1..10]
[0, 5..100]
[0, 5..]
Наиболее общий конструктор списков выглядит так: [ x | x <- исходный список, фильтр по x ]
-- все четные числа из списка [3, 5, 6, 2, 8]
[ x | x <- [3, 5, 6, 2, 8], mod x 2 == 0 ]
-- список пар, составленных их элементов двух списков
[ (x,y) | x <- [1, 2, 3], y <- [10, 20, 30]]
4
Функции для списков
head (h:t) = h
tail (h:t) = t
length s = количество элементов списка s
Для соединения списков служит оператор ++.
5
Строки
Строковые значения задаются в двойных кавычках. Они принадлежат к типу
String.
В Хаскеле строки – это списки символов, поэтому названия типов String и [Char] –
синонимы.
type String = [Char]
Слово type специально предназначено для объявления синонимов типов.
6
Преобразование в строку и обратно
Строки необходимы для вывода любых значений на экран.
Для преобразования других типов в строку служит функция show, а для
обратного преобразования – функция read.
Пример. Вывести значения координат на плоскости.
demo:: Int->Int->String
demo x y = "x = " ++ (show x) ++ "
y = " ++ (show y)
7
Сопоставление с образцом
head (h:t) = h
В определениях функций можно использовать не только имена, но и "образцы".
Образцы должны иметь форму конструкторов соответствующих типов данных.
Пример. Просуммировать список.
sumLst:: [Int]->Int
sumLst [] = 0
sumLst (x:xs) = x + sumLst xs
8
Пример. Длина списка
len [] = 0
len (x:xs) = 1 + len xs
Когда происходит сопоставление с образцом, упомянутые в нем параметры
получают значения. Если эти значения не нужны, вместо имен параметров
используют символ '_'.
len [] = 0
len (_:xs) = 1 + len xs
С учетом этого функции head и tail можно исправить.
head (x:_) = x
tail(_:xs) = xs
9
let-связывание
При определении функций часто бывает удобно использовать некоторые
промежуточные значения. Им можно давать имена при помощи конструкции let.
Решение без связывания
roots a b c = ((-b + sqrt (b*b - 4*a*c)) / (2*a),
(-b - sqrt (b*b - 4*a*c)) / (2*a))
Решение со связыванием
roots a b c = let d = sqrt (b*b - 4*a*c)
a2 = a * 2
in ((-b + d) / a2, (-b - d) / a2)
10
where-связывание
Конструкция let вводит определения до их использования, конструкция where –
после.
Решение квадратного уравнения с конструкцией where:
roots a b c = ( (-b + d)/a2, (-b - d)/a2)
where d = sqrt (b*b-4*a*c)
a2 = a*2
В конструкциях let и where можно определять не только локальные константы,
но и функции. Локальная функция имеет доступ к другим локальным именам
функции-хозяйки.
11
Охраняющие выражения
Охраняющие выражения могут накладывать на аргумент более общие
ограничения, чем образцы.
Расширим определение факториала, пусть при отрицательных значениях
аргумента он будет равен -1.
factorial 0
= 1
factorial n | n < 0
= -999
| otherwise = n * factorial (n - 1)
Красным показаны охраняющие выражения. Они располагаются между
аргументом и знаком "=".
12
Функции высшего порядка
Много задач можно быстро решить при помощи функций, аргументами которых
служат другие функции.
13
Функция map
Функция map получает функцию преобразования a->b, список [a] и
вырабатывает новый список [b]. Вот ее определение:
map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map xs
Пример. Дан список чисел. Объявить функцию facts:: [Int]->[Int], которая
получает из него список факториалов этих чисел.
facts xs = map fact xs
Или короче:
facts = map fact
14
Функция filter
Эта функция «фильтрует» список, пропуская на выход лишь то, что удовлетворяет
заданному предикату p.
filter :: (a -> Bool) -> [a] -> [a]
filter p [] = []
filter p (x:xs) | p x = x : filter xs
| otherwise = filter xs
Пример. Объявить функцию, которая из заданного списка выберет числа,
большие, чем z.
getGT z = filter (> z)
15
Функция foldr
Сворачивают список в одно значение. Чтобы выполнить свертку, надо задать:
бинарную операцию свертки (над элементом списка и накопителем),
начальное значение накопителя, сворачиваемый список.
foldr :: (b -> a -> a) -> a -> [b] -> a
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
a – тип аккумулятора, b – тип элемента списка.
Пример. Просуммировать элементы списка.
Main> foldr (+) 0 [2,4,5,6,8]
16
Функция foldl
Функция foldr начинает свертку с самого правого элемента списка, а функция foldl –
с самого левого.
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs
Пример. Если элемент списка больше аккумулятора, добавляем его в аккумулятор.
fl a b = if b > a then a+b else a
fr b a = if b > a then a+b else a
foldr fr 0 [4, 2, 1]
foldl fl 0 [4, 2, 1]
-- печатает 7
-- печатает 4
17
Функция zipWith
Функция zip соединяет два списка в список пар (работает как zipper).
zip :: [a] -> [b] -> [(a,b)]
zip (a:as) (b:bs) = (a,b):zip as bs
zip _ _ = []
Обобщением этой функции является функция высшего порядка zipWith,
соединяющая два списка при помощи заданной функции:
zipWith :: (a->b->c)->[a]->[b]->[c]
zipWith z (a:as) (b:bs) = z a b : zipWith z as bs
zipWith _ _ _ = []
Пример. Определить функцию поэлементного суммирования двух списков.
sumList = zipWith (+)
18
Лямбда-выражения
\x y -> x + y
-- на C#: (x, y) => x + y
Применение: (\x y -> x + y) 2 3
19
Сечения
Каррированные функции можно применять частично.
Бинарная операция, примененная менее чем к двум аргументам, называется
сечением. Пример:
(3+) то же, что \x -> 3+x
(+4) то же, что \x -> x+4
(+) то же, что \x y -> x+y
Пример. Удвоить элементы списка, получив новый список.
map (*2) [1,3,5]
20
Самостоятельно
Определите следующие функции.
1. Функция, принимающая на входе список вещественных чисел и вычисляющая их
арифметическое среднее. Постарайтесь, чтобы функция осуществляла только один проход по
списку.
2. Функция вычленения n-го элемента из заданного списка.
3. Функция, которая определяет позицию заданного элемента в заданном списке. Если
элемента в списке нет, функция должна возвращать число -1.
4. Функция сложения элементов двух списков. Возвращает список, составленный из сумм
элементов списков-параметров. Учесть, что переданные списки могут быть разной длины.
5. Функция перестановки местами соседних четных и нечетных элементов в заданном списке
6. Функция twopow n, которая вычисляет 2n, исходя из следующих соображений. Пусть
необходимо возвести 2 в степень n. Если n четно, т.е. n = 2k, то 2n = 22k = (2k)2. Если n нечетно,
т.е. n = 2k + 1, то 2n = 22k+1 = 2 · (2k)2. Функция twopow не должна использовать оператор ^ или
любую функцию возведения в степень из стандартной библиотеки. Количество рекурсивных
вызовов функции должно быть пропорционально log n.
7. Функция removeOdd, которая удаляет из заданного списка целых чисел все нечетные числа.
Например: removeOdd [1,4,5,6,10] должен возвращать [4,10].
8. Функция removeEmpty, которая удаляет пустые строки из заданного списка строк. Например:
removeEmpty ["", "Hello", "", "", "World!"] возвращает ["Hello","World!"].
9. Функция countTrue :: [Bool] -> Integer, возвращающая количество элементов списка, равных
True.
10. Функция makePositive, которая меняет знак всех отрицательных элементов списка чисел,
21
например: makePositive [-1, 0, 5, -10, -20] дает [1,0,5,10,20]
Документ
Категория
Презентации
Просмотров
417
Размер файла
88 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа