1. Хаскель общая характеристикаосновные особенности

• Название: 1. Хаскель общая характеристикаосновные особенности
• Анкор: sfsdfdsafasdfdsaf
• Дата: 02.01.2022
• Размер: 205.5 Kb.
• Имя файла: fp_posobie.doc
• Тип: Документы; #323128

1. Хаскель: общая характеристика/основные особенности

Хаскель – современный, логично устроенный функциональный язык программирования, который вобрал в себя многие концепции и механизмы, отработанные в рамках других функциональных языков. В целом он гораздо более сложен, чем предшествующие ему языки, в том числе Лисп и Рефал.

Важной особенностью, отличающей его от Лиспа, является то, что Хаскель – чисто функциональный язык, в нем отсутствуют императивные конструкции, а значит, и побочные эффекты. Свойство функциональности соблюдается для любого синтаксически правильного вычислимого выражения.

В сравнении с Лиспом и Рефалом Хаскель является более функциональным языком, потому как его ключевые объекты – функции являются первоклассными объектами, т.е. над ними так же естественно осуществлять операции, как и над другими обрабатываемыми структурами данных. Это свойство в первую очередь иллюстрируют функционалы – функции, аргументом или значением которых являются другие функции. В отличие от лисповских функционалов, при программировании не надо задумываться над проблемой замыкания функционального аргумента, поскольку как и в подавляющем большинстве современных функциональных языков, в Хаскеле принято статическое (лексичесическое) связывание переменных, т.е. значения переменных в ходе вычислений определяются исходя из контекста их определения (а не контекста вычисления), и нет необходимости в соответствующих языковых средствах (таких как функциональная блокировка в языке Лисп).
Оперирование функциями как данными поддерживается\облегчается также встроенным в язык каррированием функций. Это означает, что все функции Хаскеля (стандартные и определённые пользователем) являются каррированными, т.е. сведены к суперпозиции одноаргументных функций, что делает возможным частичное применение функций от нескольких аргументов, когда часть аргументов фиксирована, а часть – нет. Как и в лямбда-исчислении, запись обращения к функции
f E₁ E₂ … E_n = (…(((f E₁)E₂)… E_n)

означает последовательное применение ее к первому, второму и т.д. аргументам с получением промежуточных результатов – функций с меньшим числом аргументов. Например, для функции двух аргументов f x y = x + y частичное ее применение f 2 = 2 + y означает получение в результате функции от одного аргумента y. Здесь уже видно, что в Хаскеле синтаксис обращения к функции (функциональной аппликации) восходит к синтаксису лямбда-исчисления, т.е. используется префиксная бесскобочная запись, аргументы функции отделяются пробелами, например: f 3 4 (сравн.: в Лиспе – префиксная скобочная запись:
(f 3 4) ). Аргументы функций Хаскеля при необходимости группируются скобками: f (3+8)4 .

К особенностям организации вычислений в Хаскеле относится также то, что в нем по умолчанию применяются ленивые вычисления, и аргументы функции вычисляются только тогда, когда их значение требуется в ходе вычисления тела функции (при этом некоторые аргументы могут остаться невычисленными). Ленивые вычисления соответствуют нормальному порядку редукции выражений в лямбда-исчислении. Ленивые вычисления дают возможность работы с бесконечными структурами, в частности, со списками. Для сравнения: в языке Лисп по умолчанию приняты энергичные вычисления (соответствующие аппликативному порядку редукции), и большинство функций являются строгими, т.е. вычисляют значения своих аргументов. В Хаскеле при необходимости можно явно указать энергичные вычисления.
Еще одним принципиальным отличием Хаскеля отЛиспа является принятая в нем статическая типизация переменныхвыражений, в том числе переменных, функций), статическая проверка типов.
Лисп: динамическая типизация (переменные не связываются с типами принимаемых ими значений, их тип определяется во время исполнения программы).
Большая гибкость, эффективность исполнения,но нет возможности проверить код заранее.
Статическая типизация: переменная, параметр функции и её значение связывается с типом в момент объявления, и тип не может быть изменён позже. Динамическая типизация: переменная связывается с типом в мемент получения значения.
Статическая типизация используется во многих языках программирования, все основные выражения (объекты) имеют тип, который проверяется на этапе компиляции программы.

константы (функции без аргументов) + значения - типы
Особенности типизации в Хаскеле:
а) все функции имеют тип ( а не только данные)
б) типы функций и выражений могут быть определены (и определяются) компилятором автоматически, т.е. автоматический вывод типов.
Тем не менее в программах принято указывать типы функций (хотя они могут быть выведены), декларации типов рассматриваются как спецификации функций для человека и служат для дополнительной проверки компилятором.
в) полиморфизм типов (типы имеют параметры) более логично устроен, чем в других языках.
В нём собраны все удачные концепции, отработанные в других функциональных языках. Наиболее важными из которых являются понятия образца выражения (развитого в функциональных языках Рефал, Плэнер, ML), анонимной функции (язык Лисп и др.), модуля (определения типов, функций для контроля пространства имён, абстракные типы данных, инкапсуляция: типы, данные, классы, функции)

1. Основные/базовые типы данных Хаскеля

Скалярные типы:

Int (целые – 2 или 4 байта).

Integer (длинные целые).

Float и Double (вещественные, т.е. с плавающей точкой). Второй тип – более длинные числа (больше байт для представления числа).

Bool (булевский).

Char (по сути целые числа длиной один байт – соответствующие коды символов).

Примеры констант:

• 
  2, -4 – константы целого типа;
  
• 
  2.35, pi – вещественные константы;
  
• 
  True, False – булевские константы;
  
• 
  'a', 'D' – константы типа Char.
  

Операции:

• 
  Для булевских величин: not (отрицание), && (конъюнкция), || (дизъюнкция).
  
• 
  Для чисел: +, -, *, div и mod (деление нацело и нахождение остатка от деления нацело – для целых Int и Integer), / (деление – результат всегда вещественное число), ^ - возведение в целую степень.
  
