Множества, функторы и путаница эквалайзера

недавно на работе возникла дискуссия о наборах, которые в 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))

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

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 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 wiki (обратите внимание, что Traversable обобщение Functor)

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

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

а в реальном мире Хаскелл

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

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

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

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