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

    Очень удивительно (я бы даже сказал — внезапно!), но кортеж-пара в 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. В отличие от глобально определенных экземпляров такие редуцированные функции отображения легко скрыть в случае необходимости при импорте соответствующего модуля.
    Поделиться публикацией

    Комментарии 24

      +4
      Размышления — это хорошо.
      Реальность несколько интереснее.
      1) Пара является Функтором
      2) Подобные формулировки inc (x1, x2) = (inc x1, inc x2), наверняка требуют RankNTypes расширения. Включите его.
      3) Вам Overlapping instances говорит о конфликте. Причём, с разным результатом для разных инстансов.
      Самым простым, будет создать функцию
      {-# LANGUAGE RankNTypes #-}
      both :: (Num a, Num b) => (forall c. Num c => c -> c) -> (a, b) -> (a, b)
      both f (a, b) = (f a, f b)
      

      и вычислять надо:
      > both inc (2, 3.0)
      (3, 4.0)
      

      4) То, что вы пытаетесь определить как Функтор2 почти наверняка является БиФунктором.
      hackage.haskell.org/package/bifunctors-5
      class Bifunctor p where
        -- | Map over both arguments at the same time.
        bimap :: (a -> b) -> (c -> d) -> p a c -> p b d
        bimap f g = first f . second g
      
        -- | Map covariantly over the first argument.
        first :: (a -> b) -> p a c -> p b c
        first f = bimap f id
      
      
        -- | Map covariantly over the second argument.
        second :: (b -> c) -> p a b -> p a c
        second = bimap id
      
      
      instance Bifunctor (,) where
        bimap f g ~(a, b) = (f a, g b)
      
        0
        наверняка требуют RankNTypes расширения. Включите его.


        Интересно, почему мне об этом ничего не сказал компилятор?

        Самым простым, будет создать функцию


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

        Скажем так, если я заведу отдельную функцию both, то мне придется придумать, как реализовать вызов вида

        both inc [1, 2, 3, 4, 5]
        


        То, что вы пытаетесь определить как Функтор2 почти наверняка является БиФунктором.


        Да, это классно. Теперь попробую еще поискать трифункторы. В другом комментарии я отметил, что это проблема семантического поиска. Я понимаю, что мне нужно, но не могу сказать, как именно это называется. Так что, hoogle не всегда рулит :-).
          0
          2) Подобные формулировки inc (x1, x2) = (inc x1, inc x2), наверняка требуют RankNTypes расширения. Включите его.

          Не-а. Я сначала тоже подумал, что это ж полиморфизм второго порядка, как оно вообще компилится! Потом допёр, что в этой функции три разных inc'а.
          +4
          > Очень удивительно (я бы даже сказал — внезапно!), но кортеж-пара в GHC является функтором.
          Ничего удивительного в этом нет. Все по аналогии с тем, что функтором является левое сечение стрелки (e ->). Поскольку запятая — тип с двумя параметрами (,) :: a -> b -> (a,b), то ее левое сечение (a,) имеет однопараметрический по b тип (a,) :: b -> (a,b) и становится функтором. Теперь должно стать понятно, почему fmap (+1) (2,3) вернет (2, 4).
            0
            А я догадался о правильном поведении по аналогии с Either. Спасибо за более общее объяснение.
            +1
            Вообще, нам необходимо для разного поведения для фунторов и пар создать новый тип данных:
            {-# LANGUAGE FlexibleInstances #-}
            {-# LANGUAGE OverlappingInstances #-}
            
            instance Incable Int where
                inc = (1+)
            
            newtype Tup a = Tup {unTup :: a}
            
            instance (Incable t1, Incable t2) => Incable (Tup (t1, t2)) where
                inc (Tup (x1, x2)) = Tup (inc x1, inc x2)
            
            instance (Incable t1, Incable t2, Incable t3) => Incable (Tup (t1, t2, t3)) where
                inc (Tup (x1, x2, x3)) = Tup (inc x1, inc x2, inc x3)
            
            

            и использовать:
            > unTup $ inc $ Tup (2, 3.0)
            (3,4.0)
            
            > unTup $ inc $ Tup (2, 3.0, 8.0)
            (3,4.0,9.0)
            
              0
              Разумно, но в общем контексте не пойдет. В оригинальном проекте мне нужно, чтобы изменилось поведение именно для кортежей, которые используются в коде, который мне недоступен. В следующей статье я собираюсь объяснить этот момент.
                0
                Ваша проблема в том, что вы желаете использовать функторы, и кортежи, но кортежи вы не хотите использовать как функторы.
                Вы хотите нарушить математику, не стоит этого делать.
                  0
                  Двупараметрический тип попытались использовать как однопараметрический, редуцировав совершенно произвольно первый по порядку параметр. Или математика запрещает рассматривать другие случаи, когда нужно редуцировать, скажем, последний параметр, а остаток рассматривать как функтор?

                  Впрочем, в аппендиксе я все развернул. Я всего лишь против того, чтобы частное решение выносилось на уровень системы, тем более, в условиях, когда последствия такого решения невозможно заблокировать. Математика тут ни при чем.
                    0
                    Так и Хаскель не запрещает, только надо использовать newtype, для которого и определить функтор иначе. Возможно, было бы удобнее, если б инстансы были именованные, и можно было бы их не импортировать, а определять нужные себе в данный момент, хоть бы и даже у функции в where.
                      0
                      Создание новых типов в таких случаях плодит лишние сущности, иногда подобные типы «выламываются» из общей системы, которую приходится под них адаптировать. А если еще добавить к этому, что это расширение библиотеки, которая не тобой писана… Увы, на частном примере это не очень хорошо заметно, поэтому и кажется, что проблема искусственная. В реальной ситуации, когда в системе десятки типов, это становится заметно, но как впихнуть такой пример в формат статьи, я пока не очень понимаю. Постараюсь все же развернуть тему чуть позднее.

                      Да, именованные экземпляры были бы неплохим решением. Интересно, что мешает их реализовать? Еще одну возможность я вижу в том, чтобы предоставить возможность перекрытия экземпляров в пределах модуля. В случае паранойи можно было бы предусмотреть расширение, которое отключающает проверку перекрытия экземпляров в некоторых случаях. А то получается, как в известной присказке — «Хаскель не даст вам прострелить свою ногу» :-).

                      Насчет «нужных в данный момент». Слишком часто такие определения многократно повторяются. Иначе не возникало бы желание обобщить их. Но не больше, чем это необходимо :-).
                        0
                        В случае паранойи можно было бы предусмотреть расширение, которое отключающает проверку перекрытия экземпляров в некоторых случаях.

                        Так это, OverlappingInstances же?
                        Да, именованные экземпляры были бы неплохим решением. Интересно, что мешает их реализовать?

                        В идрисе, кстати, так и реализовали. Странно, что в хаскеле нет хотя бы расширения.
              +1
              > Допустим, мы определяем класс Incable инкрементальных типов:
              Вдогонку: зачем нам еще один класс инкрементальных типов? Уже есть class Enum с функцией succ из коробки.
                0
                Честно говоря, Incable — только для демонстрации. В оригинале был класс Reducable, но думаю, это вряд-ли кому-то тут что-то скажет. Скажу честно, использовать для демонстрации Enum просто не догадался. Не в том суть, а подобные мелочи можно шлифовать бесконечно.
                  0
                  И кстати, экземплярами Incable могут быть также дробные числа и даже кортежи :-).
                  +1
                  Принято считать, что функтор — это всегда тип, у которого есть только один параметр.

                  Э… Функтором может быть любой тип подходящего кайнда и ничего странного в этом нет. Примером може служить реализация функтора для Map a b:
                  instance Functor (Map k) where
                     -- функция применяется к значениям, а ключи не затрагиваются
                  

                  И от словаря вполне логично ожидать такого поведения (и именно так реализован функтор для Map). А, скажем, от ячейки лабиринта Cell Int Int a можно ожидать, что функция не затронет координаты ячейки, а коснется только содержимого. И это только вполне очевидные примеры.
                    0
                    Не, ну понятно, что путем частичного вычисления любой тип можно свести к однопараметрическому. Интереснее, когда функтор воздействует на все свои части. Вот, оказалось, что я заново открыл бифункторы. Знать бы еще сразу, что они так называются. Но в мне также интересны трифункторы. Я ведь задачу поставил в более общем виде.
                  +3
                  Может это слегка грубо, но мне кажется, что единственный вывод, который можно тут сделать это то, что перед тем, как писать статью стоит зайти на сайты где можно получить подробные ответы на вопросы и удостовериться, что вы правильно понимаете обсуждаемые вопросы. Примеры таких сайтов это (stack-overflow по тегу haskell, #haskell на freenode.net, рассылка Haskell-Beginners или haskell-cafe (в первой наверняка ответят подробнее), вопросы на хабрахабр, так же есть неплохие сообщества в LJ, Juick.com, ruhaskell.org).
                    +1
                    Совет хороший, и я честно искал ответы на свои вопросы. Беда тут скорее в том, что «для того, чтобы правильно задать вопрос, нужно знать, как минимум, половину ответа» ©.

                    Вполне возможно, что я неправильно понимаю некоторые вещи, но чтобы грамотно их изложить, в чем именно мое непонимание, приходится очень много объяснять. Поверьте, то, чем я поделился — только небольшой кусок проблем, с которыми я столкнулся. Мне просто удалось выделить этот кусок в чистом виде.
                      +1
                      Мне кажется, что утверждение было «в хорошем вопросе содержится половина ответа», не уверен, что из этого следует, то что её нужно знать, во всяком случае осознавать.

                      Впрочем это не важно, даже не зная половины ответа можно начать дискуссию и сайты (кроме сайтов вопросов) для этого и созданы, это поможет выяснить разницу и ошибки в понимании (возможно и у отвечающих). Просто в данной статье я заметил, некоторые вещи, которые меня удивили, так то: описание ожидаемого, не учитывание принципов работы выбора инстанса, неаккуратное соотвествие в записи того, что хочется получить и что делается (комментаний про Rank2Types). Я не знаю является ли это непониманием, или просто неточной формулировкой или неточным моим прочтением, но преварительный разбор частей бы не помешал :)
                    +2
                    У Вас в определении тройки как функтора ошибка — fmap в правой части. Вот так работает:
                    instance Functor ((,,) t1 t2) where
                        fmap f (x1, x2, x3) = (x1, x2, f x3)
                      0
                      Спасибо! Честно говоря, просто замылился глаз, когда писал код, а компилятор не дал вменяемого сообщения — предложил заняться выводом типа, а не проверить вызов.

                      Приятно также, что увеличение сразу трех элементов теперь также работает. То есть, как минимум одну свою проблему я все-таки решил :-).
                      0
                      Вы забываете о том, что у вас в кортеже могут быть значения совершенно разных типов. Давайте попробуем представить, что компилятор позволил вам реализовать fmap для тройки так, как вы хотите, и попробуем применить fmap (+1) к тройке:

                      fmap (+1) (True, "string", 2) == (True + 1, "string" + 1, 2 + 1)
                      

                      Какой результат вы хотели бы получить в этом случае?

                      Теперь понятно, почему функтором можно сделать только однопараметрический тип (или многопараметрические, но частично применённые до однопараметрического)?

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

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

                      Самое читаемое