Как написать функтор в Elixir

В Elixir есть функция Enum.map, которая работает с несколькими типами коллекций, но она не без проблем.

В этой заметке я познакомлю вас с концепцией из функционального программирования, называемой функтором. Мы создадим протокол Functor с функцией fmap, которая будет стремиться стать лучшей версией Enum.map.

Примечание: Статья написана под влиянием библиотеки Witchcraft, о которой мы рассказывали в одном из наших предыдущих постов.

Но сначала: в чем проблема с Enum.map?

Проблема с Enum.map в Elixir

Хотя Enum.map отлично работает со списками, его поведение немного странно для других коллекций.

iex(1)> cities = %{"Latvia" => "Riga", "France" => "Paris", "Germany" => Berlin}
%{"France" => "Paris", "Germany" => Berlin, "Latvia" => "Riga"}
iex(2)> cities = Enum.map(cities, fn x -> x end)
[{"France", "Paris"}, {"Germany", Berlin}, {"Latvia", "Riga"}]
Вход в полноэкранный режим Выход из полноэкранного режима

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

И мы не можем использовать результат в качестве карты.

iex(2)> Map.fetch(cities, "Latvia")
** (BadMapError) expected a map, got: [{"France", "Paris"}, {"Germany", "Berlin"}, {"Latvia", "Riga"}]
    (stdlib 3.17) :maps.find("Latvia", [{"France", "Paris"}, {"Germany", "Berlin"}, {"Latvia", "Riga"}])
Вход в полноэкранный режим Выход из полноэкранного режима

Понимание того, как Enum.map работает с картами, зависит от знания двух вещей:

  1. Elixir воспринимает карты как списки кортежей (но только когда хочет этого).

Можно сказать, что это не интуитивно понятно. Но что может быть лучше, и как сделать так, чтобы не повторять эту ошибку?

Давайте посмотрим, как в этом может помочь вектор.

Что такое вектор в Haskell?

В языке Haskell Functor — это класс типов, «интерфейс» с набором методов, общих для нескольких типов данных.

-- Definition for illustrative purposes.

class Functor f where
  fmap :: (a -> b) -> f a -> f b
  (<$) :: a -> f b -> f a
Вход в полноэкранный режим Выход из полноэкранного режима

Ближе всего к типовым классам в Elixir находятся протоколы. Точно так же, как в Elixir есть Enumerable (Enum), вы можете думать о Functor как о Functor-able, или, говоря более человеческим языком, Mappable.

Важным методом типокласса Functor в Haskell является fmap.

fmap

fmap принимает функцию и структуру, а затем возвращает ту же структуру с функцией, примененной к содержимому структуры.

Другими словами, она реализует преобразование, сохраняющее структуру.

fmap похож на Enum.map, но есть несколько ключевых отличий:

  • Она позволяет отображать более широкий набор структур. Например, в Haskell вы можете использовать fmap с одноэлементными структурами (такими как {:ok, result}) и даже с функциями.

Примечание: В Haskell fmap принимает функцию в качестве первого аргумента. Но поскольку в Elixir из-за труб данные обычно находятся в первой позиции, я поменял аргументы местами при адаптации концепции.

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

iex(1)> import Functor
Functor
Вход в полноэкранный режим Выход из полноэкранного режима

Списки

iex(2)> fmap([1, 2, 3], fn x -> x + 1 end)
[2, 3, 4]
Вход в полноэкранный режим Выход из полноэкранного режима

Карты

iex(3)> cities = %{"Latvia" => "riga", "France" => "paris", "Germany" => "berlin"}
%{"France" => "paris", "Germany" => "berlin", "Latvia" => "riga"}
iex(4)> fmap(cities, fn x -> String.capitalize(x) end)
%{"France" => "Paris", "Germany" => "Berlin", "Latvia" => "Riga"}
Войти в полноэкранный режим Выйти из полноэкранного режима

Деревья

iex(5)> a = %Tree{value: 1, children: [%Tree{value: 2, children: []}, %Tree{value: 3, children: []}]}
%Tree{
  children: [%Tree{children: [], value: 2}, %Tree{children: [], value: 3}],
  value: 1
}
iex(6)> fmap(a, fn x -> x + 1 end)
%Tree{
  children: [%Tree{children: [], value: 3}, %Tree{children: [], value: 4}],
  value: 2
}
Войти в полноэкранный режим Выйти из полноэкранного режима

