ハスケルの再帰的リスト機能

Question

私は現在、ウェブサイトを分析し、このウェブサイトに属するすべてのリンク（href）を見つけようとしているハスケルのこのプログラムに取り組んでいます。私は既にメインサイトのすべてのリンクを抽出することができましたが、私はすでに見つかったリンクをたどり、同じプロセスをやり直したいので、私は再帰に苦労しています。

これは私がすでに持っているものです。

parseHtml = fmap LB.unpack . simpleHttp 
filterFunc x y = -- damn long line with a lot of filters 

main :: IO() 
main = do 
    let site = "https://stackoverflow.com/" 
    url <- parseHtml site 
    let links = filterFunc site url 
    mapM_ print $ take 5 $ links 

そして、これはこれまでのところ、私の出力です：

"https://stackoverflow.com/company/about" 
"https://stackoverflow.com/company/work-here" 
"https://stackoverflow.com/help" 
"https://stackoverflow.com/jobs/directory/developer-jobs" 
"https://stackoverflow.com/questions/44691577/stream-versus-iterators-in-set" 

私はちょうどさらに進行すると、すでに見つかっを訪問する方法をどのようにヒントを必要とします再度リンクします。私は折りたたんで作業する必要がありますか？

Answer 1

リンク探索は本質的にグラフのトラバーサル問題です。機能的な純度のためにHaskellでは扱いにくいことがあります。外部履歴テーブルを使用して訪問したかどうかを明示的にマークするのは難しいです。

あなたの典型的なトラバースアルゴリズムは次のようになります。

function traverse(current_node) { 
    if (current_node.is_visited) { 
     return some_data; 
    } else { 
     current_node.is_visisted = true;   // Hard in Haskell! 
     accumulated_data = ...; 
     for (child in current_node.children()) { 
      accumulated_data += traverse(child); // Recursion happens here. 
     } 
     return accumulated_data; 
    } 
} 

を訪問したかどうか、我々は他のソリューションを試すことができますとしてノードをマークする簡単な、直接的な方法はありませんので。例えば、我々は、並べ替えの何かを検討するかもしれない：

traverse :: ([URL], Data) -> URL -> ([URL], Data) 
traverse (history, datum) current = let ... in ([new_history], accumulated_data) 

ここでの考え方は以下の通りである。我々は、我々が訪問したURL秒の明示的なリストを維持します。これにより、現在のノード（URL）がヒストリリスト（おそらく最適化の場合はSet）に表示されている場合は、すぐにそれを返すことができます。この場合、traverseを使用して子ノードに呼び出すたびに、new_historyのリストが得られ、訪問済みおよび非表示のリストを実質的に追跡します。URL

など foldlとしてこれを実装するための1つの可能な方法の折り畳み機能を使用している

：タイプt aは[URL]である場合があります。ここ

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

は、現在のリンクの子供であり、私たちのtraverse機能が便利なタイプを持っています署名(b -> a -> b)（type b = ([URL], Data)とtype a = URL）。

traverseとfoldlを組み合わせる方法をここから確認できますか？

Answer 2

あなたのリンクを訪問するロジックを別の機能で移動するだけで、リンクをパラメータとして受け取り、直感的にリンク上で再帰します。

最終的にリンクで何をしたいかによって、リンクを関数で単純に折り畳むことができます。場合あなたが行くようにするのではなく、たとえば、それらを返すインスタンスString -> IO [String]ためvisitLink関数の戻り値の型を（微調整、リンクを印刷するのではなく、

parseHtml = fmap LB.unpack . simpleHttp 
filterFunc x y = -- damn long line with a lot of filters 

visitLink :: String -> IO() 
visitLink site = do 
    url <- parseHtml site 
    let links = filterFunc site url 
    mapM_ print $ take 5 $ links -- or whatever you want to do on your links 
    mapM_ visitLink links -- the recursive call 


main :: IO() 
main = visitLinks "https://stackoverflow.com/" 

ます：

たとえば、少しあなたのコードを修正します最後の行はvisitLink（たとえばfmap join $ mapM visitLinks links）に変更してください。

別の答えで言及しているように、このような単純なコードでは、無限に同じリンクを頻繁に訪れることができます。訪れたリンクをvisitLinkに渡す適切なデータ構造（セットなど）に格納することを検討してください。