Почему fmap должен отображать каждый элемент списка?

Question

После прочтения книги " Изучите свой Haskell для большого блага" и очень полезной вики-книги " Теория категорий Haskell", которая помогла мне преодолеть распространенную ошибку категории, заключающуюся в путанице объектов категории с объектами программирования, у меня все еще остается следующий вопрос:

Почему должен fmap сопоставить все элементы списка?

Мне нравится, что это так, я просто хочу понять, насколько эта категория теоретически оправдана. (или, возможно, легче оправдать использование HoTT?)

В нотации Scala, List является функтором, который принимает любой тип и отображает его в тип из набора всех типов списка, например, он отображает тип Int к типу List[Int] и он отображает функции на Int например

• Int.successor: Int => Int в Functor[List].fmap(successor) : List[Int] => List[Int]
• Int.toString: Int => String в Functor[List].fmap(toString): List[Int] => List[String]

Теперь каждый экземпляр List[X] это моноид с empty функция (mempty в Хаскеле) и combine функция (mappend в Хаскеле). Я предполагаю, что можно использовать тот факт, что списки являются моноидами, чтобы показать, что map должен отобразить все элементы списка. Я чувствую, что если добавить pure функция от Applicative, это дает нам список только с одним элементом некоторого другого типа. например Applicative[List[Int]].pure(1) == List(1), поскольку map(succ) на этих элементах мы получаем список синглтона со следующим элементом, который охватывает все эти подмножества. Тогда я полагаю combine Функция всех этих синглетонов дает нам все остальные элементы списков. Почему-то я предполагаю, что это ограничивает работу карты.

Еще один наводящий аргумент в том, что map должен сопоставить функции между списками. Так как каждый элемент в List[Int] имеет тип Int, и если один отображается на List[String] нужно отобразить каждый его элемент, иначе не будет подходящего типа.

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

Контрпример?

Почему это не контрпример функции карты?

def map[X,Y](f: X=>Y)(l: List[X]): List[Y] = l match {
  case Nil => Nil
  case head::tail=> List(f(head))
}

Кажется, чтобы следовать правилам

val l1 = List(3,2,1)
val l2 = List(2,10,100)

val plus2 = (x: Int) => x+ 2
val plus5 = (x: Int) => x+5

map(plus2)(List()) == List()
map(plus2)(l1) == List(5)
map(plus5)(l1) == List(8)

map(plus2 compose plus5)(l1) == List(10)
(map(plus2)_ compose map(plus5)_)(l1) == List(10)

Ааа. Но это не соответствует ид.

def id[X](x: X): X = x

map(id[Int] _)(l1) == List(3)
id(l1) == List(3,2,1)

Answer 1

Это опирается на теоретический результат, называемый "параметричностью", который сначала был определен Рейнольдсом, а затем разработан Уодлером (среди прочих). Пожалуй, самая известная статья на эту тему - "Теоремы бесплатно!" Вадлер.

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

foo :: a -> a

Только из этого типа мы можем видеть, что если foo заканчивается, это функция идентичности. Наглядно, foo не может различить разные a Так как в Haskell у нас нет, например, Java instanceof который может проверить фактический тип времени выполнения. Так же,

bar :: a -> b -> a

должен вернуть первый аргумент. А также baz :: a -> a -> a должен вернуть либо первое, либо второе. А также quz :: a -> (a -> a) -> a необходимо несколько раз применить функцию к первому аргументу. Вы, наверное, поняли идею сейчас.

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

Для map типа, мы получаем следующее страшное свойство:

forall t1,t2 in TYPES, f :: t1 -> t2.
 forall t3,t4 in TYPES, g :: t3 -> t4.
  forall p :: t1 -> t3.
   forall q :: t2 -> t4.
    (forall x :: t1. g (p x) = q (f x))
    ==> (forall y :: [t1].
          map_{t3}_{t4} g (map2_{t1}_{t3} p y) =
          map2_{t2}_{t4} q (map_{t1}_{t2} f y))

Выше, map является известной функцией карты, в то время как map2 любая произвольная функция, которая имеет тип (a -> b) -> [a] -> [b],

Теперь, далее предположим, что map2 удовлетворяет законам функтора, в частности map2 id = id, Затем мы можем выбрать p = id а также t3 = t1, Мы получаем

forall t1,t2 in TYPES, f :: t1 -> t2.
 forall t4 in TYPES, g :: t1 -> t4.
   forall q :: t2 -> t4.
    (forall x :: t1. g x = q (f x))
    ==> (forall y :: [t1].
          map_{t1}_{t4} g (map2_{t1}_{t1} id y) =
          map2_{t2}_{t4} q (map_{t1}_{t2} f y))

Применение закона о функторе map2:

forall t1,t2 in TYPES, f :: t1 -> t2.
 forall t4 in TYPES, g :: t1 -> t4.
   forall q :: t2 -> t4.
    (forall x :: t1. g x = q (f x))
    ==> (forall y :: [t1].
          map_{t1}_{t4} g y =
          map2_{t2}_{t4} q (map_{t1}_{t2} f y))

Теперь давайте выберем t2 = t1 а также f = id:

forall t1 in TYPES.
 forall t4 in TYPES, g :: t1 -> t4.
   forall q :: t1 -> t4.
    (forall x :: t1. g x = q x)
    ==> (forall y :: [t1].
          map_{t1}_{t4} g y =
          map2_{t1}_{t4} q (map_{t1}_{t1} id y))

По закону функтора map:

forall t1, t4 in TYPES.
   forall g :: t1 -> t4, q :: t1 -> t4.
    g = q
    ==> (forall y :: [t1].
          map_{t1}_{t4} g y =
          map2_{t1}_{t4} q y)

что значит

forall t1, t4 in TYPES.
 forall g :: t1 -> t4.
    (forall y :: [t1].
          map_{t1}_{t4} g y =
          map2_{t1}_{t4} g y)

что значит

forall t1, t4 in TYPES.
          map_{t1}_{t4} = map2_{t1}_{t4}

Подводя итог:

Если map2 любая функция с полиморфным типом (a -> b) -> [a] -> [b] и такой, что он удовлетворяет первому закону функтора map2 id = id, затем map2 должен быть эквивалентен стандарту map функция.

Также смотрите сообщение в блоге Эдварда Кметта.

Обратите внимание, что в Scala вышеприведенное верно только в том случае, если вы не используете x.isInstanceOf[] и другие инструменты отражения, которые могут нарушить параметричность.