Кортежи результатов

iex(7)> fmap({:ok, 4}, fn x -> x + 3 end)
{:ok, 7}
iex(8)> fmap({:error, :not_a_number}, fn x -> x + 3 end)
{:error, :not_a_number}
Войти в полноэкранный режим Выйти из полноэкранного режима

Если вы посмотрите на эти примеры, то увидите, что все они имеют некоторое значение (значения), завернутое в структуру. fmap использует предоставленную нами функцию для изменения значения (значений), сохраняя структуру неизменной.

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

@spec fmap(f(a), (a -> b)) :: f(b)
Вход в полноэкранный режим Выйти из полноэкранного режима

Требуется:

  1. что-то типа a, обернутое в тип f
  2. функцию от типа a к типу b.

И возвращает значение типа b, обернутое в тип f.

Законы функторов в Elixir

Для достижения своей цели fmap должен следовать ряду законов уравнения. И если законы вас пугают — пожалуйста, пропустите это, посмотрите на реализацию, затем вернитесь, и все станет проще.

В Haskell компилятор не проверяет эти законы по умолчанию, но вы должны следовать им, чтобы реализация «имела смысл».

Первый закон гласит, что если у вас есть функция, которая возвращает свой вывод нетронутым, то «fmapping» сделает то же самое.

fmap(y, fn x -> x end) == y
Вход в полноэкранный режим Выход из полноэкранного режима

Второй закон гласит, что составление двух ‘fmaps’ — это то же самое, что и ‘fmapping’ композиции этих функций.

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

(fmap(x, f1) |> fmap (f2)) == (fmap(x, fn y -> f2(f1(y)) end))
Вход в полноэкранный режим Выход из полноэкранного режима

Законы неудобно выражать в Elixir, но в основном они работают для сохранения структуры типа, над которым вы проводите отображение.

Реализация Enum.map для карт, например, удовлетворяет второму закону, но не удовлетворяет первому. Следовательно, она не является законной реализацией fmap.

Почему вам нужно знать о функциональных векторах?

В программировании некоторые закономерности повторяются снова и снова.

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

  1. Решайте проблемы быстрее
  2. Расширяйте «инструменты для размышлений
  3. Сделать коммуникацию проще.

Функтор — это тоже паттерн, так же как синглтон и фабрика.

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

Давайте рассмотрим пример. В Elixir большая часть нашего кода выражается в конвейерах, которые можно рассматривать как серию преобразований данных. Это очень удобно для чтения: одна из главных причин, почему синтаксис Elixir так привлекателен.

Функторы могут помочь нам сделать наш код еще лучше двумя способами.

Во-первых, функторы выражают преобразования коллекций данных, которые можно передавать по трубам. Если у нас есть функция fmap, которая возвращает одну и ту же обертку, мы можем легко вставлять преобразования друг в друга без вызова Enum.into() между ними.

Во-вторых, функторы также помогают преобразовывать вложенные значения в конвейерах. Если функция возвращает тип данных с более сложной структурой, например {:ok, result}/{:error, error}, мы иногда сталкиваемся с проблемами при конвейерной обработке. Чтобы обработать значение, нам нужно либо деконструировать его, либо написать функцию, которая обрабатывает структуру и выполняет преобразование за сценой.

Первый вариант может привести к таким ужасам, как переход к операторам case в середине конвейера, а второй может внести много дублирования кода и сделать код более непонятным.

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

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

Моделирование функторов в Elixir

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

Настройка

Для этого урока нам понадобится новый проект Elixir.

mix new functor
Войдите в полноэкранный режим Выйти из полноэкранного режима

И файл с именем functor.ex.

Создайте протокол Functor.

Это довольно просто.

Сначала мы открываем functor.ex. Затем мы используем макрос defprotocol для создания протокола.

Мы предоставляем макросу функции, которые будут у протокола. В нашем случае единственной функцией является fmap.

defprotocol Functor do
  def fmap(a, f)
end
Вход в полноэкранный режим Выйти из полноэкранного режима

Это все, что нам нужно сделать.

Создание реализации для списков

Конечно, протокол хорош лишь настолько, насколько хороши его реализации.

Мы можем создавать новые реализации для протокола с помощью макроса defimpl. Давайте сделаем список прямо внутри functor.ex, поскольку список — это основной тип данных.

