foldrを使用してzipを実装する

https://stackoverflow.com/questions/235148

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 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)



	
		
			ライセンス： CC-BY-SA と 帰属
			所属していません StackOverflow