Конструкторы данных и обобщающий полиморфизм. Ещё раз про Нидельмана-Вунша

Полезные ссылки

В учебнике LYAH мы прошли 8-ую главу до слов derived instances, однако ничто не мешает нам освежить в памяти понятие типов, про которое вся 3-ая глава.

Репозиторий с примерами из класса

Конспект

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

   1 -- Параметры алгоритма, их меняет пользователь
   2 gap_penalty = -3
   3 weight x y = abs (x - y)
   4 
   5 -- Сам алгоритм
   6 align [] ys = gap_penalty * length ys
   7 align xs [] = gap_penalty * length xs
   8 align (x:xs) (y:ys) =
   9         maximum [aligned, left, right]
  10         where
  11                 aligned = weight x y + align xs ys
  12                 left = gap_penalty + align xs (y:ys)
  13                 right = gap_penalty + align (x:xs) ys

Если мы начали запутываться, вероятно, можно подобрать более удобные инструменты, чтобы было проще не запутаться. В данном случае, кажется, стоит подобрать более удобный способ хранения разных комбинаций данных.

Преобразования числовых типов

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

align.hs:11:29:
    Couldn't match expected type ‘Integer’ with actual type ‘Int’
    In the second argument of ‘(*)’, namely ‘length ys’
    In the expression: gap_penalty * length ys

align.hs:12:29:
    Couldn't match expected type ‘Integer’ with actual type ‘Int’
    In the second argument of ‘(*)’, namely ‘length xs’
    In the expression: gap_penalty * length xs

Проще всего договориться с собой для всей программы использовать тип Integer (он бесконечно вместительный), и везде, где возникают проблемы, преобразовывать целые числа в него. Для таких преобразований есть маленькая гора функций: toInteger, fromInteger, fromIntegral, для целых, и toRational, fromRational.

Если поискать проблему, мы обнаружим, что она в том, что функция length возвращает тип Int:

   1 *Main> :t length
   2 length :: [a] -> Int

В таком случае, не будем пользоваться length, а сделаем функцию len, которая будет возвращать правильный тип:

   1 len xs = toInteger $ length xs

Конструкторы данных

Для этого в хаскеле служит конструкция data ИмяТипа = ИмяКонструктора ТипАргумента ТипАргумента ... deriving Show

Она определяет новый тип данных с данным именем и функцию-конструктор, которая создаёт объекты этого типа данных.

Единственное, что мы можем делать с объектами такого типа – это разбирать их на части с помощью pattern-matching.

   1 data Point = XY Integer Integer deriving Show
   2 point_x (XY x y) = x

Конструктор – это обычная функция:

*Main> :t XY
XY :: Integer -> Integer -> Point
*Main> XY 2 3
XY 2 3
*Main> :t XY 2 3
XY 2 3 :: Point

Например, мы хотим представлять предложение как его текст + несколько чисел, описывающих его (например, число существительных и число глаголов). Тогда мы можем описать тип данных Sentence и переопределить weight так, чтобы он вынимал из предложений только их числовые характеристики и считал из них ответ:

   1 data Sentence = Sentence String Integer Integer
   2         deriving Show
   3 
   4 -- Параметры алгоритма, их меняет пользователь
   5 gap_penalty = -3
   6 weight (Sentence _ n1 v1) (Sentence _ n2 v2) =
   7         (n1 - n2)^2 + (v1 - v2)^2
   8 
   9 -- Сам алгоритм
  10 align [] ys = gap_penalty * len ys
  11 align xs [] = gap_penalty * len xs
  12 align (x:xs) (y:ys) =
  13         maximum [aligned, left, right]
  14         where
  15                 aligned = weight x y + align xs ys
  16                 left = gap_penalty + align xs (y:ys)
  17                 right = gap_penalty + align (x:xs) ys
  18 
  19 len xs = toInteger $ length xs

В консоли мы теперь можем:

   1 Prelude> :load "align.hs"
   2 [1 of 1] Compiling Main             ( align.hs, interpreted )
   3 Ok, modules loaded: Main.
   4 *Main> align [Sentence "Hello" 0 1] [Sentence "Привет" 0 1]
   5 0

Обобщающий полиморфизм

Ещё одна возможность с конструкторами данных: не описывать их структуру целиком сразу, а оставлять в них некое место, в которое можно положить что угодно. Но так как хаскель требует, чтобы всё было названо своим именем и у всего был тип, то мы должны сказать ему, что если нам дадут некий тип a, то тогда мы сможем определить наш конструктор, который будет хранить аргументы типа a.

