[haskell] foldr를 사용하여 foldl 작성

몇 가지 설명이 순서대로 있습니다!

ID 기능은 무엇입니까? 의 역할은 무엇입니까? 여기에 왜 필요합니까?

id은 IS 항등 함수 , id x = x및 함수와 체인 구축 될 때 제로의 당량으로 사용되는 기능 조성물 , (.). Prelude에서 정의 된 것을 찾을 수 있습니다 .

위의 예에서 id 함수는 람다 함수의 누산기입니까?

누산기는 반복 기능 적용을 통해 구축되는 기능입니다. 누산기의 이름을 step. 원하는 경우 람다로 작성할 수 있습니다.

foldl f a bs = foldr (\b g x -> g (f x b)) id bs a

또는 Graham Hutton이 다음 과 같이 작성했습니다 .

5.1 foldl운영자

이제 suml예제 에서 일반화하고 값을 결합 foldl하는 함수 f와 v시작 값으로 값을 사용하여 왼쪽에서 오른쪽 순서로 목록의 요소를 처리 하는 표준 연산자 를 고려해 보겠습니다 .

foldl :: (β → α → β) → β → ([α] → β)
foldl f v [ ] = v
foldl f v (x : xs) = foldl f (f v x) xs

이 연산자를 사용하면 suml간단히 suml = foldl (+) 0. 다른 많은 함수는를 사용하여 간단한 방법으로 정의 할 수 있습니다 foldl. 예를 들어, 다음과 같이 표준 함수 reverse를 재정의 할 수 있습니다 foldl.

reverse :: [α] → [α]
reverse = foldl (λxs x → x : xs) [ ]

이 정의는 (++)목록에 비효율적 인 추가 연산자 를 사용하지 않기 때문에 접기를 사용하는 원래 정의보다 효율적 입니다.

함수에 대해 이전 섹션에서 계산의 간단한 일반화 suml함수를 재정의하는 방법을 foldl환산 fold:

foldl f v xs = fold (λx g → (λa → g (f a x))) id xs v

반대로, 목록 인수의 꼬리 부분은 엄격하지만 그렇지 않은 사실 때문에의
fold관점 에서 재정의 할 수 없습니다. 및 에 관한 유용한 ‘이중성 정리’ 가 많이 있으며 특정 응용 프로그램에 가장 적합한 연산자를 결정하기위한 몇 가지 지침도 있습니다 (Bird, 1998).foldlfoldlfoldfoldfoldl

foldr의 프로토 타입은 foldr :: (a-> b-> b)-> b-> [a]-> b

하스켈 프로그래머는 것을 말할 것입니다 타입 의가 foldr있다 (a -> b -> b) -> b -> [a] -> b.

첫 번째 매개 변수는 두 개의 매개 변수가 필요한 함수이지만 myFoldl 구현의 단계 함수는 3 개의 매개 변수를 사용하므로 완전히 혼란 스럽습니다.

이것은 혼란스럽고 마술 적입니다! 우리는 속임수를 사용하고 누산기를 함수로 대체합니다. 그러면 결과를 산출하기 위해 초기 값에 적용됩니다.

그레이엄 허튼 설정하는 트릭 설명 foldl에 foldr위의 문서에 있습니다. 다음과 같은 재귀 적 정의를 작성하는 것으로 시작합니다 foldl.

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f v []       = v
foldl f v (x : xs) = foldl f (f v x) xs

그런 다음에 대한 정적 인수 변환을 통해 리팩터링합니다 f.

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f v xs = g xs v
    where
        g []     v = v
        g (x:xs) v = g xs (f v x)

이제 안쪽으로 g플로팅하도록 다시 작성해 보겠습니다 v.

foldl f v xs = g xs v
    where
        g []     = \v -> v
        g (x:xs) = \v -> g xs (f v x)

이것은 g함수를 반환하는 하나의 인수의 함수 로 생각하는 것과 같습니다.

