如何在Haskell中组合函数和monad动作

Question

我刚开始学习Haskell.

我正在创建一个查找重复文件的程序.我创建了以下功能:

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

我想在一个返回的函数中组合它们

Map.Map (Digest MD5) [FilePath]

我的问题是:

我无法找到一种方法来处理IO monad以获得我想要的东西.所以我的问题是:

1. 我正在尝试做的是正确的,还是应该返回类型Map.Map (IO (Digest MD5)) [FilePath].

2. 如何将这些函数组合在一起以获取按哈希分组的文件列表？

Answer 1

让我们仔细比较类型hashFile和类型categorize,记住我们想要hashFile作为参数传递categorize

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

categorize hashFile将不类型检查,因为GHC将尝试匹配k用IO (Digest MD5),但IO没有Ord实例.换句话说,IO (Digest MD5)作为一个关键是无用的Map:你需要的是Digest MD5s,而不是Digest MD5在你执行它们时最终产生s的计算.

你真正想做的是运行所有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]*(née mapM)接受一个Applicative函数,将其映射到列表中,并将结果一起粉碎成一个列表.我们用它来将每个项目变成一个(result, item)元组.这将产生一个f [(k, a)]价值.然后我fmap M.fromList结果产生了f (M.Map k a).

_{*从技术上讲,traverse有更普遍的类型(Applicative f, Traversable t) => (a -> f b) -> t a -> f (t b).我拿到了这个版本t ~ [].}

由于此实现使用M.fromList,将丢弃重复的项目.实际上,如果您不希望任何文件具有相同的内容,则MD5哈希值将不同,因此这不会成为问题.练习:如果我们想保留重复项,这会如何改变？