fmap для списков — то же самое, что и обычная карта. Поэтому для реализации мы просто воспользуемся :lists.map из дедушки Erlang.

defimpl Functor, for: List do
  @spec fmap(list, (list -> list)) :: list
  def fmap(a, f), do: :lists.map(f, a)
end
Вход в полноэкранный режим Выход из полноэкранного режима

Вот как fmap работает для списков:

iex(1)> Functor.fmap([1,2,3], fn x -> x + 1 end)
[2, 3, 4]
Войти в полноэкранный режим Выход из полноэкранного режима

Создание реализации для карт

Теперь мы подошли к типу данных, который мы упоминали в начале статьи.

Самый простой способ заставить Enum.map() возвращать карту — это упаковать ее обратно в карту после отображения.

defimpl Functor, for: Map do
  def fmap(a, f), do: Enum.map(a, f) |> Enum.into(%{})
end
Вход в полноэкранный режим Выход из полноэкранного режима

Но здесь есть небольшая проблема. Она может легко завершиться неудачей.

iex(1)> Functor.fmap(%{Netherlands: "Amsterdam"}, fn {k, v} -> v end)
** (ArgumentError) argument error
    (stdlib 3.17) :maps.from_list(["Amsterdam"])
    (elixir 1.13.0) lib/enum.ex:1448: Enum.into_map/1
Вход в полноэкранный режим Выход из полноэкранного режима

Это одна из причин, почему Enum.map() на картах возвращает списки. Функция, которую вы предоставили, может создать что-то, что уже не является картой.

Это также не правильная реализация функтора. Функторы могут изменять только одно значение: они могут отображать либо ключи, либо значения, и мы должны выбрать одно из них для реализации.

Мы можем решить обе эти проблемы одновременно, ограничив операцию отображения только значениями.

defimpl Functor, for: Map do
  def fmap(a, f) do
    map_in_list = Map.to_list(a)

    :lists.map(fn {k, v} -> {k, f.(v)} end, map_in_list)
    |> Enum.into(%{})
  end
end
Вход в полноэкранный режим Выход из полноэкранного режима

Вот как это работает:

iex(1)> Functor.fmap(%{Netherlands: "Amsterdam"}, fn x -> x <> "!" end)
%{Netherlands: "Amsterdam!"}
Вход в полноэкранный режим Выход из полноэкранного режима

Есть некоторые аргументы против такой реализации (даже если это правильный функтор 😅). Если функция map работает только со значениями, это может быть так же неинтуитивно понятно, как если бы она возвращала список.

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

Создание реализации для деревьев

Теперь, когда мы увидели, как определить fmap для более простых типов данных, давайте попробуем определить его для типа, не обслуживаемого протоколом Enum — деревьев.

Прежде всего, нам нужно определить структуру. Мы сделаем это в structures.ex.

defmodule Tree do
  defstruct value: nil, children: []

  @type t() :: %__MODULE__{
          value: any(),
          children: [t()]
        }
end
Вход в полноэкранный режим Выход из полноэкранного режима

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

Теперь мы можем определить реализацию Functor внутри модуля. В определении мы можем пропустить for: Tree — Elixir будет знать, что мы имеем в виду модуль struct.

defmodule Tree do
  # ...
  defimpl Functor do

  end
end
Вход в полноэкранный режим Выход из полноэкранного режима

Осталось только написать реализацию, которая будет рекурсивной.

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

def fmap(%Tree{value: value, children: []}, f), do: %Tree{value: f.(value), children: []}
Вход в полноэкранный режим Выход из полноэкранного режима

Если у узла есть дочерние элементы, нам нужно отобразить эту fmap на все из них. Это дает нам прекрасную возможность использовать Functor.fmap, который мы создали ранее!

def fmap(%Tree{value: value, children: children}, f) do
  updated_children = Functor.fmap(children, fn x -> fmap(x, f) end)
  %Tree{value: f.(value), children: updated_children}
Вход в полноэкранный режим Выход из полноэкранного режима

Если вы поняли приведенный выше кусок кода, то вы уже достигли определенного уровня просветления относительно функторов ☯.

Вот как работает эта функция:

iex(1)> a = %Tree{value: 1, children: [%Tree{value: 2, children: []}, %Tree{value: 3, children: []}]}
%Tree{
  children: [%Tree{children: [], value: 2}, %Tree{children: [], value: 3}],
  value: 1
}
iex(2)> Functor.fmap(a, fn x -> x + 1 end)
%Tree{
  children: [%Tree{children: [], value: 3}, %Tree{children: [], value: 4}],
  value: 2
}
Войти в полноэкранный режим Выход из полноэкранного режима

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

