Множества, функторы и уравнение

Question

Недавно на работе возникла дискуссия о множествах, которые в Scala поддерживают zip метод и как это может привести к ошибкам, например,

scala> val words = Set("one", "two", "three")
scala> words zip (words map (_.length))
res1: Set[(java.lang.String, Int)] = Set((one,3), (two,5))

Я думаю, что довольно ясно, что Setне должен поддерживать zip операция, так как элементы не упорядочены. Тем не менее, было высказано предположение, что проблема заключается в том, что Set на самом деле не функтор, и не должен иметь map метод. Конечно, вы можете попасть в беду, составив карту для набора. Переходя на Haskell сейчас,

data AlwaysEqual a = Wrap { unWrap :: a }

instance Eq (AlwaysEqual a) where
    _ == _ = True

instance Ord (AlwaysEqual a) where
    compare _ _ = EQ

а теперь в ghci

ghci> import Data.Set as Set
ghci> let nums = Set.fromList [1, 2, 3]
ghci> Set.map unWrap $ Set.map Wrap $ nums
fromList [3]
ghci> Set.map (unWrap . Wrap) nums
fromList [1, 2, 3]

Так Set не удовлетворяет закону функтора

    fmap f . fmap g = fmap (f . g)

Можно утверждать, что это не провал map операция на Setс, но провал Eq экземпляр, который мы определили, потому что он не уважает закон о замене, а именно, для двух случаев Eq на А и Б и отображение f : A -> B затем

    if x == y (on A) then f x == f y (on B)

который не подходит для AlwaysEqual (например, рассмотреть f = unWrap).

Является ли закон подстановки разумным законом для Eq типа что мы должны стараться уважать? Конечно, другие законы о равенстве соблюдаются нашими AlwaysEqual тип (симметрия, транзитивность и рефлексивность удовлетворяются тривиально), поэтому замена - единственное место, в которое мы можем попасть в беду.

Для меня подстановка кажется очень желательным свойством для Eq учебный класс. С другой стороны, некоторые комментарии к недавнему обсуждению Reddit включают

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

- Godofpumpkins

"Я также на самом деле не хочу замены / конгруэнтности, поскольку существует множество законных вариантов использования значений, которые мы хотим приравнять, но которые как-то различимы".

- sclv

"Замена имеет место только для структурного равенства, но ничто не настаивает Eq является структурным. "

- Эдвардкметт

Эти три довольно хорошо известны в сообществе Haskell, поэтому я буду не решаться идти против них и настаивать на заменяемости для моего Eq типы!

Еще один аргумент против Set быть Functor - широко признано, что, будучи Functor позволяет преобразовывать "элементы" "коллекции", сохраняя при этом форму. Например, эта цитата на вики Haskell (обратите внимание, что Traversable это обобщение Functor)

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

"Traversable о сохранении структуры в точности как есть ".

и в реальном мире Haskell

"... Функтор [A] должен сохранять форму. Функтор не должен затрагивать структуру коллекции; должны изменяться только содержащиеся в ней значения".

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

Но похоже, что SetS действительно должны быть функторами (игнорируя Ord Требование на данный момент - я вижу, что как искусственное ограничение, налагаемое нашим желанием эффективно работать с наборами, не является абсолютным требованием для любого набора. Например, наборы функций - совершенно разумная вещь для рассмотрения. В любом случае Олег показал, как написать эффективные экземпляры Functor и Monad для Set которые не требуют Ord ограничение). Для них слишком много хороших применений (то же самое верно и для несуществующих Monad пример).

Кто-нибудь может разобраться в этом беспорядке? Должен Set быть Functor? Если так, что можно сделать с возможностью нарушения законов Функтора? Для чего нужны законы Eq быть, и как они взаимодействуют с законами для Functor и Set экземпляр в частности?

Answer 1

Еще один аргумент против Set быть Functor - широко признано, что, будучи Functor позволяет преобразовывать "элементы" "коллекции", сохраняя при этом форму. [...] Очевидно, что любой экземпляр функтора для Set имеет возможность изменить форму, уменьшив количество элементов в наборе.

Я боюсь, что это случай, когда аналогия с "формой" является определяющим условием, когда это не так. Математически говоря, существует такая вещь, как функтор набора мощности. Из Википедии:

Наборы мощности: Функтор набора мощности P: Set → Set отображает каждый набор на свой набор мощности, а каждую функцию f: X → Y - на карту, которая отправляет U ⊆ X на его изображение f(U) ⊆ Y.

Функция P(f) (fmap f в функторе набора мощности) не сохраняет размер набора аргументов, но, тем не менее, это функтор.

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

(Хорошо, я сейчас заткнусь...)

---

РЕДАКТИРОВАТЬ: я обрезал следующие биты, когда я цитировал вас в верхней части моего ответа:

Например, эта цитата на вики Haskell (обратите внимание, что Traversable это обобщение Functor)

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

"Traversable о сохранении структуры в точности как есть ".

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

Еще один, менее очевидный факт о Traversable заключается в том, что существуют следующие функции (адаптировано из Gibbons & Oliveira, "Суть паттерна итератора"):

-- | A "shape" is a Traversable structure with "no content," 
-- i.e., () at all locations.
type Shape t = t ()

-- | "Contents" without a shape are lists of elements.
type Contents a = [a]

shape :: Traversable t => t a -> Shape t
shape = fmap (const ())

contents :: Traversable t => t a -> Contents a
contents = Foldable.toList

-- | This function reconstructs any Traversable from its Shape and
-- Contents.  Law:
--
-- > reassemble (shape xs) (contents xs) == Just xs
--
-- See Gibbons & Oliveira for implementation.  Or do it as an exercise.
-- Hint: use the State monad...
--
reassemble :: Traversable t => Shape t -> Contents a -> Maybe (t a)

Traversable экземпляр для множеств будет нарушать предложенный закон, потому что все непустые множества будут иметь одинаковые Shape- набор которого Contents является [()], Из этого должно быть легко доказать, что всякий раз, когда вы пытаетесь reassemble набор, который вы только когда-либо получите, верните пустой набор или синглтон.

Урок? Traversable "сохраняет форму" в очень конкретном, более сильном смысле, чем Functor делает.

Answer 2

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

Answer 3

Ну, Set можно рассматривать как ковариантный функтор и как контравариантный функтор; обычно это ковариантный функтор. И для того, чтобы вести себя в отношении равенства, нужно убедиться, что независимо от реализации, он делает.

По поводу Set.zip - это нонсенс. Как и Set.head (он у вас есть в Scala). Это не должно существовать.