세트, Functor 및 Eq 혼란

세트, Functor 및 Eq 혼란

---

최근 작업에서 세트에 대한 토론이 나왔는데, 스칼라 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가 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]

그래서 Setfunctor 법칙을 충족시키지 못합니다.

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

이것이의 실패 아니라고 주장 할 수 있습니다 map에 동작 Set들,하지만의 실패 Eq우리가 정의된다는 사실, 즉 두 개의 인스턴스를 들어, 대체 법을 존중하지 않기 때문에, 예를 EqA와 B에와 매핑 f : A -> B한 후

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

하는 보유하지 않습니다 AlwaysEqual(예를 들어 고려 f = unWrap).

대체 법칙은 Eq우리가 존중해야하는 유형에 대한 합리적인 법칙 입니까? 확실히 다른 평등 법칙은 우리 AlwaysEqual유형에 의해 존중되므로 (대칭, 전이성 및 반사성은 사소하게 충족 됨) 대체가 문제를 일으킬 수있는 유일한 장소입니다.

나에게 substition은 Eq수업에 매우 바람직한 속성처럼 보입니다 . 반면에 최근 Reddit 토론 에 대한 일부 의견은 다음과 같습니다.

"대체는 필요 이상으로 강력 해 보이며 기본적으로 유형을 인용하여 유형을 사용하는 모든 함수에 요구 사항을 부여합니다."

- godofpumpkins

"또한 우리가 동일시하고 싶지만 어떻게 든 구별 할 수있는 값에 대한 합법적 인 용도가 많기 때문에 대체 / 합의를 원하지 않습니다."

- sclv

"대체는 구조적 평등을 위해서만 유지되지만 Eq구조적 이라고 주장하는 것은 없습니다 ."

- 에드워드 크 메트

이 세 가지는 모두 Haskell 커뮤니티에서 꽤 잘 알려져 있으므로, 나는 그들에 맞서고 내 Eq유형 에 대한 대체 가능성을 주장하는 것을 주저합니다 !

Seta 에 대한 또 다른 주장-a 가되는 것은 모양을 보존하면서 "컬렉션"의 "요소"를 변형 할 수 Functor있다는 것이 널리 받아 들여지고 Functor있습니다. 예를 들어, Haskell wiki에있는이 인용문 ( Traversable의 일반화에 주의하십시오 Functor)

" Foldable요소를 처리하는 구조를 거치면서 모양을 버릴 수있는 기능을 제공하는 곳에서는 모양 Traversable을 보존하고 예를 들어 새로운 값을 입력하면서 그렇게 할 수 있습니다."

" Traversable는 구조를 그대로 유지하는 것입니다."

그리고 Real World Haskell에서

"... [A] functor는 모양을 유지해야합니다. 컬렉션의 구조는 functor의 영향을받지 않아야합니다. 컬렉션에 포함 된 값만 변경되어야합니다."

분명히 모든 펑터 인스턴스 Set는 세트의 요소 수를 줄임으로써 모양을 변경할 수 있습니다.

하지만 마치 Set s는 실제로 펑터가되어야 의 Ord요구 사항을 무시하고 -집합에 대한 절대적인 요구 사항이 아니라 집합으로 효율적으로 작업하려는 욕구에 의해 부과 된 인위적인 제한으로 간주됩니다. 예를 들어 함수 집합은 다음과 같습니다. 어떤 경우에도 Oleg 는 제약 조건 Set이 필요없는 효율적인 Functor 및 Monad 인스턴스를 작성하는 방법을 보여주었습니다Ord . 그것들에 대한 좋은 용도가 너무 많습니다 (존재하지 않는 Monad인스턴스도 마찬가지입니다 ).

누구든지이 혼란을 해결할 수 있습니까? 해야 Set할Functor ? 그렇다면 Functor 법칙을 위반할 가능성에 대해 어떻게해야합니까? 법칙은 무엇이어야하며 특히 Eq법규 Functor및 Set사례 와 어떻게 상호 작용 합니까?

---

반대하는 또 다른 논쟁 Seta 가되는 것은 모양을 보존하면서 "컬렉션"의 "요소"를 변형 할 수 Functor있다는 것이 널리 받아 들여지고 Functor있습니다. [...] 분명히, Set의 모든 functor 인스턴스는 세트의 요소 수를 줄임으로써 모양을 변경할 수 있습니다.

나는 이것이 "모양"비유가 아닌 경우를 정의하는 조건으로 취하는 경우가 두렵다. 수학적으로 말하면 파워 세트 펑터와 같은 것이 있습니다.Wikipedia에서 :

파워 세트 : 파워 세트 펑터 P : 세트 → 세트 는 각 세트를 해당 파워 세트에 매핑하고 각 기능 f : X → Y를 U ⊆ X를 이미지 f (U) ⊆ Y로 보내는 맵에 매핑합니다.

함수 P (f) ( fmap f파워 세트 펑터에서)는 인수 세트의 크기를 보존하지 않지만 그럼에도 불구하고 펑터입니다.

잘못 고려 된 직관적 인 비유를 원한다면 다음과 같이 말할 수 있습니다. 목록과 같은 구조에서 각 요소는 다른 요소와의 관계에 대해 "관심"하며 거짓 펑터가 해당 관계를 끊는 경우 "불쾌감을줍니다". . 그러나 집합은 제한적인 경우입니다. 요소가 서로 무관심한 구조이므로 "불쾌감을주기 위해"할 수있는 일은 거의 없습니다. 유일한 것은 거짓 펑터가 해당 요소를 포함하는 집합을 "음성"이 포함되지 않은 결과에 매핑하는 것입니다.

(좋아, 이제 닥칠 게 ...)

---

편집 : 내 대답의 맨 위에 인용했을 때 다음 비트를 잘랐습니다.

예를 들어, Haskell wiki에있는이 인용문 ( Traversable의 일반화에 주의하십시오 Functor)

" Foldable요소를 처리하지만 모양을 버리는 구조를 통과 할 수있는 능력을 제공하는 곳 ,Traversable allows you to do that whilst preserving the shape and, e.g., putting new values in."

" Traversable는 구조를 그대로 유지하는 것입니다."

Here's I'd remark that Traversable is a kind of specialized Functor, not a "generalization" of it. One of the key facts about any Traversable (or, actually, about Foldable, which Traversable extends) is that it requires that the elements of any structure have a linear order—you can turn any Traversable into a list of its elements (with Foldable.toList).

Another, less obvious fact about Traversable is that the following functions exist (adapted from Gibbons & Oliveira, "The Essence of the Iterator Pattern"):

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

A Traversable instance for sets would violate the proposed law, because all non-empty sets would have the same Shape—the set whose Contents is [()]. From this it should be easy to prove that whenever you try to reassemble a set you would only ever get the empty set or a singleton back.

Lesson? Traversable "preserves shape" in a very specific, stronger sense than Functor does.

---

Set is "just" a functor (not a Functor) from the subcategory of Hask where Eq is "nice" (i.e. the subcategory where congruence, substitution, holds). If constraint kinds were around from way back then perhaps set would be a Functor of some kind.

---

Well, Set can be treated as a covariant functor, and as a contravariant functor; usually it's a covariant functor. And for it to behave regarding equality one has to make sure that whatever the implementation, it does.

Regarding Set.zip - it is nonsense. As well as Set.head (you have it in Scala). It should not exist.

참고URL : https://stackoverflow.com/questions/19177125/sets-functors-and-eq-confusion