Создание реализации для кортежей результатов

Наконец, давайте посмотрим, как мы можем реализовать fmap для кортежей результатов.

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

В Elixir функции иногда возвращают одно из {:ok, result} или {:error, error}. Мы можем назвать это контекстом вычисления, которое могло быть успешным или неудачным.

Теперь представьте, что мы хотим применить к этому результату функцию, такую как fn x -> x + 1 end.

Мы можем либо:

  • Распаковать его с помощью сопоставления с образцом и обработать ошибку прямо здесь и сейчас.
  • Поднять функцию внутри контекста возможной ошибки и отправить результат куда-нибудь дальше.

С этим кортежем довольно просто сделать второе. Если у нас есть {:ok, result}, мы просто применим функцию к результату. Если у нас есть {:error, error}, мы не применяем функцию, а просто передаем ошибку.

Но есть некоторые проблемы с реализацией функтора.

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

Поскольку Elixir не может разгадать наши намерения, это означало бы сделать что-то практичное, но немного незаконное.

Но поскольку «практично, но немного незаконно» звучит как лучшая характеристика Elixir, которую я читал, мы все равно сделаем это.

defimpl Functor, for: Tuple do
  def fmap({:ok, result}, f), do: {:ok, f.(result)}
  def fmap({:error, reason}, _f), do: {:error, reason}
end
Вход в полноэкранный режим Выход из полноэкранного режима

Вот как это работает:

iex(2)> fmap({:ok, 4}, fn x -> x + 3 end)
{:ok, 7}
iex(3)> fmap({:error, :not_a_number}, fn x -> x + 3 end)
{:error, :not_a_number}
Вход в полноэкранный режим Выход из полноэкранного режима

Законным, но неидиоматичным способом сделать это в Elixir было бы создание двух структур — %Result.Ok{} и %Result.Err{} — и определение реализации fmap для них.
В качестве упражнения вы можете попробовать сделать это самостоятельно.

Полезны ли функторы в Elixir?

Теперь, когда мы создали базовый, но работающий протокол для функторов, уместно спросить: а полезна ли эта штука?

Ну, она довольно симпатичная. С его помощью мы можем делать некоторые классные вещи, например, создать функцию map, которая работает как со списком деревьев, так и с деревом списков.

def mega_map(a, f) do
  Functor.fmap(a, fn x -> Functor.fmap(x, f) end)
end
Вход в полноэкранный режим Выход из полноэкранного режима

А когда мы добавим еще пару реализаций, нам пригодится функция отображения, которая работает с несколькими типами данных (например, Enum.map), но не всегда возвращает список.

Но сила идей, вдохновленных Хаскелем, пропорциональна инфраструктуре, которую вы имеете для работы с ними. Давайте подумаем об этом как об оптимизационном упражнении. Мы уходим от локальной идиоматической вершины Elixir, чтобы написать код, который будет более выразительным и интуитивно понятным.

В Haskell у вас есть доступ к тонне других «математических» типоклассов, таких как Applicative, Monad и т.д., которые помогут вам написать код, разительно отличающийся от Elixir. И это намного проще благодаря системе типов и другим периферийным устройствам.

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

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

В частности, в последнее время я полюбил видение Witchcraft о том, как может выглядеть синтаксис Elixir. Он предоставляет пользовательские операторы, которые работают по принципу трубы. Например, вы можете использовать ~> вместо |> fmap.

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

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

Подведение итогов и дальнейшее обучение

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

Если вам интересно попробовать больше магии функторов в Elixir, ознакомьтесь с Witchcraft, который был моим главным вдохновением для этой статьи.

А если вы хотите глубже погрузиться в мир типизированного функционального программирования, вам определенно стоит попробовать Haskell. Лучший способ сделать это — начать с одной из этих книг: Haskell Programming From First Principles или Get Programming With Haskell.

До следующего раза, счастливого кодинга!

P.S. Если вы хотите читать посты Elixir Alchemy сразу после их выхода из печати, подпишитесь на нашу рассылку Elixir Alchemy и не пропустите ни одного поста!

Оцените статью
devanswers.ru
Добавить комментарий