foldr을 사용하여 zip 구현
-
04-07-2019 - |
문제
저는 현재 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
같은 기술을 사용하고 있지만 아무런 진전이 없는 것 같습니다.심지어 가능합니까?
해결책
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가 보여준 것처럼.
다른 팁
답은 이미 여기에 주어졌지만 (예시적인) 파생물은 아닙니다. 그래서이 세월이 지난 후에도 추가 할 가치가있을 것입니다.
실제로 아주 간단합니다. 첫 번째,
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 x1
r1
ys
어디 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 x2
r2
ys1
, 다음 단계로. 그리고 그게 그게 다.
언제 ys
보다 짧습니다 xs
(또는 같은 길이), []
사례 f
화재와 처리 중단. 그러나 만약 ys
보다 길다 xs
그 다음에 f
'에스 []
사례는 발사되지 않고 결승에 진출 할 것입니다 f xn
z
(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
등.
나는 당신과 매우 유사한 방법을 사용하는 방법을 찾았습니다.
myzip = foldr step (const []) :: [a] -> [b] -> [(a,b)]
where step a f (b:bs) = (a,b):(f bs)
step a f [] = []
여기에 비 원어민 해원자의 경우,이 알고리즘의 체계 버전을 작성하여 실제로 무슨 일이 일어나고 있는지 더 명확하게 만들었습니다.
> (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
.
그리고 이것은 계속됩니다 ...
이 모든 솔루션의 문제 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
모든 문자열 push
ED 기능이 함께 기능하고 끝까지, 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
많은 쓸모없는 생산과 목록 요소의 즉각적인 소비를 방지 할 수 있으며 추가 최적화를 노출시킬 수 있습니다.
이 우아한 솔루션을 직접 이해하려고 노력했기 때문에 유형과 평가를 직접 도출해 보았습니다.따라서 우리는 함수를 작성해야 합니다:
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 작성 그리고 그레이엄 허튼의 접기의 보편성과 표현성에 관한 튜토리얼.
간단한 접근 :
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)