Например, если мы хотим хранить точки либо из целых чисел, либо из дробных чисел, мы можем написать так:

   1 data Point a = XY a a deriving Show
   2 point_x (XY x y) = x
   3 
   4 integer_zero = XY 0 0
   5 float_zero = XY 0.0 0.0

Теперь, если мы посмотрим на тип конструктора, мы увидим:

   1 *Main> :t XY
   2 XY :: a -> a -> Point a

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

Таким образом, эту запись можно прочитать так: если мне на вход дадут какой-нибудь тип a, то я могу определить XY как функцию, берущую на вход два аргумента типа a, и возвращающую значение типа Point a.

Альтернативные конструкторы

Ещё одна возможность с конструкторами данных: говорить, что в нашем типе данных есть несколько конструкторов. (Но в любом случае мы их все должны перечислять при определении типа). В таком случае разнообразные конструкторы перечисляются через вертикальную черту.

Например, если мы хотим, чтобы наш алгоритм можно было применять к выравниванию как предложений, так и любых других данных, подменяя всякий раз лишь только весовую функцию, мы можем определить понятие "одной позиции в выравнивании" как либо установление соответствия между двумя какими-то элементами, либо пропуск с одной из сторон:

   1 data AlignPair a = Aligned a a | LeftGap a | RightGap a deriving Show

С таким определением мы можем посмотреть на его тип, и попробовать обернуть в его конструктор разные данные:

   1 *Main> :t Aligned
   2 Aligned :: a -> a -> AlignPair a
   3 *Main> Aligned 1 2
   4 Aligned 1 2
   5 *Main> Aligned (Sentence "OMG they killed Kenny!" 4 1) (Sentence "Они убили Кенни!" 2 1)
   6 Aligned (Sentence "OMG they killed Kenny!" 4 1) (Sentence "\1054\1085\1080 \1091\1073\1080\1083\1080 \1050\1077\1085\1085\1080!" 2 1)
   7 *Main> :t Aligned (Sentence "OMG they killed Kenny!" 4 1) (Sentence "Они убили Кенни!" 2 1)
   8 Aligned (Sentence "OMG they killed Kenny!" 4 1) (Sentence "Они убили Кенни!" 2 1)
   9   :: AlignPair Sentence

Вывод типов

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

это простые типы (например, Int, Integer, Char, Float, Bool)
это типы с аргументами (например, AlignPair Integer Integer или [Char])
это функции (например, [a] -> Int)

У хаскеля есть несколько источников знаний о том, у чего какой тип:

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

Теперь, глядя, например, на выражение Aligned 1 b хаскель сразу знает, что:

1 :: Integer (я чуть-чуть упрощаю)
Aligned :: a -> a -> Aligned a
теперь он может подставить тип для 1 в определение типа для Aligned и тем самым задать значение для переменной aб чтобы она обрела вид конкретного типа; теперь вся конструкция имеет тип Aligned 1 b :: Integer -> Integer -> Aligned Integer
из этого хаскель делает вид, что и переменная b может иметь только тип Integer

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

   1 *Main> Aligned True "hello"
   2 
   3 <interactive>:29:14:
   4     Couldn't match expected type ‘Bool’ with actual type ‘[Char]’
   5     In the second argument of ‘Aligned’, namely ‘"hello"’
   6     In the expression: Aligned True "hello"
   7     In an equation for ‘it’: it = Aligned True "hello"

Выбор лучшего ответа

В прошлой версии функции align в качестве ответа мы выдавали только вес выравнивания, а выбор лучшего ответа могла делать функция maximum. Теперь у нас ситуация сложнее, и мы должны описывать выбор лучшего ответа сами:

   1 data AlignPair a =
   2         Aligned a a | LeftGap a | RightGap a
   3         deriving Show
   4 
   5 data Alignment a =
   6         Alignment [AlignPair a] Integer
   7         deriving Show
   8 
   9 -- Получаем на вход несколько выравниваний,
  10 -- выбираем лучший
  11 best_alignment :: [Alignment x] -> Alignment x
  12 best_alignment [] = undefined "Need more alternatives!"
  13 best_alignment [a] = a
  14 best_alignment ((Alignment t1 w1):xs) =
  15         if w1 > w2
  16                 then Alignment t1 w1
  17                 else Alignment t2 w2
  18         where
  19                 Alignment t2 w2 = best_alignment xs

На том пока и остановимся...

Kodomo

Пользователь