목록 이외의 유형에 대해 접기를 구성하는 것은 무엇입니까?

목록 이외의 유형에 대해 접기를 구성하는 것은 무엇입니까?

---

단일 링크 목록을 고려하십시오. 다음과 같이 보입니다.

data List x = Node x (List x) | End

다음과 같은 접기 기능을 정의하는 것은 당연합니다.

reduce :: (x -> y -> y) -> y -> List x -> y

어떤 의미에서 reduce f x0every를 Node로 f, every End를 x0. 이것이 Prelude가 폴드 라고 부르는 것 입니다.

이제 간단한 이진 트리를 고려하십시오.

data Tree x = Leaf x | Branch (Tree x) (Tree x)

다음과 같은 기능을 정의하는 것도 마찬가지로 자연스러운 일입니다.

reduce :: (y -> y -> y) -> (x -> y) -> Tree x -> y

알 이 감소는 상당히 다른 성격을 가지고; 목록 기반은 본질적으로 순차적 인 반면,이 새로운 트리 기반은 분할 및 정복 느낌이 더 많습니다. par거기에 몇 개의 결합 자를 던지는 것을 상상할 수도 있습니다. (목록 버전에서 그런 것을 어디에 넣겠습니까?)

내 질문 :이 기능은 여전히 ​​"접기"로 분류됩니까, 아니면 다른 것입니까? (그렇다면 무엇입니까?)

기본적으로 누구나 접기에 대해 이야기 할 때마다 항상 본질적으로 순차적 인 접기 목록 에 대해 이야기 합니다. "순차적"이 폴드가 무엇인지 정의의 일부인지, 아니면 이것이 가장 일반적으로 사용되는 폴드 예제의 우연한 속성인지 궁금합니다.

---

Tikhon은 기술적 인 문제를 해결했습니다. 나는 그가 말한 것을 단순화하려고 노력할 것이라고 생각합니다.

안타깝게도 "폴딩"이라는 용어는 다음 두 가지 중 하나를 의미하기 위해 수년에 걸쳐 모호해졌습니다.

1. 컬렉션을 순서대로 순차적으로 축소합니다. Haskell에서 이것은 Foldablelarsmans가 말하는 클래스 에서 "folding"을 의미 합니다.
2. 당신이 요청한 개념 : 구조에 따라 대수 데이터 유형을 "파괴"( 구성의 반대 ), "관찰"또는 "제거". catamorphism 이라고도합니다 .

하나의 매개 변수화 된 함수가 다양한 유형에 대해이를 수행 할 수 있도록 이러한 개념을 모두 일반적으로 정의 할 수 있습니다. Tikhon은 두 번째 경우에 수행하는 방법을 보여줍니다.

그러나 대부분의 경우 Fix대수와 같은 모든 방법을 사용 하는 것은 과잉입니다. 모든 대수 데이터 유형에 대해 접기를 작성하는 더 간단한 방법을 알아 봅시다. 우리는 사용할 것이다 Maybe, 쌍, 목록과 나무를 우리의 예로 :

data Maybe a = Nothing | Just a
data Pair a b = Pair a b
data List a = Nil | Cons a (List a)
data Tree x = Leaf x | Branch (Tree x) (Tree x)
data BTree a = Empty | Node a (BTree a) (BTree a)

참고 Pair재귀 아니다; 내가 보여줄 절차는 "fold"유형이 재귀 적이라고 가정하지 않습니다. 사람들은 일반적으로이 경우를 "폴드"라고 부르지 않지만 실제로는 동일한 개념의 비재 귀적 경우입니다.

첫 번째 단계 : 주어진 유형의 접기는 접힌 유형을 사용하고 그 결과로 일부 매개 변수 유형을 생성합니다. 나는 후자를 부르고 싶다 r( "결과"를 위해). 그래서:

