Проблемы, вызванные определением кортежей как функторов

Очень удивительно (я бы даже сказал — внезапно!), но кортеж-пара в GHC является функтором. Это сложно понять, ведь функтор должен иметь только один параметр, а у пары их два. Можно восхищаться тем, как разработчики стандартной библиотеки GHC умудрились предоставить такую абстракцию, но мне кажется, полученное решение все же следует признать неудачным.

Начнем с того, что оно интуитивно непонятно. Скажем, попробуйте вычислить вручную, не используя инструментов GHC, выражение (1+) `fmap` (2, 3). А после этого проверьте полученный результат, например, в ghci. У многих ли результат ручного вычисления совпал с тем, который выдала система? И если у вас результаты все же совпали, мне очень хотелось бы услышать хорошее объяснение того, как именно вам это удалось.

Допустим, мы определяем класс Incable инкрементальных типов:

class Incable t where
    inc :: t -> t

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

instance (Num t) => Incable t where
    inc = (1+)

Однако такое определение потребует от нас включить расширение языка UndecidableInstances, а затем и вовсе запутает ситуацию. Поэтому ограничимся определениями только для самых основных представителей класса Num — типов Integer и Double.

instance Incable Integer where
    inc = (1+)
instance Incable Double where
    inc = (1+)

Очевидно, что для любого функтора можно определить экземпляр класса Incable:

instance (Functor f, Incable t) => Incable (f t) where
    inc = fmap inc

Это достаточно хорошее общее определение. Оно позволяет нам работать со списками, массивами, структурами Maybe и еще множеством типов, для которых определены экземпляры класса Functor. Среди всего этого разнообразия окажутся и пары инкрементальных значений. Однако, предположим (даже если мы нашли убедительное объяснение нынешнему поведению пар как функторов), что именно в нашем случае желательно, чтобы увеличивались сразу оба значения в паре. Было бы здорово определить экземпляр класса Incable для пар следующим образом:

instance (Incable t1, Incable t2) => Incable (t1, t2) where
    inc (x1, x2) = (inc x1, inc x2)

Увы, это невозможно. Конечно же, компиляция этого фрагмента пройдет успешно, но при попытке воспользоваться таким определением мы получим сообщение о перекрытии экземпляров:

ghci> inc (1, 2)
<interactive>:105:1:
    Overlapping instances for Incable (t0, t1)
      arising from a use of `inc'
    Matching instances:
      instance (Functor f, Incable t) => Incable (f t)
        -- Defined at src/Main.hs:16:10
      instance (Incable t1, Incable t2) => Incable (t1, t2)
        -- Defined at src/Main.hs:18:10
    In the expression: inc (1, 2)
    In an equation for `it': it = inc (1, 2)

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

Ситуация становится еще сложнее, если мы рассмотрим кортежи, в которых больше двух элементов, например, тройки. Что делать, если нам нужно вычислить что-то вроде inc (1.0, 2, 3)? Казалось бы, здесь у нас точно не должно возникнуть проблем — тройки не были определены как функторы, а значит, мы можем реализовать для них экземпляры класса Incable так, как считаем нужным:

instance (Incable t1, Incable t2, Incable t3) => Incable (t1, t2, t3) where
    inc (x1, x2, x3) = (inc x1, inc x2, inc x3)

И снова компиляция проходит успешно, а при выполнении возникает ошибка:

ghci> inc (1.0, 2, 3)
<interactive>:14:1:
    Overlapping instances for Incable (t0, t1, t2)
      arising from a use of `inc'
    Matching instances:
      instance (Functor f, Incable t) => Incable (f t)
        -- Defined at src/Main.hs:18:10
      instance (Incable t1, Incable t2, Incable t3) =>
               Incable (t1, t2, t3)
        -- Defined at src/Main.hs:20:10
    In the expression: inc (1.0, 2, 3)
    In an equation for `it': it = inc (1.0, 2, 3)

Ну вот, оказывается, что тройки тоже нельзя определить отдельно — они, как и пары, считаются разновидностью функторов. Может быть, наше определение инкрементальной тройки не нужно? Как бы не так! Уберем это определение и попробуем еще раз:

ghci> inc (1.0, 2, 3)
<interactive>:12:1:
    No instance for (Functor ((,,) t0 t1)) arising from a use of `inc'
    Possible fix:
      add an instance declaration for (Functor ((,,) t0 t1))
    In the expression: inc (1.0, 2, 3)
    In an equation for `it': it = inc (1.0, 2, 3)

Теперь нас просят определить тройку как функтор. Может быть, у нас получиться определить экземпляр класса Functor для тройки так, как нам нужно?

instance Functor ((,,) t1 t2) where
    fmap f (x1, x2, x3) = (fmap f x1, fmap f x2, fmap f x3)

Никоим образом, у нас не получиться даже скомпилировать такое определение:

[1 of 1] Compiling Main             ( src/Main.hs, interpreted )

