foldr를 사용하여 foldl 작성

foldr를 사용하여 foldl 작성

---

에서 실제 세계 하스켈 에 제 4 장 기능 프로그래밍 :

foldr로 foldl 작성 :

-- file: ch04/Fold.hs
myFoldl :: (a -> b -> a) -> a -> [b] -> a

myFoldl f z xs = foldr step id xs z
    where step x g a = g (f a x)

위의 코드는 저를 많이 혼란스럽게했고 dps 라는 누군가 가 좀 더 명확하게하기 위해 의미있는 이름으로 다시 작성했습니다.

myFoldl stepL zeroL xs = (foldr stepR id xs) zeroL
where stepR lastL accR accInitL = accR (stepL accInitL lastL)

다른 사람 Jef G는 예제를 제공하고 기본 메커니즘을 단계별로 보여줌으로써 훌륭한 작업을 수행했습니다.

myFoldl (+) 0 [1, 2, 3]
= (foldR step id [1, 2, 3]) 0
= (step 1 (step 2 (step 3 id))) 0
= (step 1 (step 2 (\a3 -> id ((+) a3 3)))) 0
= (step 1 (\a2 -> (\a3 -> id ((+) a3 3)) ((+) a2 2))) 0
= (\a1 -> (\a2 -> (\a3 -> id ((+) a3 3)) ((+) a2 2)) ((+) a1 1)) 0
= (\a1 -> (\a2 -> (\a3 -> (+) a3 3) ((+) a2 2)) ((+) a1 1)) 0
= (\a1 -> (\a2 -> (+) ((+) a2 2) 3) ((+) a1 1)) 0
= (\a1 -> (+) ((+) ((+) a1 1) 2) 3) 0
= (+) ((+) ((+) 0 1) 2) 3
= ((0 + 1) + 2) + 3

하지만 여전히 완전히 이해할 수 없습니다. 여기에 내 질문이 있습니다.

1. ID 기능은 무엇입니까? 의 역할은 무엇입니까? 여기에 왜 필요합니까?
2. 위의 예에서 id 함수는 람다 함수의 누산기입니까?
3. foldr의 프로토 타입은 foldr :: (a -> b -> b) -> b -> [a] -> b이고 첫 번째 매개 변수는 두 개의 매개 변수가 필요한 함수이지만 myFoldl 구현의 단계 함수는 3 개의 매개 변수를 사용합니다. 완전히 혼란 스럽습니다!

---

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

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)

이전 폴더 디자인에서 우리는 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 박사 논문.

---

다음 유형을 고려하십시오 foldr.

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

유형 반면으로는 step같은 것입니다 b -> (a -> a) -> a -> a. 단계가로 전달 foldr되었으므로이 경우 폴드의 유형이 (b -> (a -> a) -> (a -> a)) -> (a -> a) -> [b] -> (a -> a).

a다른 시그니처 의 다른 의미에 혼동하지 마십시오 . 유형 변수 일뿐입니다. 또한, 그래서 함수의 화살표를 잘 연관 있음을 알아 두셔야 a -> b -> c과 같은 일이다 a -> (b -> c).

예,의 누산기 값 은 유형 foldr의 함수 이고 a -> a초기 값은 id입니다. 이것은 id아무 일도하지 않는 함수 이기 때문에 의미 가 있습니다. 목록의 모든 값을 추가 할 때 초기 값으로 0으로 시작하는 것과 같은 이유입니다.

step세 가지 인수 를 취하려면 다음과 같이 다시 작성하십시오.

step :: b -> (a -> a) -> (a -> a)
step x g = \a -> g (f a x)

무슨 일이 일어나고 있는지 더 쉽게 볼 수 있습니까? 함수를 반환하기 때문에 추가 매개 변수가 필요하며이를 작성하는 두 가지 방법은 동일합니다. 또한 후 추가 매개 변수를 참고 foldr: (foldr step id xs) z. 괄호 안의 부분은 폴드 자체로 함수를 반환 한 다음에 적용됩니다 z.

---