• 
  Для целых: odd (проверка нечётности) и even (проверка чётности числа).
  
• 
  Для вещественных: sqrt (корень квадратный), log, exp, sin, cos, tan, asin, acos, atan.
  
• 
  Для всех перечисленных типов: операции сравнения >, <, >=, <=, ==, /=.
  

Составные (структурные) типы:

Строго говоря, встроенных составных типов нет, но есть встроенные конструкторы, позволяющие создавать списки и кортежи. Поэтому можно считать, что эти составные типы уже встроены.

1. 
   Списки: состоят из однотипных элементов (т.е. гомогенны, однородны) – отличие от Лисп.
   

Но как и в Лиспе определены базовые оперции сос списками:

Аналог cons и точки в S-выражениях – конструктор :

Селекторы: head и tail (аналоги car и cdr). Их свойства:

head(x:y)=x tail(x:y)=y

(head(x:y)):(tail(x:y))=(x:y)

Конструктор, обозначающий пустой список – [].

Список из n элементов a₁, a₂ ... a_n:

Лисп: (a1 .(a2 .(…(an . NIL)…)))

Хаскель: (a1 :(a2 :(…(an : [])…)))

Как и в Лиспе, допускается более простая запись: [a1,a2,…an], однако списки могут включать значения только одного типа.

Примеры списков:

[True, True, False]

[1,3,5,7]

['a', 'c', 'f']

[[1,2],[3,4,5]]

С помощью знаков [] можно задавать тип списка: [Bool], [Int], [Char], [[Int]].

2. 
   Строки. Определение типа:
   

type String = [Char]

Можно записывать двумя способами: ['a', 'c', 'f']="acf"

3. 
   Кортежи: служат для объединения (группировки) значений разных типов. Это набор значений, заключённых в круглые скобки и разделённых запятыми.
   

Примеры: (5,7), (6,'c', True), (3, [8,2], ('v', 'n')).

Встроенные функции выбора соответственно первого и второго элемента кортежа из двух значений – fst и snd.

Аналогично, можно припомощи скобок задать типы кортежей:

(Int,Int) (Int,Char,Bool) (Int,[Int],(Char,Char))

Таким образом можно получить вложенные друг в друга списки и кортежи.
Для обозначения (указания) типа некоторого выражения используется знак :: (читается "имеет тип").

5 :: Integer (1,3) :: (Int,Int)

(1.0,2.0) :: (Float,Float) (2,'a') :: (Int,Char)

tail :: [a] -> [a]

length :: [a] -> Int

Замечание: определения типов 1-3 и функции работы с ними включены в стандартный модуль Prelude.
Синтакстческие соглашения:

1. 
   Соглашения по именованию
   

1. 
   Регистр символов важен, поэтому А и а разные идентификаторы.
   
2. 
   Первая буква имён (идентификаторов) также важна:
   Заглавная – для имён типов, имён модулей
   Строчная – для имён функций (в том числе констант), переменных
   Замечание: в качестве первого символа идентификатора могуб быть спецзнаки с особой семантикой.
   
   2. 
      Запись выражений
      
      1. 
         Функции (запись в префиксной форме) и операции(=функции, записывающиеся в инфиксной форме).
         Допустимы обе формы записи
         а) в одном выражении
         б) как для функций, так и для операций
         Соглашения:
         Если имя функции состоит из букв, то предполагается её префиксная запись, но возможна и инфиксная, для этого надо имя функции заключить в обратные апострофы.
         Если имя функции целиком состоит из небуквенных знаков, то предполагается её инфиксная запись (считается операцией), но возможна и префиксная запись, для этого надо имя функции заключить/взять в скобки.
         Примеры: (x `div` y) `mod` y (+) 2 3
         
      2. 
         Обращение к функции (функциональный вызов): префиксное бесскобочное (восходит к лямбда-исчислению)
         математика: f(3,4) Лисп: (f 3 4) Хаскель: f 3 4
         Аргументы отделяются пробелами. Скобки при необходимости используются для группировки каждого аргумента (если он – выражение).
         

Важны: приоритет, ассоциативность операций.

Наибольший приоритет имеет применение (вызов) функции (=аппликация).

Например, square – функция возведения в квадрат, тогда

square 2 – 2 ≡ (square 2) – 2 => 2 (а не 0!)

square square 2 => ошибка, чтобы было правильно, нужна группировка: square (square 2)

Арифметические и логические операции: обычный приоритет и ассоциативность (левая).

Примеры:

max 1 15 – suc 7 + 3 ≡ (max 1 15)-(suc 7)+3

max 15 (30 – suc 7) +1 ≡ (max 15 (30 –(suc 7)))+1

(+) (7*2) 2

Замечание: при определении новых операций (++, ▪) можно установить для них приоритет от 0 до 9 (10 – апплик??)
16. Хаскель: определение функции

Общий вид при использовании неявного cond:

Декларация типа функции имеет вид

<имя функции>::<тип арг₁> -> … -> <тип арг_N> -> <тип результата>

Выражение для типа функции строится из имён типов, знаков круглых и квадратных скобок, знаков -> и переменных.

-> по существу операция для конструирования типа, она правоассоциативна – это видно, если число аргументов функции более одного:

a -> b -> c ≡ a -> (b -> c)

Это отражает факт каррирования функции (все функции в Хаскеле каррированы)

Тело функции – список предложений вида

<образец обращения к функции>=<выражение для вычисления значения>

p₁ … p_N = expression , где N –число аргументов функции.

Образец p_i: выражение, записанное с использованием констант, конструкторов и переменных.

Примеры образцов: 5, x, x:(y:z), [x,y]
Пример 1. Функция, вычисляющая квадрат своего аргумента

square :: Int -> Integer

square x = x*x
При сопоставлении образца с фактическим аргументов означивание переменных, входящих в образец, должно происходить единственным образом (однозначно).

