优化Haskell组合中的重复函数调用

Question

在编写一个探索生日悖论的程序时，我有以下工作的Haskell代码

sort :: Ord a => [a] -> [a]
-- body
hasDuplicates :: Eq a => [a] -> Bool
-- body
boolToInt :: Bool -> Int
-- body
main = do
-- stuff
repeats <- liftM sum . replicateM numTrials . liftM boolToInt .
liftM hasDuplicates . liftM sort . replicateM checkNum $
randomRIO (1::Int, 365)
-- stuff

在最后一行中，有许多liftM一个接一个地组成。这种成分可以优化吗？

我想到了mappingliftM到[boolToInt, hasDuplicates, sort]，然后composeing，但该列表是异构的，因此无效。CCD_ 6由于类似的原因将不起作用。

Answer 1

是的，您可以编写其中一些。最简单的方法是认识到liftM实际上只是Monad实例的fmap的实现。(1) 因此，通常的函子定律适用：

fmap id = id
fmap f . fmap g = fmap (f . g)

因此

liftM boolToInt .
liftM hasDuplicates .
liftM sort

可以写

fmap (boolToInt . hasDuplicates . sort)

我们怎样才能做得更好？让我们结合上下文来看待这个问题。

liftM sum . replicateM numTrials .
fmap (boolToInt . hasDuplicates . sort) .
replicateM checkNum

这里似乎没有太多重复，但如果每个试验或检查中都有很多试验或检查，那么效率可能会非常低，因为在对这些列表进行汇总之前，你要在内存中建立这些列表。你可以用手把它修一下，但不会很愉快。修复它的好方法是使用流媒体包。另一件需要考虑的事情是，由于我们正在处理的唯一影响是随机性，如果出现重复，我们可以立即停止试验。我稍后会做示范。

---

1. liftM的全部目的是能够为类型m写入Monad实例，然后写入instance Functor m where fmap = liftM。一般情况下，您不应该将liftM用于任何其他用途。

2. 例如，

   fmap sum . replicateM n
   

   可以写

   sumReplications = go 0 where
   go !acc 0 _ = pure acc
   go acc n m = m >>= res -> go (acc + res) (n - 1) m
   

Answer 2

您可以liftM整个组成，而不是liftM单独处理每个函数。

liftM (sum . replicate numTrials . boolToInt . hasDuplicates . sort)