이 구현이 Foldable Typeclass의 잘못된 인스턴스 인 이유는 무엇입니까?

Question

저는 멋진 Haskell Book을 통해 작업하고 있습니다. Traversable 챕터 (21)의 끝에서 다음 트리에 대한 인스턴스를 작성해야합니다.

data Tree a =
    Empty
  | Leaf a
  | Node (Tree a) a (Tree a)

여기 내 솔루션 의 전체 코드 에 대한 링크가 있습니다. 연습에서는 foldMap및 foldr. 이것이 내가 구현 한 방법입니다 foldr(호출 순서에 많은 생각을하지 않고) :

foldr _ z Empty = z
foldr f z (Leaf x) = f x z
foldr f z (Node left x right) = 
  f x $ foldr f (foldr f z left) right

그런 foldMap다음 다음과 같이 구현 했습니다.

foldMap f Empty = mempty
foldMap f (Leaf x) = f x
foldMap f (Node left x right) = 
  foldMap f left <> f x <> foldMap f right

QuickCheck의 foldable테스트 배치를 실행할 때 몇 가지 오류가 발생합니다. 내 foldr구현을 다음으로 변경 하면 모든 테스트가 통과됩니다.

foldr _ z Empty = z
foldr f z (Leaf x) = f x z
foldr f z (Node left x right) = 
  foldr f (f x (foldr f z right)) left

실패한 테스트 케이스를 직접 실행 해 보았지만 실패를 다시 만들 수 없습니다.

*Ch21_12_ExercisesTree Data.Monoid> tree = Node (Node (Leaf (-5)) 3 (Node (Leaf 3) 5 Empty)) (-2) Empty
*Ch21_12_ExercisesTree Data.Monoid> foldr (<>) (mempty :: Sum Int) t
Sum {getSum = 4}
*Ch21_12_ExercisesTree Data.Monoid> foldMap Sum t
Sum {getSum = 4}

foldQuickCheck가 사용하는 ing 기능 에 대해 알아 내지 못한 것이 있다고 생각 합니다.

질문 :

1. 오류가 발생하는 이유는 무엇입니까?
2. QuickCheck에서 테스트에 사용 된 기능을 얻을 수있는 방법이 있습니까?

Answer 1

foldr값을 (모노 이드로 ) 구성 할 수있는 함수로 바꾸는 함수 와 함께 monoid foldMap 를 사용하여Endo 얻을 수 있습니다. 그렇다면, 만약 당신 이 ...a -> b -> bab -> bfoldMap

foldMap f Empty = mempty
foldMap f (Leaf x) = f x
foldMap f (Node left x right) = 
  foldMap f left <> f x <> foldMap f right

... 해당하는 값 foldr은 다음과 같아야합니다.

foldr f z Empty = id z  -- mempty amounts to id
foldr f z (Leaf x) = (f x) z
foldr f z (Node left x right) = 
  ((\e -> foldr f e left) . f x . (\e -> foldr f e right)) z  -- (<>) amounts to (.)

조금 정리하면 ...

foldr f z Empty = z
foldr f z (Leaf x) = f x z
foldr f z (Node left x right) = 
  foldr f (f x (foldr f z right)) left)

... 우리 foldr는 귀하의 질문에 작성된 올바른 정의를 얻습니다 . 구현 간의 차이가 구성 순서와 관련이 있기 때문에에서 알 수 있듯이 non-commutative monoid를 시도하면 쉽게 실패한 경우 가 발생합니다 .

QuickCheck 하위 질문 에서 DDub의 답변을 연기합니다 . .

Answer 2

이미 추론했듯이 실패하는 이유는 두 구현이 구별 가능하기 때문에 비 교환 적 모노 이드를 사용하여 관찰 할 수 있기 때문입니다.

---

quickcheck에서 사용하는 기능을 얻는 것은 그렇게 간단하지 않습니다. 예를 들어, 좀 더 자세한 정보는 quickcheck에서 생성 된 기능 에 대한 이 질문 / 답변을Show 참조하십시오.

얻을 수있는 방법 ShowQuickCheck에서 수있는 기능에 기능을 래핑하는 것입니다 유형 . 즉, 호출중인 코드 ( 여기에 있음 )는 함수를 직접 사용하기 때문에 표시 할 수 없습니다. 당신이 시도 할 수있는 하나의 옵션은 당신의 자신의 버전을 만드는 것입니다 당신이 형식을 사용 기능 대신을 하고 필요에 따라 기능을 적용 할 수 있습니다.FunfoldableFun a ba -> bapplyFun

Answer 3

나는 단지 내가 commutative Monoid를 사용했다는 것을 깨달았다. 나는 non-commutative Monoid를 사용하여 실패를 재현 할 수 있었다.

> ftree = fmap (First . Just) tree
> foldr (<>) mempty ft
First {getFirst = Just (-2)}
> foldMap (First . Just) ft
First {getFirst = Just (First {getFirst = Just (-5)})}

이것은 아마도 간단한 경우입니다. 실제 데이터 유형을 사용하는 프로덕션 코드에서 이것은 훨씬 더 복잡 할 수 있다고 생각합니다.