list - Haskellのリストの再帰

Question

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

Answer 1

まず、あなたが持っているその機能fを考えてみましょう。ある種の累積された値、プレーンな値を取り、それらを結果に結合します。したがって、型シグネチャではa、累積された値vの型、値の型、およびr結果の型について言います。

f :: a -> v -> r

f次に、値のリストを使用する折りたたみ関数を作成します。

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

何を返す必要がありますか？結果の型の何かが得られるはずrですよね？and の結果を最初の引数に再度入力し続けるため、 aandrは実際には同じ型である必要があることに注意してください。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'

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

Answer 2

宿題のようですね。折り目を見てください。