foldMaybe :: ... -> Maybe a -> r
foldPair  :: ... -> Pair a b -> r
foldList  :: ... -> List a -> r
foldTree  :: ... -> Tree a -> r
foldBTree :: ... -> BTree a -> r

두 번째 단계 : 마지막 인수 (구조에 대한 인수)에 추가하여 폴드는 형식에 생성자가있는만큼 인수를받습니다. Pair하나의 생성자가 있고 다른 예제에는 두 가지가 있습니다.

foldMaybe :: nothing -> just -> Maybe a -> r
foldPair  :: pair -> Pair a b -> r 
foldList  :: nil -> cons -> List a -> r
foldTree  :: leaf -> branch -> Tree a -> r
foldBTree :: empty -> node -> BTree a -> r

세 번째 단계 : 이러한 각 인수는 해당하는 생성자와 동일한 배열을 갖습니다. 생성자를 함수로 취급하고 유형을 작성해 봅시다 (유형 변수가 우리가 작성중인 서명의 변수와 일치하는지 확인).

Nothing :: Maybe a
Just    :: a -> Maybe a

Pair    :: a -> b -> Pair a b

Nil     :: List a
Cons    :: a -> List a -> List a

Leaf    :: a -> Tree a
Branch  :: Tree a -> Tree a -> Tree a

Empty   :: BTree a
Node    :: a -> BTree a -> BTree a -> BTree a

4 단계 : 각 생성자의 시그니처에서 생성하는 모든 데이터 유형을 유형 변수 r(폴드 시그니처에서 사용)로 대체합니다 .

nothing := r
just    := a -> r

pair    := a -> b -> r

nil     := r
cons    := a -> r -> r

leaf    := a -> r
branch  := r -> r -> r

empty   := r
node    := a -> r -> r -> r

보시다시피 두 번째 단계에서 결과 서명을 더미 유형 변수에 "할당"했습니다. 이제 5 단계 : 이전 스케치 접기 서명에 입력합니다.

foldMaybe :: r -> (a -> r) -> Maybe a -> r
foldPair  :: (a -> b -> r) -> Pair a b -> r 
foldList  :: r -> (a -> r -> r) -> List a -> r
foldTree  :: (a -> r) -> (r -> r -> r) -> Tree a -> r
foldBTree :: r -> (a -> r -> r -> r) -> BTree a -> r

이제 이러한 유형의 접힌 부분에 대한 서명입니다. 그것들은 재미있는 인자 순서를 가지고 있습니다. 왜냐하면 data선언과 생성자 유형 에서 폴드 유형을 읽음으로써 기계적으로이 작업을 수행 했지만, 함수형 프로그래밍에서는 어떤 이유로 기본 케이스를 data정의 에서 먼저 배치 하고 재귀 케이스 핸들러 를 정의 에서 먼저 배치하는 것이 일반적 fold입니다. 문제 없어요! 좀 더 전통적으로 만들기 위해 다시 섞어 봅시다.

foldMaybe :: (a -> r) -> r -> Maybe a -> r
foldPair  :: (a -> b -> r) -> Pair a b -> r 
foldList  :: (a -> r -> r) -> r -> List a -> r
foldTree  :: (r -> r -> r) -> (a -> r) -> Tree a -> r
foldBTree :: (a -> r -> r -> r) -> r -> BTree a -> r

---

정의는 기계적으로 채워질 수도 있습니다. foldBTree단계별로 선택 하고 구현 합시다 . 주어진 유형에 대한 접기는 우리가이 조건을 충족하는 것으로 알아 낸 유형의 한 함수입니다. 유형의 생성자를 사용한 접기는 해당 유형에 대한 식별 함수입니다 (시작한 값과 동일한 결과를 얻습니다).

다음과 같이 시작합니다.

foldBTree :: (a -> r -> r -> r) -> r -> BTree a -> r
foldBTree = ???

세 개의 인수가 필요하다는 것을 알고 있으므로이를 반영하는 변수를 추가 할 수 있습니다. 긴 설명 이름을 사용하겠습니다.