Анонимная переменная _ используется в случаях, когда её значение не нужно при вычислении значения функции. Их может быть несколько (несколько вхождений в образец) – в отличие от других переменных, которые могут входить в образец только один раз (различные вхождения анонимной переменной не связаны друг с другом – отличие от Рефала).
Пример 2. Функция конъюнкции

and :: Bool -> Bool -> Bool

and True True = True

and _ _ = False
Если подходящий образец (предложение) не найден в теле функции, то выдаётся ошибка.
Пример 3. Функция вычисления длины списка (из чисел)

length :: [Int] -> Int

length l = if (l==[]) then 0 else 1+length(tail l)

l – образец аргумента

Другой вариант – с использованием конструктора : (более соответствующий Хаскелю):

length :: [Int] -> Int

length [] = 0

length (_:xs)= 1 + length xs

Как работает это определение (при вычислении функции)? Похоже не Рефал!

По очереди рассматриваются строки определения. Находится первое, образец которого сопоставим с конкретным аргументом. В результате сопоставления найдены значения входящих в образец переменных, после чего вычислятся выражение после знака равенства (в общем случае оно содержит эти переменные).
Пример 4. Операция конкатенации двух списков (эквивалент append в Лиспе). Имя функции не буквенное, поэтому инфиксное обращение:

(++) :: [Int] -> [Int] -> [Int]

[] ++ ys = ys

(x:xs) ++ ys = x:(xs ++ ys)
Пример 5. Определение константы (константной функции)

pi :: Float

pi = 3.14
Интерпретация (выполнение) вызова функции:

1. 
   Нахождение первого по порядку сверху вниз набора образцов, успешно сопоставимых с фактическими параметрами, переданными на вход функции.
   
2. 
   Значения переменных образца подставляются в вычисляемое выражение, его значение – значение функции.
   

Часто при определении функции требуется проверять условия, т.е. записывать булевские логические выражения. Для этого в Хаскеле есть понятие/конструкция охранное (охраняющее) выражение (guarded expression = ограничения на образцы). По сути это логическое выражение, которое в определяющих функцию выражениях должно быть записано после образца, но перед выражением для вычисления значения функции (перед =). Для разграничения образца и охранного выражения используется символ | вертикальной черты.

Например:

min3 a b c | a <= b && a <= c = a

| b <= a && b <= c = b

| otherwise = c синоним True (определено в Prelude)

для похожести с математической записью

Какой тип функции будет автоматически выведен?

Последнее охранное выражение otherwise обеспечивает всюду определённость функции.

Вычисление/интерпретация:

Охранные выражения, относящиеся к одному образцу, просматриваются последовательно – пока не будет найдено условие, результат вычисления которого True. Тогда берётся (для вычисления значения функции) выражение, стоящее за ним и знаком =. Опять же, если подходящая пара образец-условие не будет найдена, то вычисление прервётся сообщением об ошибке. Таким образом, охранные выражения позволяют записывать ветвления после сопоставления с образцом.

Замечание: отступ знака | необходим, чтобы не повторять одинаковый образец.
Ещё один пример (функция выдаёт список из n заданных элементов):

replicate :: Int -> a -> [a]

replicate n x | n <= 0 = []

| otherwise = x : replicate (n - 1) x
Использование отступов – это ещё одно соглашение в синтаксисе Хаскеля. Отступ влияет на то, как интерпретируется строка:

• 
  если отступ такой же, как и у предыдущей строки, то эта строка – конструкция той же вложенности (подобная конструкция);
  
• 
  если отступ больше, то новая строка – продолжение предыдущей;
  
• 
  если отступ меньше, то завершение предыдущих конструкций, переход на более высокий уровень конструкций.
  

Эти соглашения действуют и при записи конструкций let и where, которые полезны в случаях, когда при вычислении возникает двойное вычисление некоторого подвыражения. Эти конструкции позволяют избежать неэффективности в вычислениях или упрощают запись сложных выражений за счет именования их подвыражений. За счет: определения новых функций/констант.

error " … " системная функция выдачи сообщения об ошибке.
Конструкция let в простейшем случае имеет вид:

let v = <выражение> in <выражение с вхождением v>
Пример. Вычисление корней квадратного уравнения ax²+bx+c=0. Значение функции – кортеж из двух значений (корней уравнения).

sqRoots :: Float -> Float -> Float -> (Float,Float)

sqRoots a b c =

let d = sqrt(b*b-4*a*c)

in ((-b+d)/(2*a),(-b-d)/(2*a))

Замечание: можно было вынести и вычислить отдельно также 2*а :

let { d = sqrt(b*b-4*a*c); w=2*a}

in ((-b+d)/w, (-b-d)/w)
Конструкция where аналогична, только локальные переменные (область их действия – конструкции let и where) определяются после их использования:

<выражение> where <выражение>

sqRoots a b c = ((-b+d)/w, (-b-d)/w)

where d = sqrt(b*b-4*a*c)

w=2*a

Здесь использовано соглашение об отступах, позволяющее опустить фигурные скобки и точку с запятой, разделяющую определения локальных переменных.

Важно! Локальные переменные – это функции! Никакого присваивания здесь нет, как и в случае let в Лиспе.
Замечания:

1. 
   Существенное отличие let от where:
   конструкция let имеет значение (значение итогового выражения), а конструкция where – нет, поэтому
   возможно 3*(let x=2 in x+x)
   но не 3*(x+x where x=2)
   
2. 
   Поскольку локально определяемые переменные – это функции, то в них можно использовать образцы и другое.
   
3. 
   where (let) может быть общей для нескольких предложений функции; записывается после (перед) этими предложениями???
   

Бесконечные списки за счёт бесконечной рекурсии

Функция, которая возвращает бесконечную последовательность единичек:
ones :: [Int]

ones = 1:ones



При раскрытии:

ones=1:1:ones

ones=1:1:1:ones

…

