私は現在、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 を消費する関数を返します。そのため、ys の対応する部分にそれぞれ適用される関数のネストされた構成を構築する xs リストを下に移動します。
それを思いつく方法: 私は一般的なアイデアから始めました (以前に見た同様の例から), 書いた
zip2 xs ys = foldr step done xs ys
次に、次の各行に、型と値を正しく表示するために必要なものを順番に入力します。難しいケースの前に、最も単純なケースを最初に検討するのが最も簡単でした。
最初の行は、次のように簡単に記述できます。
zip2 = foldr step done
マティアストが示したように。
答えはすでにここで与えられていましたが、(例示的な) 派生ではありません。したがって、これらすべての年月が経過した後でも、おそらく追加する価値があります。
それは実際には非常に簡単です。初め、
フォルダ fz xs = foldr fz [x1,x2,x3,...,xn] = f x1 (foldr fz [x2,x3,...,xn]) = ... = f x1 (f x2 (f x3 (.. . (f xn z) ...)))
したがって、イータ展開によって、
フォルダ fz xs ys = foldr fz [x1,x2,x3,...,xn] ys = f x1 (foldr fz [x2,x3,...,xn]) ys = ... = f x1 (f x2 (f x3 (... (f xn z) ...))) ys
ここで明らかなように、 が 2 番目の引数で非強制的である場合、f最初にx1およびysで機能します。ここで.f x1r1ysr1 =(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
次のステップとして、残りの入力リスト,を呼び出して、リストに沿って左から右に情報を渡すようにします。そして、それはそれです。 r1ys1foldr f z [x2,x3,...,xn]ys1 = f x2r2ys1
ysより短いxs（または同じ長さ）[]場合、火災の場合fは処理が停止します。しかし、 ifysがxsthenfの[]ケースは起動せず、最終的なアプリケーションに到達します。f xnz(yn:ysn)
f xn z (yn:ysn) = (xn,yn) : z ysn
の終わりに達したためxs、zip処理を停止する必要があります。
z _ = []
これは、次の定義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の役割を果たします。f(x,y)
同様に、「より多くの s が存在する場合に、より多くの処理が行われる」と、の-caseはr、「それ以上の sが存在しない場合に行われる処理」です。または、自然に停止し、使い果たされたら戻ることができます。ysxz = const []nilfoldrysxf[]ys
ysが一種の累積値としてどのように使用されているかに注意してください。この値は listxsに沿って左から右へ、ある呼び出しからf次の呼び出しまで渡されます (「蓄積」ステップは、ここでは、そこから head 要素を取り除くことです)。
当然、これは左折に対応し、累積ステップは「関数を適用する」ことであり、 「 sz = 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 [] = []
ここにいる非ネイティブのHaskellersのために、実際に何が起こっているのかを明確にするために、このアルゴリズムのSchemeバージョンを作成しました。
> (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）foldrfuncはで呼び出されます
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))))
ここでこれを返すとすると、1つの要素のリストを取得し、ペア（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))))
これは、2つの要素を含むリストを取得し、それらを(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、この場合、(list 9 1)
(cons (cons 2 (first (list 9 1))) (f (rest (list 9 1))))
(cons (cons 2 9) (f (list 1)))
そして、あなたが思い出すように、fその引数を3。
そしてこれは続くなど...