foldr을 사용하여 zip 구현

Question

저는 현재 Real World Haskell의 4장을 읽고 있습니다. Foldr의 관점에서 Foldl 구현.

(코드는 다음과 같습니다.)

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)

구현해볼까 생각했는데 zip 같은 기술을 사용하고 있지만 아무런 진전이 없는 것 같습니다.심지어 가능합니까?

Answer 1

zip2 xs ys = foldr step done xs ys
  where done ys = []
        step x zipsfn []     = []
        step x zipsfn (y:ys) = (x, y) : (zipsfn ys)

이것이 작동하는 방법 : (Foldr Step Done XS) YS를 소비하는 함수를 반환합니다. 그래서 우리는 XS 목록을 따라 내려갑니다.

그것을 생각해내는 방법 : 나는 일반적인 아이디어로 시작했습니다 (이전에 본 비슷한 예에서)

zip2 xs ys = foldr step done xs ys

그런 다음 유형과 값을 올바르게 나오기 위해 다음 줄을 차례로 채웠습니다. 더 어려운 사례보다 먼저 가장 간단한 사례를 고려하는 것이 가장 쉬웠습니다.

첫 번째 줄은 더 간단하게 작성할 수 있습니다

zip2 = foldr step done

Mattiast가 보여준 것처럼.

Answer 2

답은 이미 여기에 주어졌지만 (예시적인) 파생물은 아닙니다. 그래서이 세월이 지난 후에도 추가 할 가치가있을 것입니다.

실제로 아주 간단합니다. 첫 번째,

foldr f z xs 
   = foldr f z [x1,x2,x3,...,xn] = f x1 (foldr fz [x2, x3, ..., xn]))
   = ... = f x1 (F X2 (F X3 (... (F Xn Z)))))))

따라서 Eta-expansion에 의해

foldr f z xs ys
   = foldr f z [x1,x2,x3,...,xn] ys = f x1 (foldr f z [x2,x3,...,xn]) ys
   = ... = f x1 (F X2 (F X3 (... (F Xn Z))))))) ys

여기서 명백한 것처럼 만약에 f 두 번째 논쟁에서 비정규입니다, 그것은 작동합니다 첫 번째 ~에 x1 그리고 ys, f x1r1ys 어디 r1 =(f x2 (f x3 (... (f xn z) ...)))= foldr f z [x2,x3,...,xn].

그래서 사용

f x1 R1 [] = []
f x1 R1 (y1:ys1) = (x1,y1) : R1 ys1

우리는 정보의 통과를 준비합니다 왼쪽에서 오른쪽으로 목록을 따라 부름 r1 이랑 쉬다 입력 목록의 ys1, foldr f z [x2,x3,...,xn]ys1 = f x2r2ys1, 다음 단계로. 그리고 그게 그게 다.

---

언제 ys 보다 짧습니다 xs (또는 같은 길이), [] 사례 f 화재와 처리 중단. 그러나 만약 ys 보다 길다 xs 그 다음에 f'에스 [] 사례는 발사되지 않고 결승에 진출 할 것입니다 f xnz(yn:ysn) 신청,

f xn 지 (yn:ysn) = (xn,yn) : 지 ysn

우리가 끝났기 때문에 xs,, zip 처리가 중지되어야합니다.

지 _ = []

그리고 이것은 정의를 의미합니다 z = const [] 사용되어야한다:

zip xs ys = foldr f (const []) xs ys
  where
    f x r []     = []
    f x r (y:ys) = (x,y) : r ys

의 관점에서 f, r a의 역할을 수행합니다 성공 연속, 어느 f 처리가 계속 될 때 전화, 쌍을 방출 한 후 (x,y).

그래서 r ~이다 "더 많은 일은 ys 더 많은 경우 x에스", 그리고 z = const [],, nil-가방 foldr, 이다 "무엇이 끝났는가 ys 더 이상 없을 때 x에스". 또는 f 그 자체로 멈출 수 있습니다 [] 언제 ys 소진되었습니다.

