Haskell Foldr 기능을 작성하는 올바른 방법입니까?

Question

나는 운동을하고 있었다 Yaht의 재귀 데이터 유형 섹션을 찾았습니다 listFoldr 약간 도전적인 기능 (주로 내가 실제로 차이를 이해하지 못했기 때문에 foldl 그리고 foldr 처음에는). 마침내 어떻게 정확히 어떻게 깨달았을 때 foldr 기능이 작동하면 listFoldl a listFoldr 기능:

listFoldl f i [] = i
listFoldl f i (x:xs) = listFoldl f (f i x) xs

listFoldr f i [] = i
listFoldr f i (x:xs) = listFoldr f (f x i) xs

이것은 작동하는 것으로 보입니다 (이것보다 더 많은 테스트를 수행했습니다).

Main> foldr (-) 4 [1, 2, 3]
-2
Main> listFoldr (-) 4 [1, 2, 3]
-2

하지만 해결책 운동을 위해 주어진 것은 내 것과 크게 다릅니다. 그들의 listFoldl 내 것과 정확히 동일하지만 그들의 listFoldr:

listFoldr f i [] = i
listFoldr f i (x:xs) = f x (listFoldr f i xs)

어떤 솔루션이 더 나은지, 내 또는 그들의 솔루션은 무엇입니까? 그들 중 하나가 틀렸습니까? (내 테스트에서 둘 다 똑같은 결과로 끝납니다 ...)

Answer 1

나는 당신이 '반대 순서'에서 요소를 처리하고 있다고 생각합니다. 그래서 당신은 옳지 않습니다.

'주문'이 중요한 예를 가지고 이것을 시연 할 수 있어야합니다. 예를 들어, 같은 것입니다

listfoldr f "" ["a", "b", "c"]

여기서 'f'는

f s1 s2 = "now processing f(" @ s1 @ "," @ s2 @ ")\n"

여기서 '@'는 String-Append 연산자입니다 (Haskell에있는 것을 잊어 버립니다). 요점은 단지 기능을 '악기'하는 것입니다.이 기능은 다양한 Args와 함께 어떤 순서를 호출하는지 알 수 있습니다.

(수학 "4-1-2-3"은 "4-3-2-1"과 같은 대답을 생성하기 때문에 이것은 예에 나타나지 않았다는 점에 유의하십시오.)

Answer 2

솔루션이 확실히 잘못되었습니다. 당신은 단순히 구현했습니다 foldl 기능 f 반대 순서로 논쟁을 취합니다. 예를 들어 무엇이 잘못되었는지, foldr (:) [] 목록에서 식별 기능이어야하지만 기능이 목록을 뒤집습니다. 당신의 기능이 아닌 다른 이유가 많이 있습니다. foldr, 어떻게 foldr 무한 목록에서 작동하며 귀하의 것은 그렇지 않습니다. 그들이 당신의 예에서 동일하다는 것은 순수한 우연의 일치입니다. 3 - (2 - (1 - 4)) == 1 - (2 - (3 - 4)). 처음부터 시작하여 어떻게 foldr 작동해야합니다.

Answer 3

당신의 것은 깨졌습니다. 단일 숫자 결과로 끝나지 않는 무언가로 시도하십시오.

eg: listFoldr (++) "a" ["b", "c", "d"]

당신은 잘못된 방향으로 처리하고 있습니다.

Answer 4

목록에 [x1, x2, ..., xk], 당신의 listFoldr 계산합니다

 f xk (... (f x2 (f x1 i)) ...)

반면 foldr 계산해야합니다

 f x1 (f x2 (... (f xk i) ...))

(이에 비해 foldl 계산합니다

f (... (f (f i x1) x2) ...) xk

본질적으로, listFoldr f = foldl (flip f).)

당신은 테스트 케이스가 불행한 일이기 때문입니다

3 - (2 - (1 - 4)) = 1 - (2  - (3 - 4))

이와 같은 기능을 테스트 할 때는 f 이는 비 통신 및 비 연관적 (즉, 인수 및 응용 순서 주문)이므로 표현이 올바르게 평가되는지 확인할 수 있습니다. 물론, 뺄셈은 비 통신적이고 비 연관적이며 당신은 단지 운이 좋았습니다.