Изоморфизм спешит на помощь

в 8:40, , рубрики: изоморфизм, математика, ооп, Программирование, функциональное программирование

«Изоморфизм» — одно из базовых понятий современной математики. На конкретных примерах на Haskell и C# я не только растолкую теорию для нематематиков (не используя при этом никаких непонятных математических символов и терминов), но и покажу как этим можно пользоваться в повседневной практике.

Проблема в том, что строгое равенство (например, 2 + 2 = 4) часто оказывается излишне строгим. Вот пример:

Haskell

add :: (a, a) -> a
add (x, y) = x + y

C#

int Add(Tuple<int, int> pair) {
  return pair.Item1 + pair.Item2;
}

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

Haskell

add' :: a -> a -> a
add' x = y -> x + y

C#

Func<int, int> Add_(int x) {
  return y => x + y;
}

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

  • первая функция сразу возвращает сумму (т.е. выполняет вычисление в момент вывоза),
  • в то время как вторая функция возвращает другую функцию (которая в конце-концов вернет сумму — если ее кто-то вызовет, конечно, иначе никакого вычисления выполнено не будет: это пример отложенного вычисления и здесь тоже не обошлось без изоморфизма, к которому я вернусь чуть позднее).

А это и есть «быть излишне строгим».

Изоморфизм же «достаточно строг»; он не требует полного, всеохватывающего равенства, но ограничивается равенством "в некотором смысле", который всегда обусловлен определенным контекстом.

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

Haskell

curry :: ((a, b) → c) → a → b → c
curry f x y = f (x, y),
uncurry :: (a → b → c) → (a, b) → c
uncurry f (x, y) = f x y

C#

Func<TArg1, Func<TArg2, TRes>> Curry(Func<Tuple<TArg1, TArg2>, TRes> uncurried) {
  return arg1 => arg2 => uncurried(Tuple.Create(arg1, arg2));
}
Func<Tuple<TArg1, TArg2>, TRes> Uncurry(Func<TArg1, Func<TArg2, TRes>> curried) {
  return pair => curried(pair.Item1)(pair.Item2);
}

… и теперь для любых x, y:

Haskell

curry add $ x, y = uncurry add' $ (x, y)

C#

Curry(Add)(x)(y) = Uncurry(Add_)(Tuple.Create(x, y))

Чуть больше математики для особо любознательных

На самом деле должно было бы выглядеть вот так:

Haskell

curry . uncurry = id
uncurry . curry = id
id x = x

C#

Compose(Curry, Uncurry) = Id
Compose(Uncurry, Curry) = Id, где:
T Id<T>(T arg) => arg;
Func<TArg, TFinalRes> Compose<TArg, TRes, TFinalRes>(
  Func<TArg, TRes> first, 
  Func<TRes, TFinalRes> second) {
  return arg => second(first(arg));
}
...или как extension-метод (определение функции Id остается таким же):
Curry.Compose(Uncurry) = Id
Uncurry.Compose(Curry) = Id, где:
public static Func<TArg, TFinalRes> Compose<TArg, TRes, TFinalRes>(
  this Func<TArg, TRes> first, 
  Func<TRes, TFinalRes> second) {
  return arg => second(first(arg));
}

Id следует понимать как "ничего не произошло". Поскольку изоморфизм это двухсторонний преобразователь по определению, то всегда можно 1) взять что-то одно, 2) преобразовать это в другое и 3) преобразовать обратно в первое. Таких операций можно проделать всего две: потому что на первом этапе (№1) выбор всего лишь из двух вариантов. И в обоих случаях операция должна приводить ровно к тому же результату, как если бы вообще ничего не происходило (именно по этой причине задействовано строгое равенство — потому что вообще ничего не изменилось, а не "что-то" не изменилось).

Вдобавок к этому, существует теорема о том, что id элемент всегда уникален. Обратите внимание, что функция Id — generic, полиморфна и потому действительно уникальна по отношению к каждому конкретному типу.

Изоморфизм оказывается очень и очень полезным именно потому, что строг, но не слишком. Он сохраняет определенные важные свойства (в примере выше — одинаковый результат при одинаковых аргументах), при этом позволяя свободно трансформировать сами структуры данных (носители изоморфных поведения и свойств). И это абсолютно безопасно — ведь изоморфизм всегда работает в обе стороны, а значит всегда можно вернуться обратно без потери тех самых "важных свойств". Приведу другой пример, который настолько полезен на практике, что даже положен в основу многих "продвинутых" языков программирования типа того же Haskell'я:

Haskell

toLazy :: a -> () -> a
toLazy x = _ -> a

fromLazy :: (() -> a) -> a
fromLazy f = f ()

C#

Func<TRes> Lazy(TRes res) {
  return () => res;
}
TRes Lazy(Func<TRes> lazy) {
  return lazy();
}

Этот изоморфизм сохраняет сам результат отложенного вычисления — это и есть "важное свойство", в то время как структуры данных — разные.

Вывод? ООП, особенно строго типизированное, (вынужденно) работает на уровне "строгого равенства". И потому — по следам приведенных примеров — часто бывает излишне строгим. Когда ты привыкаешь мыслить "излишне строго" (а это происходит незаметно — помалу просачивается в программиста, особенно если он не ищет вдохновения в математике), твои решения невольно теряют желанную (или, по крайней мере, объективно возможную) гибкость. Понимание изоморфизма — в содружестве с осознанной попыткой быть внимательнее к своему
и чужому коду — помогает четче определять круг "важных свойств", абстрагируясь от излишних деталей: а именно, от конкретных структур данных, на которых эти "важные свойства" запечатлены (они же — "детали реализации", если уж на то пошло). В первую очередь — это способ мыслить и уже только потом — более удачные (микро)архитектурные решения и, как естественное следствие, переиначенный подход к тестированию.

P.S. Если увижу, что статья принесла пользу, то вернусь к темам "более удачных (микро)архитектурных решений" и "переиначенному подходу к тестированию".

Автор: f2heartz

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js