---

방법에 주목하십시오 ys 목록을 따라 왼쪽에서 오른쪽으로 전달되는 일종의 축적 값으로 사용됩니다. xs, 하나의 호출에서 f 다음으로 ( "축적"단계는 여기에서 헤드 요소를 벗겨냅니다).

당연히 이것은 왼쪽 주름에 해당하며 축적 단계가 "함수 적용"인 경우 z = id "더 이상 없을 때 최종 축적 된 값을 반환 x에스":

foldl f a xs =~ foldr (\x r a-> r (f a x)) id xs a

마찬가지로 유한 목록의 경우

foldr f a xs =~ foldl (\r x a-> r (f x a)) id xs a

그리고 결합 기능은 계속 될지 여부를 결정하기 때문에 일찍 멈출 수있는 왼쪽으로 접을 수 있습니다.

foldlWhile t f a xs = foldr cons id xs a
  where 
    cons x r a = if t x then r (f a x) else a

또는 건너 뛰는 왼쪽 주름, foldlWhen t ..., 와 함께

    cons x r a = if t x then r (f a x) else r a

등.

Answer 3

나는 당신과 매우 유사한 방법을 사용하는 방법을 찾았습니다.

myzip = foldr step (const []) :: [a] -> [b] -> [(a,b)]
    where step a f (b:bs) = (a,b):(f bs)
          step a f [] = []

Answer 4

여기에 비 원어민 해원자의 경우,이 알고리즘의 체계 버전을 작성하여 실제로 무슨 일이 일어나고 있는지 더 명확하게 만들었습니다.

> (define (zip lista listb)
    ((foldr (lambda (el func)
           (lambda (a)
             (if (empty? a)
                 empty
                 (cons (cons el (first a)) (func (rest a))))))
         (lambda (a) empty)
         lista) listb))
> (zip '(1 2 3 4) '(5 6 7 8))
(list (cons 1 5) (cons 2 6) (cons 3 7) (cons 4 8))

그만큼 foldr 결과는 목록에 적용될 때 함수에 주어진 목록과 함께 접힌 목록의 zip을 반환하는 함수가 있습니다. Haskell은 내부를 숨 깁니다 lambda 게으른 평가 때문에.

---

더 나누기 위해 :

입력을 ZIP 가져옵니다. '(1 2 3) Foldr func가 호출됩니다.

el->3, func->(lambda (a) empty)

이것은 다음으로 확장됩니다.

(lambda (a) (cons (cons el (first a)) (func (rest a))))
(lambda (a) (cons (cons 3 (first a)) ((lambda (a) empty) (rest a))))

우리가 지금 이것을 반환한다면, 우리는 하나의 요소 목록을 가져 와서 쌍 (3 요소)을 반환하는 함수가 있습니다.

> (define f (lambda (a) (cons (cons 3 (first a)) ((lambda (a) empty) (rest a)))))
> (f (list 9))
(list (cons 3 9))

계속해서 Foldr는 이제 func를 호출합니다

el->3, func->f ;using f for shorthand
(lambda (a) (cons (cons el (first a)) (func (rest a))))
(lambda (a) (cons (cons 2 (first a)) (f (rest a))))

이것은 이제 두 개의 요소가있는 목록을 가져 와서 (list 2 3):

> (define g (lambda (a) (cons (cons 2 (first a)) (f (rest a)))))
> (g (list 9 1))
(list (cons 2 9) (cons 3 1))

무슨 일이야?

(lambda (a) (cons (cons 2 (first a)) (f (rest a))))

a, 이 경우 IS (list 9 1)

(cons (cons 2 (first (list 9 1))) (f (rest (list 9 1))))
(cons (cons 2 9) (f (list 1)))

그리고 당신이 기억 하듯이, f 논쟁을 ZIPS 3.

그리고 이것은 계속됩니다 ...

Answer 5

