Functor가 아닌 (또는 Traversable이 아닌) Foldable의 예?

Functor가 아닌 (또는 Traversable이 아닌) Foldable의 예?

---

Foldable인스턴스는 컨테이너의 일종 될 가능성이 있으며, 그래서이 될 가능성 Functor도있다. 실제로 이것은 말한다

Foldable유형은 컨테이너 (클래스가 기술적으로 필요하지 않지만이다 Functor, 흥미로운 Foldable들 모두 Functor들).

그래서 Foldable당연히 a Functor또는 a 가 아닌 의 예가 Traversable있습니까? (아마도 Haskell 위키 페이지가 놓친 것 :-))

---

다음은 완전한 파라 메트릭 예입니다.

data Weird a = Weird a (a -> a)

instance Foldable Weird where
  foldMap f (Weird a b) = f $ b a

Weird부정적인 위치에서 발생 Functor하기 때문 이 아닙니다 a.

---

다음은 간단한 예 Data.Set.Set입니다.. 직접보십시오.

그 이유는 다음에 대해 정의 된 특수 fold및 map함수 의 유형을 검토하면 분명해집니다 Set.

foldr :: (a -> b -> b) -> b -> Set a -> b

map :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b

데이터 구조가 내부적으로 이진 검색 트리에 의존하기 때문에 Ord요소에 대한 제약이 필요합니다. Functor인스턴스는 모든 요소 유형을 허용해야하므로 실행 불가능합니다.

반면에 접기는 항상 요약 값을 생성하기 위해 트리를 파괴하므로 접기의 중간 결과를 정렬 할 필요가 없습니다. 폴드가 실제로 새로운을 구축하더라도 제약 조건 Set을 충족하는 책임 Ord은 폴드 자체가 아니라 폴드에 전달 된 누적 함수에 있습니다.

완전히 매개 변수화되지 않은 모든 컨테이너 유형에도 동일하게 적용됩니다. 그리고의 유용성을 감안할 때 Data.Set"흥미로운"에 대해 인용 한 발언이 Foldable약간 의심스러워 보입니다.

---

읽기 아름다운 접기 나는 그것을 포장하여 Foldable만들 수 있음을 깨달았 Functor습니다.

data Store f a b = Store (f a) (a -> b)

간단한 스마트 컨 트럭 터로 :

store :: f a -> Store f a a
store x = Store x id

(이것은 Store comonad 데이터 유형 의 변형 일뿐입니다.)

이제 우리는

instance Functor (Store f a) where
    fmap f (Store x g)   = Store x (f . g)

instance (F.Foldable f) => F.Foldable (Store f a) where
    foldr f z (Store x g)    = F.foldr (f . g) z x

이렇게하면 Data.Set.SetSjoerd Visscher와 Sjoerd Visscher를 모두 Weird펑터로 만들 수 있습니다 . (그러나 구조는 그 값을 기억하지 않기 때문에 우리가 사용한 함수 fmap가 복잡한 경우 반복해서 접는 것은 매우 비효율적 일 수 있습니다 .)

---

업데이트 : 이것은 또한 펑터이고 접을 수 있지만 횡단 할 수없는 구조의 예를 제공합니다. Store순회 가능 하게하려면 순회 가능하게 만들어야 (->) r합니다. 그래서 우리는 구현해야 할 것입니다

sequenceA :: Applicative f => (r -> (f a)) -> f (r -> a)

하자 걸릴 Either b에 f. 그런 다음 구현해야합니다.

sequenceA' :: (r -> Either b a) -> Either b (r -> a)

분명히 그러한 기능은 없습니다 ( Djin으로 확인할 수 있습니다 ). 그래서 우리는 깨닫지 못합니다 sequenceA.

참조 URL : https://stackoverflow.com/questions/8359115/an-example-of-a-foldable-which-is-not-a-functor-or-not-traversable