foldBTree :: (a -> r -> r -> r) -> r -> BTree a -> r
foldBTree branch empty tree = ???

data선언을 보면 BTree두 가지 가능한 생성자 가 있음을 알 수 있습니다. 정의를 각각의 경우로 분할하고 해당 요소에 대한 변수를 채울 수 있습니다.

foldBTree :: (a -> r -> r -> r) -> r -> BTree a -> r
foldBTree branch empty Empty = ???
foldBTree branch empty (Branch a l r) = ???
    -- Let's use comments to keep track of the types:
    -- a :: a
    -- l, r :: BTree a

이제와 같은 것보다 부족한 undefined첫 번째 방정식을 채우는 유일한 방법은 다음과 empty같습니다.

foldBTree :: (a -> r -> r -> r) -> r -> BTree a -> r
foldBTree branch empty Empty = empty
foldBTree branch empty (Branch a l r) = ???
    -- a :: a
    -- l, r :: BTree a

두 번째 방정식을 어떻게 채우나요? 다시 말하지만, undefined우리는 이것을 가지고 있습니다.

branch :: a -> r -> r -> r
a      :: a
l, r   :: BTree a

우리가 있었다면 할 subfold :: BTree a -> r수 있습니다 branch a (subfold l) (subfold r) :: r. 하지만 물론 우리는 'subfold'를 쉽게 작성할 수 있습니다.

foldBTree :: (a -> r -> r -> r) -> r -> BTree a -> r
foldBTree branch empty Empty = empty
foldBTree branch empty (Branch a l r) = branch a (subfold l) (subfold r)
    where subfold = foldBTree branch empty

이의 배입니다 BTree때문에 foldBTree Branch Empty anyTree == anyTree. 참고 foldBTree이러한 유형의 유일한 함수가 아닙니다; 이것도 있습니다 :

mangleBTree :: (a -> r -> r -> r) -> r -> BTree a -> r
mangleBTree branch empty Empty = empty
mangleBTree branch empty (Branch a l r) = branch a (submangle r) (submangle l)
    where submangle = mangleBTree branch empty

그러나 일반적으로 mangleBTree필요한 속성이 없습니다. 예를 들어, 우리가 가지고 있다면 foo = Branch 1 (Branch 2 Empty Empty) Empty, 그것은 다음과 같습니다 mangleBTree Branch Empty foo /= foo. 따라서 mangleBTree올바른 유형이 있더라도 폴드가 아닙니다.

---