Но ленивость вычислений не приводит к бесконечной рекурсии. Любой конструктор лишь создаёт структуру, не вычисляя аргументы. Вычисление идёт при сопоставлении с образцом.
Компиляторы www.haskel.org (CHC (Classgoev?? Haskel Compiler), Hugs)
17. Хаскель: функционалы

Функционалы – вполне обычные функции, не требующие специальных средств для своего определения/вызова.

При необходимости выполнения некоторой операции (преобразования) над всеми элементами списка. Определение функционала:

myMap f [] = []

myMap f (x:xs) = f x : myMap f xs

Встроенная функция имеет имя map (есть в Prelude).

Пример. Функция по списку целых строит список знаков элементов исходного списка. Например: signList [1,-3,-4,0]==[1,-1,-1,0]

signList :: [Int] -> [Int]

signList x = myMap sign x
Также как и в Лиспе, в качестве функциональных аргументов допускаются анонимные функции. Их запись (от нескольких переменных):

\ x y -> x+y

Аналогия с лямбда-исчислением: символ \ – вместо λ, символы -> – вместо знака точки, после стрелочки – выражение для вычисления значения функции (в нём может быть образец, но это используется редко).

Замечание: поскольку все функции Хаскеля каррированные, то такая запись (функции с несколькими аргументами) эквивалентна следующей:

add = \x -> \y -> x+y

Анонимные функции полезны для единичного вызова в ходе вычислений.
Пример. Функция, увеличивающая свой целый аргумент на единицу. Её заголовок:

inc :: Int -> Int

Сама функция описывается в одну строку, ниже в каждой из строк даётся одно из возможных альтернативных определений этой функции:

inc x = x+1

inc x = add x 1

inc = \x -> x+1

inc = (+1)

inc = (1+)

inc = add 1

Соответственно функцию incList, увеличивающую все элементы целочисленного списка на единицу, можно определить любой из описанных ниже строк:

incList x = map inc x

incList x = map (\x -> x+1) x

incList x = map (+1) x

incList x = map (add 1) x

Замечание: во всех строках переменная х (аргумент функции) может быть опущена:

incList = map inc

…

Запись, подобная (+1), называется секцией (сечение, section). По сути это запись частичной функции для передачи в качестве функционального аргумента. В ней обязательны скобки для правильной группировки инфиксных операций.

Частичные функции получаются подстановкой фактического аргумента в тело функции.

Замечание: в отличие от обычных функций, для инфиксных операций в секции можно указывать как первый, так и второй аргумент, что удобно. Иногда это не важно: (+1) и (1+), иногда важно: (/2) и (2/). Ещё примеры: (х++) (++)?? (++y). Специализация уже существующей функции нужными аргументами.
Можно также определить (или использовать встроенные) другие функционалы. Функционалы свёртки (аналоги лисповкого reduce):

правая свёртка: foldr f a x == f x₁ (f x₂ …(f x_n a)…)

левая свёртка: foldl f a x == f(f …(f (f a x₁) x₂)… x_n-1)x_n

где х == [x₁, x₂, … , x_n]

Если нет необходимости в константе (или константу нельзя задать):

foldr1 f x == f x₁ (f x₂ …(f x_n-1 x_n)…)

foldl1 f x == f(f … (f x₁ x₂)… x_n-1)x_n

Примеры:

foldl (+) 0 [1,2,3] == 6

foldr (+) 0 [1,2,3] == 6

foldl1 (+) [1,2,3] == 6

foldr1 (+) [1,2,3] == 6

Функция нахождения максимального элемента списка (здесь существенно без а):

maximum (Ord a) => [a] -> a

maximum = foldr1 max

или

maximum = foldl1 max
Свёртки могут быть применены когда:

• 
  требуется один поэлементный проход по списку
  
• 
  возврат одного значения на базе этого прохода
  

Примеры: суммирование и произведение всех элементов списка

sum = foldl1 (+)

product = foldl1 (*)
Другие полезные функционалы

filter выбирает из списка значение, удовлетворяющее заданной функции-предикату. Например:

filter (>0) [1,-2,-3,4,0] == [1,4]
takeWhile выбирает начальную последовательность элементов списка, удовлетворяющих предикату (до первого элемента, не удовлетворяющего условию):

takeWhile (<4) [1,-2,-3,4,0] == [1,-2,-3]
dropWhile отбрасывает начальную последовательность элементов списка, удовлетворяющих предикату

dropWhile (<4) [1,-2,-3,4,0] == [4,0]
any/all - один/все элементы списка удовлетворяют заданному предикату.

Функциональный аргумент этих функционалов – предикат, т.е. функция, возвращающая булевское значение.
zipWith поэлементное объединение двух списков на основе некоторой двухместной функции (например, +, *, max). Пример использования:

zipWith max [4,-2,-3] [1,0,5] == [4,0,5]

Определение этой функции:

zipWith :: (a->b->c) -> [a] -> [b] -> [c]

zipWith _ [] _ = []

zipWith _ _ [] = []

zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys
Функция, дважды применяющая функциональный аргумент (функцию) к второму аргументу:

twice :: (a -> a) -> a -> a

twice f x = f (f x)

Пример: twice inc 7 == 9

Тип twice inc :: Int->Int

Т.е. исходя из контекста применения переменная типа получает значение.

Тип twice twice :: (c -> c) -> c -> c
Инфиксная операция композиции функций (встроена):

(.) :: (b -> c) -> ( a-> b) -> (a -> c)

f . g = \x -> f(g x) или (f . g) x= f(g x)

Удобна для записи сложных функций. Точка выделяется пробелами! Создание функций "на лету" для передачи другим функциям в качестве параметра. Пример:

map ((*3) . sign) list

Композиция правоассоциативна:

h = f1 . f2 . f3

h x = f1(f2(f3 x))

h = \x -> f1(f2(f3 x))
Таким образом, функции высшего порядка дают возможность определять и использовать абстрактные шаблоны поведения.
Быстрая сортировка Хоара на основе функционалов:

