Недавно появилось обсуждение о 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
в частности?