Haskellのリスト上の再帰

Question

たとえば、['a'、 'b'、 'c'、 'd'、 'e']などのリストがあります。
このようなことをしたい：
最初に最初の2つの要素、f 'a' 'b'で何かをします
次に、リストのfの返品値と次の要素で同じことを行います。 f resultof（result 'c'） 'd'など。
どうすればこのようなことができますか？

Answer 1

まず、その機能を考えてみましょう f あなたが持っていること。何らかの蓄積された価値と平易な値が必要であり、それらを結果に結合します。したがって、タイプの署名で、私たちは言います a 蓄積された値のタイプについては、 v 値のタイプ、および r 結果のタイプ。

f :: a -> v -> r

今、私たちは使用する折り畳み関数を作成したいと思います f および値のリスト。

someFold :: (a -> v -> r) -> [v] -> ?

何を返すべきですか？結果のタイプの何かを生成するはずです r, 、 右？今それに注意してください a と r 私たちはの結果に餌を与え続けているので、実際に同じタイプでなければなりません f それは再び最初の議論です。

someFold :: (a -> v -> a) -> [v] -> a

今、1つのことが欠けています。どうやって最初に手に入れますか a？それを見るには2つの方法があります。最初の値を選択するだけです。その場合 a と同じタイプです v, 、または基本値を指定するので、 a 実際には異なる可能性があります v. 。それはもっと興味深いので、後者と一緒に行きましょう。また、このリストで左に移動することにしましょう。 （それはあなたが必要とするものですよね？）

someFold :: (a -> v -> a) -> a -> [v] -> a

それで...どのようにそれを実装しますか？再帰的になるので、基本的なケースから始めましょう。

someFold f acc [] = acc

リストの終わりに達したら、十分に蓄積しましたよね？それは簡単でした。では、再帰的なケースはどうですか？あなたが言ったことから、各ステップで適用する必要があります f 最初の引数としての「これまでの蓄積された価値」、および2番目の「リストの最初の値」に。 f acc x. 。次に、折り畳み続けます それ 私たちの新しい「蓄積された」価値として。

someFold f acc (x:xs) = someFold f (f acc x) xs

簡単ですよね？しかし...私たちがあなたが言ったようにやりたいと思ったら、リストの最初の2つの値を取得して関数を開始した場合はどうなりますか？また簡単です。最初の要素を取り、元の「ベース」アキュムレータと呼んでください！

someFold1 :: (v -> v -> v) -> [v] -> v
someFold1 f (x:xs) = someFold f x xs

それ以来に注意してください a と同じタイプです v この特別なケースでは、関数 someFold1 非常に面白いタイプの署名があります。この説明を理解した場合は、おめでとうございます。実装したばかりです foldl と foldl1.

Prelude> foldl1 min "abcde" -- "abcde" is sugar for ['a','b','c','d','e']
'a'

実際のコードでは、実際に使用する必要があります foldl' と友達。

Answer 2

宿題のように聞こえます。折り目を見てください。

Answer 3

この場合、折り畳みの問題は、通常、一度に要素を処理することです。手動で折りたたむようにすることができます。

あなたはあなたの機能を持っていると仮定します f, 、それは一度に2つの要素を取得し、 アキュムレータ （最後の反復の結果）FED。次に、あなたは次のようになります：

fold2 :: (a -> a -> b -> b) -> [a] -> b -> b
fold2 f accum (x:y:zs) = fold2 f (f x y) zs
fold2 _ accum []       = accum
fold2 _ _     _        = error "odd number of elements"

これを理解してみてください。 fold2 リストの上位2つの要素を剃り、それを供給します f. 。結果は、再帰呼び出しに新しいアキュムレータとして渡されます。これは、リストが空になるまで行われます。