优化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一个接一个地组成.这个组合可以优化吗？

我想到了map平liftM到[boolToInt, hasDuplicates, sort],然后compose荷兰国际集团,但该名单是异类所以无效.iterate由于类似的原因不会起作用.

Answer 1

是的,你可以组成其中一些.一看就知道最简单的方法是要认识到liftM其实只是一个实现fmap的Monad实例(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

这里似乎没有太多的重复,但是如果每个都有很多试验或许多检查,那么可能会有很大的低效率,因为你在对它们求和之前在内存中建立这些列表.你可以手工解决这个问题,但不会很愉快(2).解决它的好方法是使用流媒体包.另一件需要考虑的事情是,由于我们正在使用的唯一影响是随机性,如果出现重复,我们可以停止试验.我稍后会尝试演示.

1. 在整个目的的liftM是能够写一个Monad实例的类型m,然后写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