^{(내 대답 [1] , [2] , [3] , [4] 을 빠르게 훑어 보면서 Haskell의 구문, 고차 함수, 커링, 함수 구성, $ 연산자, 중위 / 접두사 연산자, 섹션 및 람다를 이해했는지 확인하십시오. )}

접힘의 보편적 인 속성

배는 재귀의 특정 종류의 단지 법전 편찬이다. 그리고 보편성 속성은 단순히 재귀가 특정 형식을 따르면 일부 공식 규칙에 따라 폴드로 변환 될 수 있음을 나타냅니다. 반대로 모든 폴드는 그런 종류의 재귀로 변형 될 수 있습니다. 다시 한 번, 일부 재귀는 정확히 동일한 답을 제공하는 접기로 변환 될 수 있지만 일부 재귀는 불가능하며이를 수행하는 정확한 절차가 있습니다.

당신의 재귀 함수가 보이는에 같은 목록에 작동하는 경우 기본적으로, 왼쪽 , 하나에게 폴드를 변환 할 수 있는 권리를 대체 f하고 v거기에 실제로이 무엇인지에 대해.

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

예를 들면 :

sum []     = 0   {- recursion becomes fold -}
sum (x:xs) = x + sum xs   ⇒     sum = foldr 0 (+)

다음 v = 0과 sum (x:xs) = x + sum xs동등 sum (x:xs) = (+) x (sum xs)하므로 f = (+). 2 개 더보기

product []     = 1
product (x:xs) = x * product xs  ⇒  product = foldr 1 (*)

length []     = 0
length (x:xs) = 1 + length xs    ⇒  length = foldr (\_ a -> 1 + a) 0

운동:

1. 구현 map, filter, reverse, concat및 concatMap재귀 막에 상기와 같은 기능을 왼쪽 측면.

2. 위의 공식 , 즉 대체 f및 오른쪽v 의 접기 공식에 따라이 5 가지 함수를 foldr로 변환합니다 .

foldr를 통한 Foldl

왼쪽에서 오른쪽으로 숫자를 합산하는 재귀 함수를 작성하는 방법은 무엇입니까?

sum [] = 0     -- given `sum [1,2,3]` expands into `(1 + (2 + 3))`
sum (x:xs) = x + sum xs

찾기 위해 오는 첫 번째 재귀 함수는 합산을 시작하기 전에 완전히 확장됩니다. 그것은 우리가 필요로하는 것이 아닙니다. 한 가지 접근 방식은 각 단계에서 즉시 숫자를 더하는 accumulator 가있는 재귀 함수를 만드는 것입니다 ( 재귀 전략에 대해 자세히 알아 보려면 꼬리 재귀 에 대해 읽어보십시오 ).

suml :: [a] -> a
suml xs = suml' xs 0
  where suml' [] n = n   -- auxiliary function
        suml' (x:xs) n = suml' xs (n+x)

좋아, 그만! GHCi에서이 코드를 실행하고 작동 방식을 이해했는지 확인한 다음 신중하고 신중하게 진행하십시오. suml접기로 재정의 할 수는 없지만 그럴 suml'수 있습니다.

suml' []       = v    -- equivalent: v n = n
suml' (x:xs) n = f x (suml' xs) n

suml' [] n = n함수 정의에서 그렇죠? 그리고 v = suml' []보편적 속성 공식에서. 함께 이것은 v n = n수신하는 모든 것을 즉시 반환하는 함수를 제공합니다 v = id. 계산해 봅시다 f.

suml' (x:xs) n = f x (suml' xs) n
-- expand suml' definition
suml' xs (n+x) = f x (suml' xs) n
-- replace `suml' xs` with `g`
g (n+x)        = f x g n

따라서 suml' = foldr (\x g n -> g (n+x)) id, 따라서, suml = foldr (\x g n -> g (n+x)) id xs 0.

foldr (\x g n -> g (n + x)) id [1..10] 0 -- return 55

Now we just need to generalize, replace + by a variable function:

foldl f a xs = foldr (\x g n -> g (n `f` x)) id xs a
foldl (-) 10 [1..5] -- returns -5

