Практика 5. Типы данных

Тип или конструктор?

data CatT = CatD String Int
data Pet = Cat CatT | Dog String Int | Parrot

ghci> :t Dog
Dog :: String -> Int -> Pet
ghci> :t Parrot
Parrot :: Pet

Возраст: что делать с попугаем?

age :: Pet -> Maybe Int
age pet = case pet of
  Dog _ age -> Just age
  Cat (CatD _ age) -> Just age
  -- допишите недостающую ветку

  Parrot -> Nothing

• Δ Полнота сопоставления: учтены все конструкторы

Напишите сумму значений дерева

sumTree :: Tree Int -> Int
sumTree t = case t of
  Leaf x -> x
  Node l x r -> sumTree l + x + sumTree r

Меняем значения, сохраняем дерево

transform :: (a -> b) -> Tree a -> Tree b
transform f t = case t of
  Leaf x -> Leaf ____________
  Node l x r -> Node __________________________ ____________ __________________________

transform f t = case t of
  Leaf x -> Leaf (f x)
  Node l x r -> Node (transform f l) (f x) (transform f r)

• Схема рекурсии прежняя; результаты теперь собираются обратно в дерево
• Высота не меняется: height (transform f t) == height t

Предскажите кайнд

ghci> :kind Tree
Tree :: * -> *
ghci> :kind Tree Bool
Tree Bool :: *
ghci> :kind Either String
Either String :: * -> *
ghci> :kind Either String Int
Either String Int :: *

• :t спрашивает тип терма; :k спрашивает кайнд типа
• Node — конструктор данных; Tree — конструктор типа

Список: две ветки, одно поддерево

-- Схематически: встроенный список устроен так
-- data List a = Nil | Cons a (List a)
[]       -- пустой список
x : xs   -- голова и хвост

safeHead :: [a] -> Maybe a
safeHead xs = case xs of
  [] -> ______________
  x : _ -> ______________

  [] -> Nothing
  x : _ -> Just x

Дуплицирование элементов списка

dupEvens :: [a] -> [a]
dupEvens = concat . map f . zip [0..]
  where
    f :: (Int, a) -> [a]
    f (i, x) = if odd i then [x] else [x, x]

type или newtype?

type ModuleId = Int
type CourseId = Int

newtype ModuleId = ModuleId Int
newtype CourseId = CourseId Int

Спроектируйте опции командной строки

data Mode = HelpMode | RunMode
data Format = Plain | JSON
data BadOptions = BadOptions Mode (Maybe Format) (Maybe FilePath)

Что вы теперь умеете

• Уметь читать декларации алгебраических типов данных
• Пользоваться сопоставлением с образцом
• Писать рекурсию по дереву и списку
• Различать терм, тип и кайнд
• Выбирать Maybe, type и newtype по смыслу задачи
• Выражать допустимые состояния суммой и произведением типов

Если тип применили неправильно

ghci> :kind Maybe Maybe
<interactive>:1:7: error: [GHC-83865]
    • Expecting one more argument to ‘Maybe’
      Expected a type, but ‘Maybe’ has kind ‘* -> *’
    • In the first argument of ‘Maybe’, namely ‘Maybe’
      In the type ‘Maybe Maybe’

Maybe ждёт обычный тип, а ему передали конструктор типа.

Кайнды: дополнительные примеры

data Free f a = Pure a | Free (f (Free f a))
-- Free :: (* -> *) -> * -> *

data HFree f a = HPure a | HFree (f (HFree f) a)
-- HFree :: ((* -> *) -> * -> *) -> * -> *

Полиморфные типы и система \lambda\omega

type Pair a b = forall c. (a -> b -> c) -> c

Pair Int Char \equiv forall c. (Int -> Char -> c) -> c

\begin{aligned} &\mathbf{Pair} : * \to * \to * \\ &\mathbf{Pair} = \lambda \alpha^*\,\beta^*.\,\forall \gamma.\,(\alpha\to\beta\to\gamma)\to\gamma \\ &\mathbf{pair} : \forall \alpha\,\beta.\,\alpha\to\beta\to\mathbf{Pair}\ \alpha\ \beta \\ &\mathbf{pair} = \Lambda \alpha^*\,\beta^*.\,\lambda x^\alpha\,y^\beta.\,(\Lambda \gamma^*.\,\lambda f^{\alpha\to\beta\to\gamma}.\,f\ x\ y) \\ &\mathbf{fst} : \forall \alpha\,\beta.\,\mathbf{Pair}\ \alpha\ \beta\to\alpha \\ &\mathbf{fst} = \Lambda \alpha^*\,\beta^*.\,\lambda p^{\mathbf{Pair}\ \alpha\ \beta}.\,p\ \alpha\ (\mathbf{K}\ \alpha\ \beta) \end{aligned}

Records и coerce: подробности

• Селекторы полей могут быть частичными у типов-сумм
• Для полей используют префиксы; дополнительные варианты синтаксиса дают расширения GHC
• newtype позволяет разделить типы без дополнительной обёртки во время исполнения

import Data.Coerce (coerce)
intsToIds :: [Int] -> [CourseId]
intsToIds = coerce

Расширения records · Parse, don’t validate

Типы-произведения в C++

#include <string>
struct CatT {
    std::string name;
    int age;
};
CatT createBarsik() { return CatT{"barsik", 4}; }
std::string getName(const CatT& cat) { return cat.name; }

Поля — компоненты произведения; конструктор создаёт значение, доступ к полю извлекает компонент.

Типы-суммы в C

struct Pet {
    enum { CAT, DOG, PARROT } tag;
    union {
        struct { const char *name; int age; } cat;
        struct { const char *name; int age; } dog;
    } value;
};
/* tag и value должны согласовываться */
switch (pet.tag) {
case CAT:    printf("Cat: %s", pet.value.cat.name); break;
case DOG:    printf("Dog: %s", pet.value.dog.name); break;
case PARROT: printf("Parrot"); break;
}

Типы-суммы в C++

std::variant<Cat, Dog, Parrot> pet{Cat{"barsik", 4}};
if (std::holds_alternative<Cat>(pet)) {
    std::cout << "Cat " << std::get<Cat>(pet).name;
} else if (std::holds_alternative<Dog>(pet)) {
    std::cout << "Dog " << std::get<Dog>(pet).name;
} else if (std::holds_alternative<Parrot>(pet)) {
    std::cout << "Parrot";
}

std::variant

Типы-суммы в Python

class Pet: pass
class Cat(Pet):
    def __init__(self, name): self.name = name
class Dog(Pet):
    def __init__(self, name): self.name = name
class Parrot(Pet): pass

if isinstance(pet, Cat):
    print("Cat " + pet.name)
elif isinstance(pet, Dog):
    print("Dog " + pet.name)
elif isinstance(pet, Parrot):
    print("Parrot")
else:
    raise AssertionError("unreachable code")  # No exhaustiveness check

Типы-суммы в Kotlin

sealed class Pet
class Cat(val name: String) : Pet()
class Dog(val name: String) : Pet()
class Parrot : Pet()

fun showPet(pet: Pet): String = when (pet) {
    is Cat -> "Cat: " + pet.name
    is Dog -> "Dog: " + pet.name
    is Parrot -> "Parrot"
}

Иерархия sealed позволяет компилятору проверять полноту выражения when.

Что посмотреть в транспорте

• Parse, don’t validate
• (youtube) Тагир Валеев — Pattern matching в Java и его воображаемые друзья
• The algebra (and calculus!) of algebraic data types