foldrを使用したHaskell foldlの実装

Question

foldrを使用してfoldl関数の実装を理解するのに困っています。私はこの質問（Writing foldl using foldr）を読んでいると私はまだ私は、次の例では理解していないいくつかのものを持っている：

fun :: [Int] -> [Int] 
fun l = foldr g (const []) l 1 
    where g x f lst = if gcd x lst == 1 then x : f x else f lst 

関数は、パラメータとしてリストをとり、gcd(l[i], l[i + 1] = 1別のリストを返します。

私の質問は以下のとおりです。
x、fとlst
2.何const[]で、なぜ私はid機能を使用することはできませんです 1.？

Answer 1

foldrの型シグネチャは、これは、その3つの引数に適用され、あなたのfoldrが引数として1をとる関数を返さなければならないことを意味し、この

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b 

です。

ですから、これはあなたのg機能を意味し、この

foldr :: (Int -> (Int -> [Int]) -> (Int -> [Int])) 
     -> (Int -> [Int]) 
     -> [Int] 
     -> (Int -> [Int]) 

にごfoldrを特化することができますが、次のタイプに

g :: Int -> (Int -> [Int]) -> Int -> [Int] 

を持っている必要がありますので、あなたのパラメータは、タイプ

x :: Int 
f :: Int -> [Int] 
lst :: Int 

を持っており、 foldr第2号目tはIntの代わりにInt -> [Int]を必要とするため、値[]を渡すことはできません。

は幸いconstは、その引数を無視して、ちょうど常にfが実際にアキュムレータのいくつかの種類であるあなたのケースでは定数式

const [] :: a -> [b] 

を返す関数を返します。しかし、いくつかの値の値のリスト、ここで連鎖関数です。最後にこのファンクションチェーンに1を渡すことで、それが評価され、返す実際のリストをfunに作成しています。

Answer 2

foldrは、自転車のような奇妙なツールの1つです。一度使用すると使いやすいものですが、最初から学ぶのは難しいです。数年の経験を経て、私はfoldrで解決できる問題を見つけ、すぐに正しく解決することができました。しかし、私が十分にやったこと説明する詳細！

実際には、私は通常、曖昧に連続通しの言語でfoldrと考えています。 foldrだけ三つの引数に適用される「シンプル」の場合を無視すると、foldrの適用は、次のようになります。

foldr go finish xs acc1 acc2 ... where 
    finish acc1 acc2 ... = ? 
    go x cont acc1 acc2 ... = ? 

acc1など、アキュムレータは、「左から右へ」渡されます。結果は、概念的には、「右から左に」渡された単一の値から成ります。

finishは、アキュムレータの最終値を取得し、結果の種類を生成します。あなたがあなたの折り目を生成したいだけで何把握たら

foldr go finish [] acc1 acc2 ... 
= 
finish acc1 acc2 ... 

だから、finishを書くことが、かなりの機械であるため、これは通常の書き込みするための最も簡単な部分です。

goは、単一のコンテナ要素、「継続」、およびアキュムレータを取得します。それらのアキュムレータが結果を得るために継続に「転送」し、その結果を使用して独自のものを構築する場合は、変更された値を渡します。

foldlは、新しいアキュムレータ引数を使用してコンテナの残りの部分を折りたたんで結果を返すため、特に単純なケースです。私はもう少し実例を見るのが少し面白いと思います。ここでは数値のコンテナを取り、実行中の合計と実行中の製品を表すペアのリストを生成します。

sumsProducts :: (Num n, Foldable f) => f n -> [(n, n)] 
sumsProducts xs = foldr go finish xs 0 1 
    where 
    finish total prod = [(total, prod)] 
    go x cont total prod = 
     (total, prod) : cont (x + total) (x * prod)