src/Main.hs:19:36:
    Couldn't match expected type `b' with actual type `f0 b'
      `b' is a rigid type variable bound by
          the type signature for
            fmap :: (a -> b) -> (t1, t2, a) -> (t1, t2, b)
          at src/Main.hs:19:5
    In the return type of a call of `fmap'
    In the expression: fmap f x3
    In the expression: (x1, x2, fmap f x3)

src/Main.hs:19:43:
    Couldn't match expected type `a' with actual type `f0 a'
      `a' is a rigid type variable bound by
          the type signature for
            fmap :: (a -> b) -> (t1, t2, a) -> (t1, t2, b)
          at src/Main.hs:19:5
    In the second argument of `fmap', namely `x3'
    In the expression: fmap f x3
    In the expression: (x1, x2, fmap f x3)
Failed, modules loaded: none.

В качестве последнего шанса попробуем определить тройку как функтор по аналогии с парой:

instance Functor ((,,) t1 t2) where
    fmap f (x1, x2, x3) = (x1, x2, fmap f x3)

Увы, это определение не компилируется по той же причине, что и предыдущее:

[1 of 1] Compiling Main             ( src/Main.hs, interpreted )

src/Main.hs:19:36:
    Couldn't match expected type `b' with actual type `f0 b'
      `b' is a rigid type variable bound by
          the type signature for
            fmap :: (a -> b) -> (t1, t2, a) -> (t1, t2, b)
          at src/Main.hs:19:5
    In the return type of a call of `fmap'
    In the expression: fmap f x3
    In the expression: (x1, x2, fmap f x3)

src/Main.hs:19:43:
    Couldn't match expected type `a' with actual type `f0 a'
      `a' is a rigid type variable bound by
          the type signature for
            fmap :: (a -> b) -> (t1, t2, a) -> (t1, t2, b)
          at src/Main.hs:19:5
    In the second argument of `fmap', namely `x3'
    In the expression: fmap f x3
    In the expression: (x1, x2, fmap f x3)
Failed, modules loaded: none.

Обсуждение

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

Кроме того, определение пары как разновидности функторов не совсем логично. Принято считать, что функтор — это всегда тип, у которого есть только один параметр. В то же время, даже у простейшего кортежа (пары) уже два параметра. При этом совсем непонятно, почему в определении экземпляра класса Functor для пары указывается только один параметр, а не два?

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

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

class Functor2 f where
    fmap2 :: (a1 -> b1) -> (a2 -> b2) -> f a1 a2 -> f b1 b2

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

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

Выводы

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

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

instance Functor ((,,) t1 t2) where
    fmap f (x1, x2, x3) = (x1, x2, f x3)

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

instance Functor ((,,) t1 t2) where
    fmap f (x1, x2, x3) = (f x1, f x2, f x3)

Но он не компилируется, хотя и по несколько иной причине:

[1 of 1] Compiling Main             ( src/Main.hs, interpreted )

src/Main.hs:19:28:
    Couldn't match type `b' with `t2'
      `b' is a rigid type variable bound by
          the type signature for
            fmap :: (a -> b) -> (t1, t2, a) -> (t1, t2, b)
          at src/Main.hs:19:5
      `t2' is a rigid type variable bound by
           the instance declaration at src/Main.hs:18:10
    Expected type: t1
      Actual type: b
    In the return type of a call of `f'
    In the expression: f x1
    In the expression: (f x1, f x2, f x3)

src/Main.hs:19:30:
    Couldn't match type `t1' with `t2'
      `t1' is a rigid type variable bound by
           the instance declaration at src/Main.hs:18:10
      `t2' is a rigid type variable bound by
           the instance declaration at src/Main.hs:18:10
    Expected type: a
      Actual type: t1
    In the first argument of `f', namely `x1'
    In the expression: f x1
    In the expression: (f x1, f x2, f x3)

src/Main.hs:19:34:
    Couldn't match type `a' with `t2'
      `a' is a rigid type variable bound by
          the type signature for
            fmap :: (a -> b) -> (t1, t2, a) -> (t1, t2, b)
          at src/Main.hs:19:5
      `t2' is a rigid type variable bound by
           the instance declaration at src/Main.hs:18:10
    Expected type: t2
      Actual type: b
    In the return type of a call of `f'
    In the expression: f x2
    In the expression: (f x1, f x2, f x3)
Failed, modules loaded: none.

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

Тем не менее, я по-прежнему настаиваю, что определение пары как функтора на уровне системной библиотеки оказалось неудачным решением. В пользу этого говорит и то, что для других многопараметрических типов (например, кортежей более высокого порядка, карт и т.п.) экземпляры класса Functor в системной библиотеке не предоставлены. Я подозреваю, что разработчикам просто понадобилось поведение функтора для пар где-то «по месту», а затем они посчитали полезным поднять ее до уровня системы. Чтобы проверить эту версию, проще всего пересобрать системную библиотеку без определения пар как функторов, но у меня сейчас нет времени для такого эксперимента.

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