이 모든 솔루션의 문제 zip 그들은 한 목록이나 다른 목록 위에 접힌 것입니다.이 목록은 목록 융합의 말에서 두 가지가 "좋은 생산자"라면 문제가 될 수 있습니다. 실제로 필요한 것은 두 목록을 모두 접는 솔루션입니다. 다행히도 정확히 그에 대한 논문이 있습니다. "과도한 접촉으로 접힌 주름".

보조 유형, 초 기능 장애가 필요합니다.이 기능은 기본적으로 다른 과도 장애를 인수로 취하는 함수입니다.

newtype H a b = H { invoke :: H b a -> b }

여기에 사용 된 과음은 기본적으로 일반 기능의 "스택"처럼 작용합니다.

push :: (a -> b) -> H a b -> H a b
push f q = H $ \k -> f $ invoke k q

또한 두 가지 하이퍼 팅을 하나로 묶는 방법이 필요합니다.

(.#.) :: H b c -> H a b -> H a c
f .#. g = H $ \k -> invoke f $ g .#. k

이것은 관련이 있습니다 push 법으로 :

(push f x) .#. (push g y) = push (f . g) (x .#. y)

이것은 연관 연산자로 판명되었으며 이것은 정체성입니다.

self :: H a a
self = H $ \k -> invoke k self

또한 "스택"의 다른 모든 것을 무시하고 특정 값을 반환하는 것이 필요합니다.

base :: b -> H a b
base b = H $ const b

마지막으로, 당신은 과도 장애에서 가치를 얻는 방법이 필요합니다.

run :: H a a -> a
run q = invoke q self

run 모든 문자열 pushED 기능이 함께 기능하고 끝까지, base 또는 무한히 고리.

이제 정보를 전달하는 함수를 사용하여 두 목록을 하이퍼 팅으로 접을 수 있으며 최종 값을 조립할 수 있습니다.

zip xs ys = run $ foldr (\x h -> push (first x) h) (base []) xs .#. foldr (\y h -> push (second y) h) (base Nothing) ys where
  first _ Nothing = []
  first x (Just (y, xys)) = (x, y):xys

  second y xys = Just (y, xys)

두 목록을 두 목록에 접는 이유는 GHC가 전화 한 것이 때문입니다. 퓨전을 나열하십시오, 그것은 IN에 대해 이야기합니다 GHC.베이스 모듈, 그러나 아마도 훨씬 더 잘 알려져있을 것입니다. 좋은 목록 제작자가되고 사용합니다 build ~와 함께 foldr 많은 쓸모없는 생산과 목록 요소의 즉각적인 소비를 방지 할 수 있으며 추가 최적화를 노출시킬 수 있습니다.

Answer 6

이 우아한 솔루션을 직접 이해하려고 노력했기 때문에 유형과 평가를 직접 도출해 보았습니다.따라서 우리는 함수를 작성해야 합니다:

zip xs ys = foldr step done xs ys

여기서 우리는 파생해야합니다 step 그리고 done, 그것이 무엇이든.상기하다 foldr의 유형, 목록으로 인스턴스화됨:

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

그러나 우리의 foldr 호출은 하나가 아닌 두 개의 목록 인수를 허용해야 하기 때문에 아래와 같이 인스턴스화되어야 합니다.

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

왜냐하면 -> ~이다 오른쪽 결합, 이는 다음과 같습니다.

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

우리의 ([b] -> [(a,b)]) 에 해당 state 원본의 유형 변수 foldr 유형 서명이므로 모든 항목을 바꿔야 합니다. state 그것으로:

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

이는 우리가 전달하는 인수를 의미합니다. foldr 다음 유형이 있어야 합니다.

step :: a -> ([b] -> [(a,b)]) -> [b] -> [(a,b)]
done :: [b] -> [(a,b)]
xs :: [a]
ys :: [b]

그것을 기억해 foldr (+) 0 [1,2,3] 다음으로 확장됩니다.

1 + (2 + (3 + 0))

그러므로 만일 xs = [1,2,3] 그리고 ys = [4,5,6,7], 우리의 foldr 호출은 다음으로 확장됩니다.

1 `step` (2 `step` (3 `step` done)) $ [4,5,6,7]

이는 우리의 1 `step` (2 `step` (3 `step` done)) 구문은 다음을 통과하는 재귀 함수를 생성해야 합니다. [4,5,6,7] 요소를 압축합니다.(원래 목록 중 하나가 더 길면 초과된 값은 버려집니다.)IOW, 우리의 구성에는 다음 유형이 있어야 합니다. [b] -> [(a,b)].

3 `step` done 우리의 기본 사례는 다음과 같습니다. done 다음과 같은 초기값입니다. 0 ~에 foldr (+) 0 [1..3].3이 최종 값이기 때문에 3 이후에는 아무것도 압축하고 싶지 않습니다. xs, 이므로 재귀를 종료해야 합니다.기본 사례에서 목록에 대한 재귀를 어떻게 종료합니까?빈 목록을 반환합니다. [].하지만 기억해 done 유형 서명:

done :: [b] -> [(a,b)]

그러므로 우리는 그냥 돌아갈 수 없습니다 [], 우리는 수신하는 모든 것을 무시하는 함수를 반환해야 합니다.그러므로 사용 const:

done = const [] -- this is equivalent to done = \_ -> []

이제 무엇인지 알아보기 시작하겠습니다. step 해야한다.유형의 값을 결합합니다. a 유형의 기능으로 [b] -> [(a,b)] 유형의 함수를 반환합니다. [b] -> [(a,b)].

~ 안에 3 `step` done, 나중에 압축 목록으로 이동하게 될 결과 값은 다음과 같아야 한다는 것을 알고 있습니다. (3,6) (원본으로 알고 있음 xs 그리고 ys).그러므로 3 `step` done 다음을 평가해야 합니다.

\(y:ys) -> (3,y) : done ys

기억하세요, 우리는 함수를 반환해야 하며 그 안에 요소를 어떻게든 압축해야 합니다. 위의 코드는 의미가 있고 유형 검사입니다.

이제 우리는 정확히 얼마나 step 평가해야 하므로 평가를 계속합시다.우리의 모든 감소 단계는 다음과 같습니다. foldr 평가는 다음과 같습니다:

3 `step` done -- becomes
(\(y:ys) -> (3,y) : done ys)
2 `step` (\(y:ys) -> (3,y) : done ys) -- becomes
(\(y:ys) -> (2,y) : (\(y:ys) -> (3,y) : done ys) ys)
1 `step` (\(y:ys) -> (2,y) : (\(y:ys) -> (3,y) : done ys) ys) -- becomes
(\(y:ys) -> (1,y) : (\(y:ys) -> (2,y) : (\(y:ys) -> (3,y) : done ys) ys) ys)

평가를 통해 이러한 단계 구현이 발생합니다(우리는 다음을 설명합니다). ys 빈 목록을 반환하여 조기에 요소가 부족함):

step x f = \[] -> []
step x f = \(y:ys) -> (x,y) : f ys

따라서 전체 기능은 zip 다음과 같이 구현됩니다:

zip :: [a] -> [b] -> [(a,b)]
zip xs ys = foldr step done xs ys
  where done = const []
        step x f [] = []
        step x f (y:ys) = (x,y) : f ys

추신.:접힌 부분의 우아함에 영감을 받았다면 다음을 읽어보세요. Foldr을 사용하여 Foldl 작성 그리고 그레이엄 허튼의 접기의 보편성과 표현성에 관한 튜토리얼.

Answer 7

간단한 접근 :

lZip, rZip :: Foldable t => [b] -> t a -> [(a, b)]

-- implement zip using fold?
lZip xs ys = reverse.fst $ foldl f ([],xs) ys
     where f  (zs, (y:ys)) x = ((x,y):zs, ys)

-- Or;
rZip xs ys = fst $ foldr f ([],reverse xs) ys
     where f x (zs, (y:ys))  = ((x,y):zs, ys)