Поліморфія та класи в Haskell
Привіт, любий читачу!
Сьогодні ми поговоримо про поліморфізм функцій та про класи у мові Haskell, як їх використовувати і для чого вони потрібні. Усі ми використовували метод поліморфізму, наприклад, у Java. А як це можна застосувати до Haskell? Haskell не є об'єктно-орієнтованою мовою, але в ньому все ж таки присутні класи. Хоча класи в Haskell і мають деякі властивості класів об'єктно-орієнтованих мов, вони абстраговані і від цього набагато потужніші. Проводячи аналогію з мовою Java далі, класи в Haskell є нічим іншим як інтерфейси — у клас записуються лише декларації функцій, а реалізації цих функцій буде зроблено пізніше. Хочеться висловити подяку користувачеві Darkus за прочитання та виправлення всіх недоліків та неточностей у статті, а також за слушні поради та допомогу у написанні.
Поліморфізм функцій
У Haskell існує два види поліморфізму — параметричний і спеціальний (англійською мовою називають терміном ad hoc, який прийшов з латинської мови).
Параметричний
Якщо ви хоч раз програмували мовою Haskell, то неодмінно зустрічали приклади параметричного поліморфізму в функціях length, head, teal, curry, uncurry, map, filter, . . Що поєднує всі ці функції? Давайте подивимося на реалізацію деяких із них:
У перших трьох функцій вхідний параметр типу a, а у curry і uncurry ще b і c. Замість конкретного типу даних (Int, Bool, Char, .) використовується типізація. Приклад на java:
Тут також використовується А — невідомий тип даних, який буде визначено під час компіляції. Поліморфізм використовується тоді, коли невідомо якого типу даних буде параметр, але відомі операції, які над ним (ІЛМ з ним) будуть здійснюватися.
Усі ідентифікатори типових змінних у мові Haskell повинні починатися з маленької літери (наприклад, a, abc, aA101), а всі конкретні типи (конструктори) починаються з великої літери (наприклад, String, Int, Node).
Параметр a може приймати будь-які типи, Int, String або навіть функції (наприклад, length [f, g, h] , де f, g, h - функції, які мають однакові типи). Варто зауважити, що тип b може приймати будь-які типи, в тому числі і тип параметра a .
Тип функції в інтерпретаторі GHCi (і Hugs) завжди можна дізнатися за допомогою команди :t , наприклад:
Спеціальний (ad hoc)
Синонімом спеціального поліморфізму є термін "перевантажені функції". Це слабкіший тип поліморфізму, ніж параметричний. Візьмемо для прикладу оператор (функцію) додавання (+). Вираження такого виду (+) 2 3 ->> 5 (+) 2.5 3.85 ->> 6.35 відрізняються від виразів (+) True False (+) [1,2,3] [3,2,1] тем, що в першому випадку були використані чисельні значення, а у другому значення типу Bool та [Int]. Оператор додавання не визначений для нечисленних типів. Все тому, що ця функція має тип (+) :: a -> a -> a а такий (+) :: Num a => a -> a -> a. Тобто тут вводиться обмеження на тип даних, що вводяться (і виводяться).
Обмеження, яке накладено тип a : Num a говорить, що тип a має бути елементом класу Num. Такі класи типів дуже важливі у Haskell, оскільки вони додають додатковий захист від помилок під час програмування, а також можуть зменшити кількість написаного коду в рази. Це ми побачимо у наступному прикладі.
Дано такі типи двійкових дерев: Двійкове дерево, яке може зберігати будь-який тип даних
Двійкове дерево, яке може зберігати два елементи, і кожневідгалуження закінчується «листом» з одним елементом (а не Nil):
Двійкове дерево, яке може зберігати дані типу String і теж закінчується листом:
І, скажімо, є ще два види списків: звичайний
Маючи всі ці структури даних, хотілося б написати функцію size, яка незалежно від структури даних, виводила б її глибину (для дерев), або довжину (для списків), або одним словом — розмір. Наївним рішенням було написати для кожного свою функцію:
Тепер якщо з'явиться ще якась структура даних, то доведеться виконувати нову функцію, яка буде підходити тільки для цієї структури. А нам хотілося б, щоб однією функцією можна було отримати розмір будь-якої структури даних. Як у функції (+) було обмеження класом Num, і нам треба зробити обмеження класом Size, а цього треба його спочатку створити:
Залишилося тільки зробити екземпляри (інстанції) цього класу під конкретні значення a (=під конкретні типи даних):
Готово! Тепер якщо ми в GHCi напишемо :t size , побачимо size :: Size a => a -> Int. Ми отримали що хотіли:
Кожен екземпляр класу Size реалізував функцію size, яка може бути застосована лише до значень певного типу (=структурам даних). У цьому випадку ця функція, як і інші певні оператори (+), (*), (-), перевантажена.
Але є й свої мінуси такого рішення. Наприклад, нам хотілося б дізнатися кількість елементів у парному списку, тобто
Очевидно було б зробити таке:
Але тут у нас виникне проблема, тому у нас вже є інстанція для звичайного списку (instance Size [a] where ), нам більше не можна використовувати інше визначення, тому що, як уже говорилося раніше, тип a може бути будь-якимтипом, зокрема (b,c) , тобто. [a] == [(b,c)] Для вирішення цієї проблеми можна використовувати Overlapping Instances (англ. перекриваючі екземпляри класу). У цього рішення є і свої мінуси (імпорт одного з модулів може змінити значення програми, може викликати помилки, що збивають з пантелику, і так далі). Тепер трохи докладніше про класи.
У попередньому прикладі ми склали клас Size , а ось неповна декларація класу Haskell: (tv = type variable):
Неповна тому, що до декларації класу також можуть бути введені обмеження на tv (наприклад, tv має бути елементом класу Ord). Сигнатур може бути скільки завгодно, але кожна з них повинна включати (як вхідний та вихідний параметр) змінну tv. Типові класи - це колекції типів, для яких визначені спеціальні функції. Ось деякі (одні з найважливіших) класи в Haskell:
- Eq- клас для тесту на рівність (нерівність) двох типів даних (операції ==, /=)
- Ord— клас визначення порядку типів, тобто який елемент більше, який менше (операції >, >=, deriving ). Між класами існує також залежність. Наприклад, якщо ми знаємо як порівнювати два елементи (клас Ord), ми повинні заздалегідь вміти визначати чи дорівнює один елемент іншому (клас Eq). Адже реалізації оператора ( >= ) треба мати реалізований оператор (==). Тому можна сказати, що клас Ord залежить (успадковує) від класу Eq. Ось докладніша схема залежності класів:
Погляньмо на клас еквівалентності Eq більш детально. Як раніше було згадано, цей клас повинен мати дві функції (==) і (/=):
З коду видно, що для будь-якої інстанції класу Eq достатньо реалізувати одну з двох функцій. Наприклад, для типу Bool (дватипу рівні лише тоді, коли вони обидва True або False) це зроблено так:
Як видно, випадок True False і False True (як і останній рядок) необов'язково писати, т.к. нерівність є зворотною операцією рівності. Якщо до цього ми мали так, що тип є кокретизацією іншоготипу(наприклад, [Int] є інстанцією типу [a]), то тепер тип може бути екземпляркласу(наприклад, Bool є інстанцією класу Eq). За цією ж аналогією можна написати функції рівності тих двійкових дерев, що ми використовували вище. Наприклад, для Tree2:
Для (Tree3 a b) ми вже повинні будемо накладати умову як на a, так і на b, тобто instance (Eq a, Eq b) => Eq (Tree3 a b)
Все що лівіше за символ => називається контекстом, що правіше цього символу має бути або базовим типом (Int,Bool. ), або конструктори типів (Tree a, [. ]. ). Оператор (==) є перевантаженою функцією (ad-hoc поліморфія).
Рівність (==) є типозалежною властивістю, яка потребує реалізації під кожен тип (наприклад реалізація рівності двійкових дерев). Хотілося б, щоб можна було порівнювати дві функції таким чином:
Це вимагало б у Haskell написання такого коду:
Чи можливо написати таку функцію, яка видавала б результат рівності двохбудь-якихфункцій (True або False)? На жаль, із тези Черча-Тьюринга випливає, що рівність двох будь-яких функцій не можна визначити. Не існує алгоритму, який би для двох будь-яких даних функцій завжди і через кінцеву кількість кроків вирішував, чи є дві функції рівними чи ні. Такий алгоритм не можна запрограмувати жодною мовою програмування.
Замість реалізації своєї функції для рівності, наприклад, двійковихдерев, можна завжди помістити ті класи, які успадковуються цим типом автоматично після ключового слова deriving. Тобто ми могли б спокійно написати:
Це дозволяє нам не писати власноруч інстанцію класу Eq ( instance Eq a => Eq (Tree a) where . ). Але для будь-якої функції тоді доведеться накладати умову на змінну a , що ця змінна є елементом класу Eq. Іноді, все-таки доводиться самому писати ці функції, оскільки «автоматичне» порівняння який завжди працює оскільки ми цього хотіли. Наприклад для двійкового дерева
буде реалізована (автоматично) наступна функція:
Як ми бачимо, перший аргумент Node3 був опущений, чого нам не хотілося б у деяких випадках.
Висновок
Тільки зареєстровані користувачі можуть брати участь в опитуванні. Заходьте будь ласка.