Наборы, функторы и путаница Eq

Недавно появилось обсуждение о Sets, которое в 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]

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

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

Можно утверждать, что это не является провалом операции map на Set s, а ошибкой экземпляра Eq, который мы определили, поскольку он не соблюдает закон замены, а именно: для двух экземпляров Eq на A и B и отображения 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 является структурным".

- edwardkmett

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

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

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

"Traversable заключается в сохранении структуры точно как-есть."

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

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

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

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

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

Ответы

-- | 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)