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)
仕組み:(folder step done xs)消費する関数を返します ys;そのため、xsリストを下に移動して、 ysの対応する部分にそれぞれ適用される関数。
それを思いつく方法:私は一般的なアイデアから始めました(同様の 前に見た例)、書きました
zip2 xs ys = foldr step done xs ys
次の各行に順番に入力します 型と値が正しく出てくるようにします。一番簡単だった 難しいケースの前にまず最も単純なケースを検討してください。
最初の行は、より簡単に書くことができます
zip2 = foldr step done
マティアストが示したように。
他のヒント
答えはすでにここに与えられていましたが、(例証的な)派生ではありませんでした。したがって、これらすべての年が経過した後でも、追加する価値はあるでしょう。
実際には非常に簡単です。まず、
foldr f z xs = foldr f z [x1,x2,x3,...,xn] = f x1 (foldr f z [x2,x3,...,xn]) = ... = f x1 (f x2 (f x3 (... (f xn z) ...)))
η-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
が2番目の引数で強制されていない場合、 x1で first 動作します
および ys
、 f x1
r1
ys
ここで、 r1 =
(f x2(f x3(...(f xn z)...)))
= foldr fz [x2、 x3、...、xn]
。
したがって、使用
f x1 r1 [] = [] f x1 r1 (y1:ys1) = (x1,y1) : r1 ys1
呼び出し r1
により、リストに沿って左から右への情報の通過を手配します。入力リスト ys1
の rest 、 folder fz [x2、x3、...、xn]
<次のステップとして、code> ys1 = f x2 r2
ys1
。そしてそれはそれです。
ys
が xs
より短い(または同じ長さ)場合、 f
の []
ケース起動し、処理が停止します。ただし、 ys
が xs
より長い場合、 f
の []
ケースは実行されず、最終的な f xn
z
(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
は success continuation の役割を果たし、 f
はペア(x、y)
を発行した後、処理を続行します。
つまり、 r
は&quot; x
s&quot; がさらにある場合に、より多くの ys
で行われることです。 z = const []
、 folder
の nil
-caseは、&quot; what is x
s&quot; がなくなったときに ys
で行います。または、 ys
が使い果たされたときに f
が自動的に停止し、 []
を返します。
f の1回の呼び出しから、リスト
xs
に沿って左から右に渡される ys
が一種の累積値として使用されることに注意してください/ code>を次へ(「蓄積」ステップ、ここでは、そこからヘッド要素を取り除く)。
自然にこれは左折に相当します。ここでは、累積ステップが「関数を適用」しています。 z = id
では、「 x
s&quot;」がなくなったときに最終的な累積値を返します:
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
etc。
あなたと非常によく似た方法を使用する方法を見つけました:
myzip = foldr step (const []) :: [a] -> [b] -> [(a,b)]
where step a f (b:bs) = (a,b):(f bs)
step a f [] = []
ここでの非ネイティブHaskellerについては、実際に何が起こっているかを明確にするために、このアルゴリズムの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))
folder
は関数になり、リストに適用されると、関数に与えられたリストで折り返されたリストの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))))
ここでこれを返す場合、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)
で圧縮するfuncです:
> (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
で引数を圧縮します。
これは続きます...
zip
のこれらすべてのソリューションの問題は、どちらか一方のリストにしか折りたたまれないことです。これは、両方の用語が「良いプロデューサー」である場合に問題になる可能性がありますリスト融合。実際に必要なのは、両方のリストを折り畳むソリューションです。幸いなことに、&quot;折り畳み関数をハイパーファンクションで処理する&quot; と呼ばれる、まさにそれに関する論文があります。 p>
補助型、ハイパー関数が必要です。これは基本的に、別のハイパー関数を引数として取る関数です。
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
また、2つのハイパー関数をエンドツーエンドでまとめる方法も必要です。
(.#.) :: 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
は、 base
に到達するか無限にループするまで、すべての push
された関数をエンドツーエンドで一緒に文字列化します。
これで、一方から他方に情報を渡す関数を使用して、両方のリストをハイパー関数に折りたたみ、最終値を組み立てることができます。
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が list fusion と呼んでいるもののためです。これは GHC.Baseモジュールですが、おそらくもっとよく知られているはずです。優れたリストプロデューサーであり、 folder
で build
を使用すると、リスト要素の無駄な大量生産を防ぎ、さらなる最適化を公開できます。
このエレガントなソリューションを自分で理解しようとしたので、自分で型と評価を導き出そうとしました。それで、関数を書く必要があります:
zip xs ys = foldr step done xs ys
ここでは、 step
と done
を導出する必要があります。 folder
のタイプ、リストにインスタンス化されます:
foldr :: (a -> state -> state) -> state -> [a] -> state
ただし、 folder
呼び出しは、次のようなインスタンス化する必要があります。1つではなく2つのリスト引数を受け入れる必要があるためです。
foldr :: (a -> ? -> ?) -> ? -> [a] -> [b] -> [(a,b)]
-&gt;
は right-associative であるため、これは次と同等です:
foldr :: (a -> ? -> ?) -> ? -> [a] -> ([b] -> [(a,b)])
([b]-&gt; [(a、b)])
は、元の folder
型の state
型変数に対応します署名。したがって、出現するすべての state
を次のように置き換える必要があります。
foldr :: (a -> ([b] -> [(a,b)]) -> ([b] -> [(a,b)]))
-> ([b] -> [(a,b)])
-> [a]
-> ([b] -> [(a,b)])
これは、 folder
に渡す引数が次のタイプでなければならないことを意味します:
step :: a -> ([b] -> [(a,b)]) -> [b] -> [(a,b)]
done :: [b] -> [(a,b)]
xs :: [a]
ys :: [b]
folder(+)0 [1,2,3]
は次のように展開されることを思い出してください:
1 + (2 + (3 + 0))
したがって、 xs = [1,2,3]
および ys = [4,5,6,7]
の場合、 folder
呼び出しは次のように展開されます:
1 `step` (2 `step` (3 `step` done)) $ [4,5,6,7]
これは、 1 `step`(2` step`(3 `step` done))
コンストラクトが [4,5,6 、7]
要素を圧縮します。 (元のリストのいずれかが長い場合、余分な値は破棄されることに注意してください)。 IOW、コンストラクトのタイプは [b]-&gt;でなければなりません。 [(a、b)]
。
3 `step` done
は基本ケースです。 done
は、 foldr(+ )0 [1..3]
。 3は xs
の最終値であるため、3以降は何も圧縮したくないため、再帰を終了する必要があります。基本ケースのリストに対する再帰をどのように終了しますか?空のリスト []
を返します。ただし、 done
型署名を思い出してください:
done :: [b] -> [(a,b)]
したがって、 []
だけを返すことはできないため、受け取ったものをすべて無視する関数を返す必要があります。したがって、 const コード>
:
done = const [] -- this is equivalent to done = \_ -> []
ここで、 step
がどうあるべきかを考え始めましょう。タイプ a
の値とタイプ [b]-&gt;の関数を組み合わせます。 [(a、b)]
およびタイプ [b]-&gt;の関数を返します。 [(a、b)]
。
3 `step` done
では、後で圧縮リストに移動する結果の値は(3,6)
(元の< code> xs および ys
)。したがって、 3 `step` done
は以下に評価される必要があります:
\(y:ys) -> (3,y) : done ys
関数を返す必要があることを忘れないでください。その中に何らかの方法で要素を圧縮します。上記のコードが意味を持ち、型チェックを行います。
step
がどの程度正確に評価されるべきかを想定したので、評価を続けましょう。 folder
評価のすべての削減手順は次のようになります。
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
PS:折り畳みの優雅さに触発されている場合は、 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)