Conclusion

Now read Graham Hutton's A tutorial on the universality and expressiveness of fold. Get some pen and paper, try to figure everything that he writes until you get derive most of the folds by yourself. Don't sweat if you don't understand something, you can always return later, but don't procrastinate much either.

---

Here's my proof that foldl can be expressed in terms of foldr, which I find pretty simple apart from the name spaghetti the step function introduces.

The proposition is that foldl f z xs is equivalent to

myfoldl f z xs = foldr step_f id xs z
        where step_f x g a = g (f a x)

The first important thing to notice here is that the right hand side of the first line is actually evaluated as

(foldr step_f id xs) z

since foldr only takes three parameters. This already hints that the foldr will calculate not a value but a curried function, which is then applied to z. There are two cases to investigate to find out whether myfoldl is foldl:

1. Base case: empty list

     myfoldl f z []
   = foldr step_f id [] z    (by definition of myfoldl)
   = id z                    (by definition of foldr)
   = z
   
     foldl f z []
   = z                       (by definition of foldl)
   

2. Non-empty list

     myfoldl f z (x:xs)
   = foldr step_f id (x:xs) z          (by definition of myfoldl)
   = step_f x (foldr step_f id xs) z   (-> apply step_f)
   = (foldr step_f id xs) (f z x)      (-> remove parentheses)
   = foldr step_f id xs (f z x)
   = myfoldl f (f z x) xs              (definition of myfoldl)
   
     foldl f z (x:xs)
   = foldl f (f z x) xs
   

Since in 2. the first and the last line have the same form in both cases, it can be used to fold the list down until xs == [], in which case 1. guarantees the same result. So by induction, myfoldl == foldl.

---

There is no Royal Road to Mathematics, nor even through Haskell. Let

h z = (foldr step id xs) z where   
     step x g =  \a -> g (f a x)

What the heck is h z? Assume that xs = [x0, x1, x2].
Apply the definition of foldr:

h z = (step x0 (step x1 (step x2 id))) z 

Apply the definition of step:

= (\a0 -> (\a1 -> (\a2 -> id (f a2 x2)) (f a1 x1)) (f a0 x0)) z

Substitute into the lambda functions:

= (\a1 -> (\a2 -> id (f a2 x2)) (f a1 x1)) (f z x0)

= (\a2 -> id (f a2 x2)) (f (f z x0) x1)

= id (f (f (f z x0) x1) x2)

Apply definition of id :

= f (f (f z x0) x1) x2

Apply definition of foldl :

= foldl f z [x0, x1, x2]

Is it a Royal Road or what?

---

This might help, I tried expanding in a different way.

myFoldl (+) 0 [1,2,3] = 
foldr step id [1,2,3] 0 = 
foldr step (\a -> id (a+3)) [1,2] 0 = 
foldr step (\b -> (\a -> id (a+3)) (b+2)) [1] 0 = 
foldr step (\b -> id ((b+2)+3)) [1] 0 = 
foldr step (\c -> (\b -> id ((b+2)+3)) (c+1)) [] 0 = 
foldr step (\c -> id (((c+1)+2)+3)) [] 0 = 
(\c -> id (((c+1)+2)+3)) 0 = ...

---

foldr step zero (x:xs) = step x (foldr step zero xs)
foldr _ zero []        = zero

myFold f z xs = foldr step id xs z
  where step x g a = g (f a x)

myFold (+) 0 [1, 2, 3] =
  foldr step id [1, 2, 3] 0
  -- Expanding foldr function
  step 1 (foldr step id [2, 3]) 0
  step 1 (step 2 (foldr step id [3])) 0
  step 1 (step 2 (step 3 (foldr step id []))) 0
  -- Expanding step function if it is possible
  step 1 (step 2 (step 3 id)) 0
  step 2 (step 3 id) (0 + 1)
  step 3 id ((0 + 1) + 2)
  id (((0 + 1) + 2) + 3)

Well, at least, this helped me. Even it is not quite right.

참고URL : https://stackoverflow.com/questions/6172004/writing-foldl-using-foldr