이제 세부 사항에서 한 발 뒤로 물러나 mangleTree예제 를 통해 마지막 요점에 집중 해 보겠습니다. 폴드 (구조적 의미에서 내 대답의 상단에있는 # 2)는 대수 유형에 대한 가장 간단하고 사소한 함수 일뿐입니다. 유형의 생성자를 인수로 전달할 때 그 유형에 대한 식별 기능이됩니다. (사소한 것은 같은 foo f z xs = xs것이 허용되지 않음을 의미합니다 .)

이것은 매우 중요합니다. 내가 그것에 대해 생각하는 두 가지 방법은 다음과 같습니다.

1. 주어진 유형의 접기는 해당 유형의 값에 포함 된 모든 정보를 "볼"수 있습니다. (이것이 유형의 생성자를 사용하여 처음부터 해당 유형의 모든 값을 완벽하게 "재구성"할 수있는 이유입니다.)
2. 접기는 해당 유형에 대한 가장 일반적인 "소비자"기능입니다. 해당 유형의 값을 사용하는 모든 함수를 작성하여 해당 유형에서 사용하는 유일한 작업은 fold 및 생성자입니다. (일부 기능의 배 전용 버전이 쓰기에 어려운 심하게 수행하지만, 시도의 쓰기 tail :: [a] -> [a]와 foldr, (:)하고 []. 고통스러운 운동 등)

두 번째 요점은 생성자가 필요하지 않다는 점에서 훨씬 더 나아갑니다. data선언이나 생성자를 사용하지 않고 폴드 만 사용 하여 모든 대수 유형을 구현할 수 있습니다 .

{-# LANGUAGE RankNTypes #-}

-- | A Church-encoded list is a function that takes the two 'foldr' arguments
-- and produces a result from them.
newtype ChurchList a = 
    ChurchList { runList :: forall r. 
                            (a -> r -> r)  -- ^ first arg of 'foldr'
                         -> r              -- ^ second arg of 'foldr'
                         -> r              -- ^ 'foldr' result
               }

-- | Convenience function: make a ChurchList out of a regular list
toChurchList :: [a] -> ChurchList a
toChurchList xs = ChurchList (\kons knil -> foldr kons knil xs)

-- | 'toChurchList' isn't actually needed, however, we can make do without '[]'
-- completely.
cons :: a -> ChurchList a -> ChurchList a
cons x xs = ChurchList (\f z -> f x (runlist xs f z))

nil :: ChurchList a
nil = ChurchList (\f z -> z)

foldr' :: (a -> r -> r) -> r -> ChurchList a -> r
foldr' f z xs = runList xs f z

head :: ChurchList a -> Maybe a
head = foldr' ((Just .) . const) Nothing

append :: ChurchList a -> ChurchList a -> ChurchList a
append xs ys = foldr' cons ys xs

-- | Convert a 'ChurchList' to a regular list.
fromChurchList :: ChurchList a -> [a]
fromChurchList xs = runList xs (:) []

연습으로 이런 방식으로 다른 유형을 작성해 볼 수 있습니다 ( RankNTypes확장자 를 사용합니다 . 입문서를 읽으십시오 ). 이 기술을 Church 인코딩 이라고 하며 실제 프로그래밍에서 유용 할 때가 있습니다. 예를 들어 GHC는 foldr/ buildfusion 이라는 것을 사용 하여 목록 코드를 최적화하여 중간 목록을 제거합니다. 볼 이 하스켈 위키 페이지를 , 그리고 종류를주의 build:

build :: (forall b. (a -> b -> b) -> b -> b) -> [a]
build g = g (:) []

를 제외하고는 위와 newtype동일 fromChurchList합니다. 기본적으로 GHC가 목록 처리 코드를 최적화하는 데 사용하는 규칙 중 하나는 다음과 같습니다.

-- Don't materialize the list if all we're going to do with it is
-- fold it right away:
foldr kons knil (fromChurchList xs) ==> runChurchList xs kons knil

내부적으로 교회 인코딩을 사용하는 기본 목록 함수를 구현하고, 그 정의를 적극적으로 인라인하고,이 규칙을 인라인 코드에 적용함으로써 같은 함수의 중첩 된 사용을 map긴밀한 루프로 통합 할 수 있습니다.

---

모든 경우를위한 접기

우리는 실제로 다양한 유형의 전체에 적용 할 수있는 접기의 일반적인 개념을 생각 해낼 수 있습니다. 즉, fold목록, 트리 등에 대한 함수를 체계적으로 정의 할 수 있습니다 .

이 일반적인 개념은 fold그의 의견에서 언급 한 @pelotom의 catamorphisms 에 해당합니다.

재귀 유형

핵심 통찰력은 이러한 fold함수가 재귀 유형을 통해 정의 된다는 것 입니다. 특히:

data List a = Cons a (List a) | Nil
data Tree a = Branch (Tree a) (Tree a) | Leaf a

이러한 유형은 모두 분명 recursive-- 있습니다 List의 Cons경우와 Tree의 Branch경우.

고정 포인트

함수와 마찬가지로 고정 소수점을 사용하여 이러한 유형을 다시 작성할 수 있습니다. 다음의 정의를 기억하십시오 fix.

fix f = f (fix f)

추가 생성자 래퍼가 있어야한다는 점을 제외하면 실제로 유형에 대해 매우 유사한 것을 작성할 수 있습니다.

newtype Fix f = Roll (f (Fix f))

함수fix 의 고정 점을 정의하는 것과 마찬가지로 이것은 펑터 의 고정 점을 정의합니다 . 이 새로운 유형을 사용하여 모든 재귀 유형을 표현할 수 있습니다 .Fix

이를 통해 List다음과 같이 유형 을 다시 작성할 수 있습니다.

data ListContainer a rest = Cons a rest | Nil
type List a = Fix (ListContainer a)

기본적으로 s를 임의의 깊이 Fix에 중첩 할 수 있습니다 ListContainer. 그래서 우리는 다음을 가질 수 있습니다.

Roll Nil
Roll (Cons 1 (Roll Nil))
Roll (Cons 1 (Roll (Cons 2 (Roll Nil))))

대응하는 [], [1]그리고 [1,2]각각.

즉 보는 ListContainer것은 a는 Functor간단합니다 :

instance Functor (ListContainer a) where
  fmap f (Cons a rest) = Cons a (f rest)
  fmap f Nil           = Nil

에서 ListContainerto 까지의 매핑 List은 매우 자연 스럽다고 생각합니다 . 명시 적으로 재귀하는 대신 재귀 부분을 변수로 만듭니다. 그런 다음 Fix해당 변수를 적절하게 채우기 위해 사용 합니다.

유사한 유형도 작성할 수 Tree있습니다.

고정 점 "풀기"

그렇다면 우리는 왜 신경을 쓰나요? 를 사용하여 작성된 임의 유형에 fold대해 정의 할 수 있습니다 . 특히:Fix

fold :: Functor f => (f a -> a) -> (Fix f -> a)
fold h = h . fmap (fold h) . unRoll
  where unRoll (Roll a) = a

기본적으로 접기가 수행하는 모든 작업은 "롤링 된"유형을 한 번에 한 레이어 씩 풀고 매번 결과에 함수를 적용하는 것입니다. 이 "언 롤링"을 통해 모든 재귀 유형에 대해 접기를 정의하고 개념을 깔끔하고 자연스럽게 일반화 할 수 있습니다.

목록 예제의 경우 다음과 같이 작동합니다.

1. At each step, we unwrap the Roll to get either a Cons or a Nil
2. We recurse over the rest of the list using fmap.
   1. In the Nil case, fmap (fold h) Nil = Nil, so we just return Nil.
   2. In the Cons case, the fmap just continues the fold over the rest of the list.
3. In the end, we get a bunch of nested calls to fold ending in a Nil--just like the standard foldr.

Comparing Types

Now lets look at the types of the two fold functions. First, foldr:

foldr :: (a -> b -> b) -> b -> [a] -> b

Now, fold specialized to ListContainer:

fold :: (ListContainer a b -> b) -> (Fix (ListContainer a) -> b)

At first, these look completely different. However, with a bit of massaging, we can show they're the same. The first two arguments to foldr are a -> b -> b and b. We have a function and a constant. We can think of b as () -> b. Now we have two functions _ -> b where _ is () and a -> b. To make life simpler, let's curry the second function giving us (a, b) -> b. Now we can write them as a single function using Either:

Either (a, b) () -> b

This is true because given f :: a -> c and g :: b -> c, we can always write the following:

h :: Either a b -> c
h (Left a) = f a
h (Right b) = g b

So now we can view foldr as:

foldr :: (Either (a, b) () -> b) -> ([a] -> b)

(We are always free to add parentheses around -> like this as long as they're right-associative.)

Now lets look at ListContainer. This type has two cases: Nil, which carries no information and Cons, which has both an a and a b. Put another way, Nil is like () and Cons is like (a, b), so we can write:

type ListContainer a rest = Either (a, rest) ()

Clearly this is the same as what I used in foldr above. So now we have:

foldr :: (Either (a, b) () -> b) -> ([a] -> b)
fold  :: (Either (a, b) () -> b) -> (List a -> b)

So, in fact, the types are isomorphic--just different ways of writing the same thing! I think that's pretty cool.

(As a side note, if you want to know more about this sort of reasoning with types, check out The Algebra of Algebraic Data Types, a nice series of blog posts about just this.)

Back to Trees

So, we've seen how we can define a generic fold for types written as fixed points. We've also seen how this corresponds directly to foldr for lists. Now lets look at your second example, the binary tree. We have the type:

data Tree a = Branch a (Tree a) (Tree a) | Leaf a

we can rewrite this using Fix by following the rules I did above: we replace the recursive part with a type variable:

data TreeContainer a rest = Branch rest rest | Leaf a
type Tree a = Fix (TreeContainer a)

Now we have a tree fold:

fold :: (TreeContainer a b -> b) -> (Tree a -> b)

Your original foldTree looks like this:

foldTree :: (b -> b -> b) -> (a -> b) -> Tree a -> b

foldTree accepts two functions; we'll combine the into one by first currying and then using Either:

foldTree :: (Either (b, b) a -> b) -> (Tree a -> b)

We can also see how Either (b, b) a is isomorphic to TreeContainer a b. Tree container has two cases: Branch, containing two bs and Leaf, containing one a.

So these fold types are isomorphic in the same way as the list example.

Generalizing

There is a clear pattern emerging. Given a normal recursive data type, we can systematically create a non-recursive version of the type, which lets us express the type as a fixed point of a functor. This means that we can mechanically come up with fold functions for all these different types--in fact, we could probably automate the entire process using GHC Generics or something like that.

In a sense, this means that we do not really have different fold functions for different types. Rather, we have a single fold function which is very polymorphic.

More

I first fully understood these ideas from a talk given by Conal Elliott. This goes into more detail and also talks about unfold, which is the dual to fold.

If you want to delve into this sort of thing even more deeply, read the fantastic "Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire" paper. Among other things, this introduces the notions of "catamorphisms" and "anamorphisms" which correspond to folds and unfolds.

Algebras (and Coalgebras)

Also, I can't resist adding a plug for myself :P. You can see some interesting similarities between the way we use Either here and the way I used it when talking about algebras in another SO answer.

There is in fact a deep connection between fold and algebras; moreover, unfold--the aforementioned dual of fold--is connected to coalgebras, which are the dual of algebras. The important idea is that algebraic data types correspond to "initial algebras" which also define folds as outlined in the rest of my answer.

You can see this connection in the general type of fold:

fold :: Functor f => (f a -> a) -> (Fix f -> a)

The f a -> a term looks very familiar! Remember that an f-algebra was defined as something like:

class Functor f => Algebra f a where
  op :: f a -> a

So we can think of fold as just:

fold :: Algebra f a => Fix f -> a

Essentially, fold just lets us "summarize" structures defined using the algebra.

---

A fold replaces every constructor with a function.

For example, foldr cons nil replaces every (:) with cons and [] with nil:

foldr cons nil ((:) 1 ((:) 2 [])) = cons 1 (cons 2 nil)

For a tree, foldTree branch leaf replaces every Branch with branch and every Leaf with leaf:

foldTree branch leaf (Branch (Branch (Leaf 1) (Leaf 2)) (Leaf 3))
    = branch (branch (leaf 1) (leaf 2)) (leaf 2)

This is why every fold accepts arguments that have the exact same type as the constructors:

foldr :: (a -> list -> list) -> list -> [a] -> list

foldTree :: (tree -> tree -> tree) -> (a -> tree) -> Tree a -> tree

---

I would call this a fold, and declare Tree a Foldable. See the Foldable example in the GHC docs.

참고URL : https://stackoverflow.com/questions/16426463/what-constitutes-a-fold-for-types-other-than-list