quickSort :: (Ord a) => [a] -> [a]

quickSort [] = []

quickSort (x:xs) = smaller ++ [x] ++ bigger

where smaller = quickSort(filter (< x) xs)

bigger = quickSort(filter (>= x) xs)
Примеры композиций (семинар)

(sum . replicate 5)(max 6 9)

replicate 2 (product (map (*3)(zipWith max [1,2] [4,5]))

= replicate 2 . product (map (*3)(zipWith max [1,2] [4,5]))

18. Хаскель: классы типов и полиморфизм

В языке есть:

1. 
   встроенные типы (например, type String = [Char])
   
2. 
   средства конструирования новых типов [,],(,) и другие
   
3. 
   возможность ввести имя (синоним) типа
   
4. 
   полиморфные функции
   

При работе со структурами принято давать им имена. Например:

type Point3D = (Float,Float,Float)
Логичная систематизация типов вводит понятия класса типов и экземпляра класса.

Концепция класса типов: класс характеризуется набором функций/операций (определяются свойствами), применимых к типам этого класса.

Например, класс Eq охватывает типы, поддерживающие операцию сравнения (значений) на равенство (проверку равенства).
Хаскель статически типизированный язык, механизм вывода типов определённый. Любой синтаксически правильное выражение (в том числе функционаные выражения) имеет свой тип, известный при компиляции. Например:

map :: (a -> b) -> [a] -> [b]

(:) :: a -> [a] -> [a]

эти объявления выведет компилятор, но обычно декларируют при определении.

Сигнатура функции читается так: для любого типа а функция f имеет тип ... Какой именно тип – определяется при компиляции (выводится из контекста).

а, b – типовые переменные (независимые переменные типа, не обязаны быть разными).

map – полиморфная функция

Полиморфные функции: те, в объявлении которых встречаются переменные типа.

Насколько широко может пониматься а, b (что может быть их значением)? Чтобы полиморфные функции правильно работали (и правильно компилировались) часто необходимо задавать ограничения на типовые переменные, точнее: какие операции возможны над значениями типов.

Например, функция member поиска элемента в списке (встроенная elem)

member :: a -> [a] -> Bool

Чтобы реализовать поиск в списке элемента типа а, необходимо уметь сравнивать (проверять на равенство) элементы. Т.е. для типа а должна быть реализована операция Eq.??

Должен быть способ указывать при определнии функций, какие оперции должны поддерживаться типом, чтобы полиморфная функция могла вычисляться.

Замечание: сравнение концепции с понятием класса в других (императивных) объектно-ориентированных языках.

Императивный ООЯ: класс≡тип объектов, Хаскель: класс≡множество типов с общими операциями, т.е. метатип. Похоже: понятие интерфейса, определяющего некоторое поведение. В Хаскеле говорят: тип входит в класс или является экземпляром класса (принадлежит классу).
Базовые классы типов

Класс Eq предоставляет интерфейс для проверки на равенство: операции == (равно) и /= (неравно). Если для значений некоторого типа предполагается проверять равенство, то он должен быть экземпляром этого класса. Почти все рассмотренные стандартные типы, за исключением функциональных, входят в Eq.
Класс Ord: типы, поддерживающие отношение порядка. К операциям, определённым в Eq, добавляются операции >, >=, <, <=, max a b, min a b (+ compare???).

В этот класс входят типы Char, Int, Integer, Float, Double, Bool.
Класс Num – класс типов для чисел. К перечисленным выше операциям добавляются операции +, -, *, abs, signum, negate, fromInteger, fromInt. Числа – полиморфные константы.
Класс Floating – класс типов для вещественных чисел. В это класс входят типы Float, Double. К операциям класса Num добавляются операции sqrt (квадратный корень), exp, log, pi, sin, cos, tg, asin, acos, atan (тригонометрические функции).
Класс Integral – класс типов для целых чисел: Int, Integer. К операциям класса Num добавляется функция fromIntegral: принимает целое число типа Int или Integer, а возвращает число типа Num (преобразование типа). Пример (когда она необходима): fromIntegral(length [1,2,3])+5.2
Класс Enum – класс типов с последовательным упорядочиванием значений (т.е. определён их порядок следования, поэтому значения таких типов можно перенумеровать). Их можно использовать в интервалах списков. В это класс из встроенных входят все числовые типы, Char, Bool. Операции (функции), определённые в классе: succ, pred, toEnum, fromEnum. Примеры:

succ 'b' == 'c' succ 7 == 8
Класс Bounded – типы, у которых есть значения верхней и нижней границы (Int, Integer, Bool, Char). Определены полиморфные функции-константы minBound и maxBound. Пример: minBound для Bool возвращает False.
Класс Show – типы, значения которых могут быть графически представлены как строки (а, следовательно, показаны). Все рассмотренные типы – экземпляры класса Show. Даёт возможность вывода на печать значения сложного типа. Определена функция show:: a-> String преобразования значения в строку. Например:

вычисление show 5.33 возвращает "5.33".
Класс Read (в определённом смысле противоположен Show) – типы, значения которых могут быть считаны как строки. Определена функция read: принимает строку и возвращает значение другого типа. Например:

read "8.2" + 1.8 == 10.0

Декларция типа функции: read:: String -> a

Замечание: read полиморфна в типе возвращаемого значения, поэтому если из контекста не ясно, какой тип должен быть у считанного значения, то следует использовать операцию аннотации (объявления) типа: например,

read "13" :: Int
Возвращаемся к полиморфным функциям. В общем случае при определении такой функции в её сигнатуре (декларации типа) следует записать так называемое ограничение класса, к которому должна принадлежать каждая переменная типа (точнее обозначаемый ею тип). Например:

elem :: (Eq a) => a -> [a] -> Bool

Читается: для любого типа а, являющегося экземпляром класса Eq (чтобы использовать в функции ==), функция имеет тип

Сигнатуры операций и функций рассмотренных классов:

(==) :: (Eq a) => a -> a -> Bool

(*) :: (Num a) => a -> a -> a

fromIntegral :: (Num b, Integral a) => a -> b

Таким образом, возможно несколько ограничений, записываемых через запятую.

Наследование – это просто ограничение на класс типа-параметра при объявлении класса:

class C a => D a where …

= любой тип а принадлежит классу D, если он является экземпляром С и реализует его операции.
Замечание:

1. 
   Один тип может быть экземпляром нескольких классов. Например, Char является экземпляром классов Eq и Ord.
   
2. 
   Очевидна некоторая связь (родственность/детализация) классов. При определении классов могут устанавливаться аналогичные ограничения класса для типа а (чтобы подкласс допускал). Например (в стандартной библиотеке): class (Eq a, Show a) => Num a where …
   можно считать что Num – наследник Eq и Show
   class (Eq a) => Ord a
   
3. 
   Если мы решаем сделать некоторый тип экземпляром некоторого класса, то должны в общем случае реализовать/определить функции этого класса.
   Объявление экземпляра: instance (ключевое слово).
   

19. Хаскель: конструкторы данных и конструкторы типов

В языке есть средства определния новых типов данных. Конструкция с ключевым словом data служит для объявления нового типа. Примеры:

data Point = Point Float Float

data Fifure = Circle Point Float | Square Point Point

Point и Figure – конструкторы типа (выполняют роль имени типа), выделенные жирным Point, Circle и Square – конструкторы данных (имена значений этого типа). Имена конструкторов должны начинаться с заглавной буквы. Вертикальная черта читается как "или", т.е. фигура – это круг или квадрат.

Замечания:

1. 
   Конструкторы данных по сути являются функциями:
   Circle :: Point -> Float -> Figure
   Square :: Point -> Point -> Figure
   
2. 
   В альтернативах могут быть конструкторы с разным количеством параметров.
   
3. 
   Имя конструктора значений может совпадать с именем типа.
   
4. 
   Запись конкретных значений введённых типов:
   Point 1.5 2
   Square (Point 1.5 2) (Point 0 0)
   Замечание: Можно было бы в этом примере не вводить типы Point, Figure, а воспользоваться кортежами. Однако: полезно именование типов используемых структур данных.
   Напомним: конструкторы могут использоваться при сопоставлении с образцом. Для вычисления площади фигуры:
   sqr :: Figure -> Float
   sqr (Circle _ r) = pi * r^2
   sqr (Square (Point x1 y1)(Point x2 y2)) = abs (dx*dy)
   where dx = x1 – x2
   dy = y1 – y2
   здесь скобки обязательны.
   
5. 
   Т.к. конструкторы данных – функции, а все функци каррированы, их можно использовать в частичных вычислениях:
   map (Circle (Point 0 0)) [1,2,3] == список из трёх кругов с центром в (0,0) и радиусами 1, 2 и 3 (концентрические). Они удовлетворяют всем соглашениям об именах префиксных/инфиксных функций.
   
6. 
   Порядок указания конструкторов в альтернативах важен – этот порядок фиксируется компилятором и его можно использовать в операциях сравнения >,<,<= ... (класс Ord), поскольку компилятор может автоматически порождать экземпляры (меньшим считается значение, конструктор которого определён раньше).
   
7. 
   Конструкторы сами могут быть значениями (посути: функции нулевой арности, без аргументов). Например:
   в модуле Prelude data Bool = True | False
   трёхзначная логика:
   data Tbool = Yes | No | Unknown
   tand:: Tbool-> Tbool-> Tbool
   tand Yes Yes = Yes операция конъюнкции
   tand No _ = No
   tand _ No = No
   tand _ _ = Unknown
   
8. 
   Можно сравнить с записями (языки С, Паскаль). Есть ли возможность именования полей записей, как в этих языках? Можно заметить, что пока в примерах именуются структуры в целом (имена конструкторов данных), но не все их отдельные части.
   В языке Хаскель есть возможность именования внутренних частей структур данных(полей структуры). Пример:
   

data Person = Person String String Int String String

имя фамилия возраст телефон адрес

Для удобства есть возможность записи с именованными полями (ввести имя для каждого поля):

data Person = Person {

firstName :: String,

lastName :: String,

age :: Int,

phoneNumber :: String,

address :: String }

Имена полей можно использовать при вызове конструктора (при задании конкретных записей):

let sdr = Person { firstName = "Ivan", lastName = "Sidorov",

age = 45, phoneNumber = "4951234567",

address = "Tverskaya, 25" }

Замечания:

1. 
   На самом деле, имя поля – это функция (создаётся компилятором):
   firstName :: Person -> String
   age :: Person -> Int
   Аналогичные функции доступа к полям записи мы могли сами определить.
   
2. 
   Имена полей можно вводить и в рекурсивных структурах.
   

Рекурсивные типы

В Хаскеле возможно рекурсивное определение типов данных. Например, двоичное бинарное дерево (в нём либо лист, либо есть оба/два поддерева), т.е. любой узел – либо лист, либо узел с двумя поддеревьями. И пусть в узлах хранятся значения типа Int. Тогда:

data BiTree = Leaf Int | BiTree Int BiTree BiTree

или

data BiTree = Leaf {value :: Int} |

BiTree {value :: Int, left, right :: BiTree}

если поименовать поля записей

Запись конкретных деревьев с помощью конструкторов:

Leaf 7

BiTree 2 (Leaf 5)(Leaf 3) 3 узла

BiTree 1 (Leaf 0)(BiTree 4 (Leaf 7)(Leaf 3)) 5 узлов
Функция увеличения узлов дерева на единицу:

incValTree :: BiTree -> BiTree

incValTree (Leaf v) = Leaf (v+1)

incValTree (BiTree v left right) = BiTree (v+1)

(incValTree left)

(incValTree right)

Фактически: конструируем дерево заново, с новыми значениями в узлах.

Функционал для дерева, подобный функционалу map для списков:

mapTree :: (Int -> Int) -> BiTree -> BiTree

mapTree f (Leaf v)= Leaf (f v)

mapTree f (BiTree v l r) = BiTree (f v)(mapTree f l)

(mapTree f r)

Опять: конструируем заново дерево.

Тогда можно записать:

incValTree = mapTree (+1)

doubleValTree = mapTree (2*)

Такая краткость возможна, т.к. функциональный аргумент – первый, а дерево – второй аргумент (не можем опустить первый аргумент, не опустив второго).
Можно определить списки следующим образом:

data List a = Empty | Cons a (List a) или a -:- (List a)

Empty – константа с тем же смыслом, что и [], Cons – конструктор (как и :).

Поведение – эквивалентно [a], если определить все соответствующие функции (head, tail и т.д.).

Но data [a]= [] | a:[a] синтаксически неверно!
Конструкторы типов

Понять смысл/обоснованность этого названия можно в случаях, когда типы имеют параметры (полиморфны). Например:

data Maybe a = Nothing | Just a

Maybe – конструктор типа, Nothing и Just – конструкторы данных. Абстракция для случаев, когда может быть пустое значение.

Если конструкторы данных принимают в качестве аргументов значения (некоторого типа) и возвращают значения (другого типа), то конструкторы типов принимают в качестве аргументов типы и возвращают новый тип.

Возможны: Maybe Int, Maybe Char, Maybe [a] и др.

Just 'a' :: Maybe Char автоматически выводится тип

Ещё один важный тип:

data Either a b = Left a | Right b

инкапсуляция значения одного из двух типов.

Maybe, Either – полиморфные типы.

Напомним: есть ключевое слово для опеределения синонима типа (не путать с конструированием типа):

type Name = String

type Address = String

type Date = (Int,Month,Int)

type String = [Char] дать мнемоническое имя уже существующему типу

data Month = Jan | Feb | Mar | … | Nov | Dec

↑ уже конструктор ↑ конструкторы без параметров

Могут быть синонимы с параметрами (типов), т.е. параметризация синонимов. Например:

type AssocList k v = [(k,v)]

type Vector3 a = (a,a,a)

В случае определения собственно типов полезно, чтобы они были экземплярами базовых классов – для этого и используется конструкция

instance <класс> <экземпляр> where

Предполагается реализация функций базового класса, к которому подсоединяется новый тип, для этого нового класса.

Базовый класс Num определён в стандартной библиотеке (модуле Prelude):

class (Eq a, Show a) => Num a where

(+),(-),(*) :: a -> a -> a

negate :: a -> a

abs, signum :: a -> a

fromInteger :: Integer -> a

fromInt :: Int -> a

После ключевого слова class заданы ограничения на тип а: чтобы а мог быть экземпляром Num, он должен быть экземпляром Eq и Show. Тип может быть сделан экземпляром класса, если он поддерживает соответствующее поведение.

Определим тип, представляющий натуральное число, и включим его в класс Num:

data Natural = Natural Int

Это непосредственное объявление экземпляра класса.

Реализуем сначала функции Eq (Show опустим):

instance Eq Natural where

(Natural x) == (Natural y) = x == y

операцию /= явно определять не будем, поскольку в классе Eq она определена как отрицание для ==. Далее:

instance Num Natural where

(Natural x)+(Natural y) = fromInt(x+y)

(Natural x)-(Natural y) = fromInt(x-y)

(Natural x)*(Natural y) = fromInt(x*y)

"распаковка", выполнение операции, "запаковка" (преобразование) в натуральное число

fromInt x | x>0 = Natural x

| otherwise = undefined

abs a = a

signum a = 1

negate a = undefined

Пример функции над натуральными числами:

incNat :: Natural -> Natural

incNat a = a+1

т.к. любое целое число воспринимается компилятором как вызов fromInt с соответствующим аргументом (автоматическое преобразование к нужному типу).
Аналогично: преобразование к нужному типу 0 и 1 в функции

fact :: (Num a) => a -> a

fact 0 = 1

fact n = n* fact(n-1)
Можно заметить, что приведение реализации функций класса Eq достаточно очевидно и может быть выполнено компилятором (выведено) автоматически. Это так для простых типов: Natural, Point и базовых классов Eq, Ord, Show. Поэтому можно поручить/возложить это на компилятор, используя директиву deriving:

data Natural = Natural Int deriving (Eq)

data Point = Point Float Float deriving (Eq, Show)

Действительно: Natural состоит из одного элемента, Point – сущность из 2-х элементов. Eq: сравнение – поэлементное. Show: отображение в виде строки с помощью перевода в строку составляющих элементов и имён конструкторов. Посути: вывод реализаций функций на основе известных реализаций этих функций для компонент конструктора – значений.
Вывод классов типов (точнее, функций классов) – возможен и для полиморфных типов:

data Vector a a a = Vector a a a deriving (Eq)

но точнее, следовало бы записать:

data (Eq a) => Vector a a a = Vector a a a deriving (Eq)

↑ ограничение на класс

Т.е. экземплярами класса Eq будут не все возможные типы Vector a a a, а только такие, для которых а принадлежит классу Eq.
Вывод классов возможен и для более сложных структур, в частности, для дерева:

data BiTree = Leaf Int |

BiTree Int BiTree BiTree deriving (Eq, Ord)

и для полиморфного дерева (но тогда необходимо добавить ограничение на класс для типа а)
Замечание: автоматический вывод (генерация) экземпляров класса возможен:

1. 
   для базовых классов Eq, Ord, Enum, Bounded, Show, Read и некоторых других (т.е. не для всех базовых классов);
   
2. 
   deriving (механизм автоматического вывода экземпляров) подразумевает неявное объявление экземпляра.
   

data Either a b = Left a | Right b

deriving (Eq, Ord, Read, Show)
Операция ++ значительно затратнее, чем :, так что целесообразнее использовать правую свёртку для построения списка из списков.

20. Хаскель: генераторы списков, бесконечные списки

В языке Хаскель есть несколько удобных средств для записи списков:

• 
  интервалы;
  
• 
  списочные выражения (list comprehensoin);
  
• 
  бесконечные списки.
  

Интервалы, а частности, удобны для записис/создания списков чисел, являющихся арифметической последовательностью. Например:

[1..20] – список чисел от 1 до 20

[2,4..20] – все чётные числа от 1 до 20

[3,6..20] – список чисел от 3 до 18???? с шагом 3

[20,19..1] – другой порядок чисел от 1 до 20 (в обратном порядке)

В общем случае в интервалах могут быть указаны (в качестве элементов списка) любые значения, тип которых принадлежит классу типов Enum, и даже выражения для их вычисления: [3,6..49*18]

В частности, Char:

['U'..'Z'] == "UVWXYZ"

['a'..'e'] == "abcde"

А как задать геометрические прогресии? С помощью функций для конструирования бесконечных списков.
Списочное выражение (list comprehensoin) – мощная синтаксическая конструкция для записи списков; упрощает обработку списков. Эта конструкция похожа на запись множеств в математике. Например:

[x*2 | x <- [1..10]] – список удвоенных чисел из заданного интервала: х последовательно принимает значения элементов списка, и для него вычисляется значение соответствующего элемента результирующего списка.

[x | x <- [12..100], x mod 5 == 0] – список чисел из заданного интервала, делящихся без остатка на 5, т.е. ==[10,15..100].

При таком задании списков до вертикальной черты задаётся выражение для вычисления элемента списка, после вертикальной черты – источник выборки данных (список или даже несколько списков через запятую) и охранное выражение (условие выборки: накладывается на выбираемые из источника значения, возможно несколько условий через запятую, по сути: фильтрация).

Ещё один пример:

[(x,y) | x <- xs, y <- ys, x <= y]

Правило генерации элементов списка:

1. 
   Выбрать значения (последовательно) из заданного списка/ов, удовлетворяющие заданным условиям (условию).
   
2. 
   Вычислить по ним (используя выражение) значения результирующего списка.
   

Возможно использование конструкции let, например:

[x | (y,z) <- listOfPairs, let x = y^2+z^2, x>16]

Примеры определения списков на основе генераторов списков:

points list1 list2 = [(x,y) | x <- list1, y <- list2, x+y>10]

- список кортежей чисел, сумма которых больше 10.

Как вычисляется? При фиксированном х рассматриваются (генерируются) y, таким образом, рассматриваются все комбинации из элементов заданных списков, и из них отбираются нужные (условие применения выборки).

removeUppercase str = [c | c <- str, c `elem` ['a'..'z']]

removeUppercase "XYafZ" == "af"

Функционалы:

mapC f list = [f x | x <- list]

filterC f list = [x | x <- list, f x]

Обычные функции:

lengthC list = sum [1 | _ <- list]

Замечание: возможны вложенные генераторы.
Интервалы можно использовать для создания бесконеных списков (верхний предел не указывается). Например:

[1..] – список натуральных чисел

[2,4..] – список чётных чисел

Т.к. в реальности нужно лишь конечное число определённых значений:

take 15 [7,12,..1000]
Возникает вопрос: как представляются бесконечные списки? Ключевой момент для понимания этого: в Хаскеле ленивое вычисление большинства функций. Конструкторы данных – функции, все они ленивые, их вычисление – по необходимости, например, при сопоставлении с образцом. Конструкторы лишь конструируют (создают) структуры (составные данные). Списки создаются двумя конструкторами: [] и : (инфиксная, аналог cons). Как структура запись вида [1,2,3] лишь упрощение записи 1:2:3:[].

Поэтому возможны определения рекурсивных функций вида:

ones :: [Int]

ones = 1:ones

- список из единиц. Бесконечная рекурсия? В рамках объемлющей функции нам необходимо конечное число единиц. Вспомним описание функции take:

take 0 _ = []

take n (x:xs) = x : take (n-1) xs

Тогда шаги вычисления этой фунции с аргументом ones:

take 3 ones

take 3 (1:ones)

1:take 2 ones

1:take 2 (1:ones)

1:1:take 1 ones

1:1:take 1 (1:ones)

1:1:1:take 0 ones

1:1:1:[] что == [1,1,1]

Т.к. для любого т будет построен соответствующий список (из нужного количества элементов-единичек), то список действительно бесконечный.

Аналогично функция:

powersOf2 x = x : powersOf2(x*2)

Вычисление powersOf2 1 даёт бесконечный список степеней двойки.

Бесконечные списки могут использоваться в функционалах:

sum(take 100 (filter odd (map (^2) [1..])))

- сумма первых 100 нечётных квадратов натуральных чисел.
Функции для конструирования бесконечных списков

repeat x == [x,x,…] – бесконечный список-повторение заданного значения

Например, ones = repeat 1

cycle [1,2,3] == [1,2,3,1,2,3,…] – бесконечное поочерёдное повторение элементов заданного списка.

iterate f x – список, каждый эелмент которого есть применение f к предыдущему элементу.

Например: powersOf2 1 = iterate (*2) 1

Соответственно, можно получить прогрессию, если

f = (*n) – геометрическая прогрессия

f = (+m) – арифметическая прогрессия
Числа Фибоначчи: бесконечный список

fibSeq :: Integer -> Integer -> [Integer]

fibSeq m n = m : fibSeq n (m+n)

fibonacci :: [Integer]

fibonacci = fibSeq 1 1
Быстрая сортировка:

quickSort :: (Ord a) => [a] -> [a]

quickSort [] = []

quickSort (x:xs) = smaller ++ [x] ++ bigger

where smaller = quickSort [z | z <- xs, z < x]

bigger = quickSort [z | z <- xs, z >= x]