避免在Haskell中显式递归

Question

下面的简单函数迭代地应用给定的monadic函数,直到它命中Nothing,此时它返回最后一个非Nothing值.它做我需要的,我理解它是如何工作的.

lastJustM :: (Monad m) => (a -> m (Maybe a)) -> a -> m a
lastJustM g x = g x >>= maybe (return x) (lastJustM g)

作为我在Haskell的自我教育的一部分,我试图尽可能避免明确的递归(或至少理解如何).在这种情况下,似乎应该有一个简单的非显式递归解决方案,但我无法搞清楚.

我不希望像一个一元版本的takeWhile,因为它可以收集所有没有预值昂贵,反正我不关心他们.

我检查了Hoogle的签名,没有任何显示.这个m (Maybe a)位让我觉得monad变换器在这里可能很有用,但我真的不具备我需要提出细节的直觉(还).

这可能要么是令人尴尬地容易做到这一点,要么令人尴尬地容易理解为什么不能或不应该这样做,但这不是我第一次将自我尴尬作为一种教学策略.

更新:我当然可以提供谓词而不是使用Maybe:类似(a -> Bool) -> (a -> m a) -> a(返回谓词为真的最后一个值)也可以正常工作.我感兴趣的是使用标准组合器编写没有显式递归的任一版本的方法.

---

背景:这是一个简化的上下文工作示例:假设我们对单位广场中的随机游走感兴趣,但我们只关心退出点.我们有以下步骤功能:

randomStep :: (Floating a, Ord a, Random a) =>
              a -> (a, a) -> State StdGen (Maybe (a, a))
randomStep s (x, y) = do
  (a, gen') <- randomR (0, 2 * pi) <$> get
  put gen'
  let (x', y') = (x + s * cos a, y + s * sin a)
  if x' < 0 || x' > 1 || y' < 0 || y' > 1
    then return Nothing
    else return $ Just (x', y')

类似的东西evalState (lastJustM (randomStep 0.01) (0.5, 0.5)) <$> newStdGen会给我们一个新的数据点.

Answer 1

避免显式递归的很多内容是组成内置的递归组合器,它通常用于非常通用的未提升值.做同样的事情在一个函子,单子,或其他类型解禁有时使用工作基本一样吊装作业fmap,<*>,>>=,等等.在某些情况下,预先解除版本已经存在,如mapM,zipWithM等.其他时候,takeWhile提升并非易事,也没有提供内置版本.

你的功能确实具有应该成为标准组合器的升级版本的特性.首先,让我们去掉monad来重建你隐含提升的函数:

lastJust :: (a -> Maybe a) -> a -> a

这里的"最后"这个词给了我们一个提示; 非显式递归通常使用临时列表作为控制结构.所以你想要的是last应用于迭代函数生成的列表,直到获得Nothing.通过类型的略微概括,我们找到了生成器:

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

所以我们有这样的事情:

dup x = (x, x)
lastJust f x = last $ unfoldr (fmap dup . f) x

不幸的是,在这一点上我们有点卡住了,因为(据我所知)没有monadic展开,解除它就像takeWhile,不是微不足道的.另一件可能有意义的事情是更具普遍性的展示,如签名(MonadMaybe m) => (b -> m (a, b)) -> b -> m [a]和伴随的MaybeT变压器,但标准库中也不存在,monad变换器无论如何都是绝望之坑.第三种方法可能是找到某种方法来将两者Maybe和未知单子一起概括为MonadPlus类似的东西.

当然,可能有其他方法具有不同的结构,但我怀疑你可能会发现任何需要递归进入"monad"的函数的类似尴尬,例如,每一步在概念上引入了另一层必须是与消除>>=,join等

总结:首先检查你写的函数最好是在没有显式递归的情况下表达,使用unfoldM不存在的递归组合器(某些风格).你可以自己编写组合子(正如人们所做的那样takeWhileM),在Hackage上挖掘monadic递归组合器,或者只是保留你的代码.