foldl f v xs = g xs v
    where
        g []     = id
        g (x:xs) = \v -> g xs (f v x)

이제 우리는 g리스트를 재귀 적으로 걷는 함수를 가지고 있고, 어떤 함수를 적용합니다 f. 최종 값은 식별 함수이며 각 단계는 함수도 생성합니다.

그러나 , 우리는 이미 목록에 매우 유사한 재귀 함수를 가지고 있습니다 foldr.!

2 접기 연산자

fold를 사용하는 동안 작업자는, 재귀 이론 (Kleene, 1952)에서 그 기원을 가지고 fold프로그래밍 언어 날짜의 중심 개념으로는 APL의 감소 연산자 (아이버슨, 1962)에 백업하고, 나중에 FP의 삽입 운영자에 (배 커스를 , 1978). Haskell에서 fold목록 연산자는 다음과 같이 정의 할 수 있습니다.

fold :: (α → β → β) → β → ([α] → β)
fold f v [ ] = v
fold f v (x : xs) = f x (fold f v xs)

즉,이 함수 주어진 f유형 α → β → β및 값 v유형을 β상기 함수
fold f v유형의리스트를 처리하는 [α]타입의 값을 수득 βNIL로 생성자를 대체함으로써 []값으로 목록의 마지막에 v, 각각의 단점 생성자 (:)목록 내의하여 기능 f. 이러한 방식으로 fold연산자는 목록 처리를위한 간단한 재귀 패턴을 캡슐화합니다. 여기서 목록에 대한 두 생성자는 단순히 다른 값과 함수로 대체됩니다. 목록에서 익숙한 많은 함수는 fold.

이것은 우리 g함수 와 매우 유사한 재귀 체계처럼 보입니다 . 이제 트릭 : 사용 가능한 모든 마법 (일명 Bird, Meertens 및 Malcolm)을 사용 하여 fold 의 보편적 속성 인 특수 규칙을 적용합니다.이 규칙 은 g목록을 처리 하는 함수에 대한 두 정의 간의 동등성입니다 .

g [] = v
g (x:xs) = f x (g xs)

경우에만

g = fold f v

따라서 폴드의 보편적 인 속성은 다음과 같습니다.

    g = foldr k v

여기서 g몇 가지를 들어,이 방정식에 해당해야합니다 k및 v:

    g []     = v
    g (x:xs) = k x (g xs)

이전 foldl 디자인에서 우리는 v == id. 두 번째 방정식의 경우 다음 의 정의 를 계산 해야합니다 k.

    g (x:xs)         = k x (g xs)
<=> g (x:xs) v       = k x (g xs) v      -- accumulator of functions
<=> g xs (f v x)     = k x (g xs) v      -- definition of foldl
<=  g' (f v x)       = k x g' v          -- generalize (g xs) to g'
<=> k = \x g' -> (\a -> g' (f v x))      -- expand k. recursion captured in g'

계산 된 정의 k와 vfoldl의 정의를 다음과 같이 대체하면 다음과 같습니다.

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f v xs =
    foldr
        (\x g -> (\a -> g (f v x)))
        id
        xs
        v

recursive g는 foldr combinator로 대체되고 accumulator는 f역순으로 목록의 각 요소에서 구성 체인을 통해 빌드 된 함수가됩니다 (따라서 오른쪽 대신 왼쪽으로 접습니다).

이것은 확실히 다소 진보 된 것이므로 , 변형을 가능하게하는 fold 의 보편적 인 속성 인 이 변형을 깊이 이해하기 위해 아래 링크 된 Hutton의 튜토리얼을 추천합니다.

---

참고 문헌

• Haskell Wiki : Foldl as foldr
• 접기의 보편성과 표현성에 대한 튜토리얼 , Graham Hutton, J. Functional Programming 9 (4) : 355-372, 1999 년 7 월.
• Malcolm, G. 대수 데이터 유형 및 프로그램 변환. , Groningen University 박사 논문.