ハスケルで関数とモナドの動作を構成する方法

Question

私はちょうどハスケルを学び始めました。

私は重複ファイルを見つけるプログラムを作成しています。私が対処する方法を見つけることができません

：私は、以下の機能作成しました：

hashFile :: (MonadIO m) => FilePath -> m (Digest MD5) 
categorize :: Ord k => (a -> k) -> [a] -> Map.Map k [a] 

をそして私は

Map.Map (Digest MD5) [FilePath]

私の質問がある返す機能でそれらを構成したいです私が望むものを得るためのIOモナド。だから、私の質問は以下のとおりです。

1. は、私が正しいをやろうとしている、または戻り値の型は 本当にMap.Map (IO (Digest MD5)) [FilePath]になりべきものです。

2. ハッシュでグループ化されたファイルのリストを取得するには、これらの関数を一緒に作成するにはどうすればよいですか？

Answer 1

てみましょう慎重ので、チェックを入力しないであろうcategorize

hashFile ::    FilePath -> IO (Digest MD5) -- I simplified the MonadIO constraint 
categorize :: Ord k => ( a ->  k  ) -> [a] -> M.Map k [a] 

categorize hashFileに引数としてhashFileを渡すために私たちが望むことを念頭に、categorizeの種類とhashFileのタイプを比較しGHC kをIO (Digest MD5)に一致させようとしますが、IOにはOrdインスタンスがありません。言い換えれば、IO (Digest MD5)はMapの鍵として役に立たない：あなたが必要とするのはDigest MD5であり、実行すると最終的にはDigest MD5を生成する計算ではない。

IOの計算をすべて実行し、その結果（タイプDigest MD5）をMapに入力してください。結果の関数はIO (Map (Digest MD5) FilePath) - IOの計算を返し、実行するとMap (Digest MD5) FilePathを返します。

---

これを行う最も簡単な方法は、必要なタイプに合わせてcategorizeを調整することです。

categorize :: (Applicative f, Ord k) => (a -> f k) -> [a] -> f (M.Map k a) 
categorize f = fmap M.fromList . traverse (\x -> fmap (, x) (f x)) 

（私はTupleSectionsを使用しています）まずタイプを見てみましょう。 IOがApplicativeのインスタンスであるので、(a -> f k)は、以下の制約の下でFilePath -> IO (Digest MD5)で統一：私たちが望むタイプです

a ~ FilePath 
f ~ IO 
k ~ Digest MD5 

のでcategorize hashFile :: [FilePath] -> IO (M.Map (Digest MD5) FilePath)、。

ここで実装を見てみましょう。 traverse :: Applicative f => (a -> f b) -> [a] -> f [b] *（nee mapM）はApplicative関数を受け取り、それをリストにマップし、結果をまとめてリストにします。各アイテムを(result, item)タプルに変換するために使用しています。これによりf [(k, a)]値が生成されます。そして、 M.fromListの結果がf (M.Map k a)になります。

_{*技術的には、traverseは、より一般的なタイプの(Applicative f, Traversable t) => (a -> f b) -> t a -> f (t b)です。私はt ~ []を取ってこのバージョンに着いた。}

この実装ではM.fromListが使用されるため、重複した項目が破棄されます。実際には、ファイルの内容が同じであることを期待していない場合は、MD5のハッシュが異なるため問題ありません。練習問題：重複を維持したい場合、これはどのように変化しますか？