10

下面的简单函数迭代地应用给定的一元函数，直到它遇到一个 Nothing，此时它返回最后一个非 Nothing 值。它可以满足我的需要，并且我了解它的工作原理。

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

作为我在 Haskell 中自我教育的一部分，我试图尽可能避免显式递归（或至少了解如何）。在这种情况下，似乎应该有一个简单的非显式递归解决方案，但我无法弄清楚。

我不想要像monadic 版本的东西takeWhile，因为收集所有 pre-Nothing 值可能很昂贵，而且我也不关心它们。

我检查了 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会给我们一个新的数据点。

4

2 回答 2

9

避免显式递归的很多内容是编写内置递归组合器，它们通常适用于非常通用的未提升值。在 Functor、Monad 或其他提升类型中执行相同的操作有时可以使用基本提升操作，如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

不幸的是，在这一点上我们有点卡住了，因为（据我所知）没有单子展开，举起它，就像takeWhile，不是微不足道的。另一件可能有意义的事情是一个更一般的展开，带有一个类似的签名(MonadMaybe m) => (b -> m (a, b)) -> b -> m [a]和一个伴随的MaybeT转换器，但这在标准库中也不存在，而且单子转换器无论如何都是绝望的深渊。第三种方法可能是找到某种方法将两者Maybe和未知单子概括为MonadPlus或类似的东西。

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

总结：首先检查您所写的函数最好在没有显式递归的情况下表达，使用unfoldM不存在的递归组合器（某种味道）。您可以自己编写组合器（就像人们已经完成的那样takeWhileM），在 Hackage 上挖掘单子递归组合器，或者保持您的代码不变。

于 2010-05-18T18:17:48.247 回答
3

我不想要像 monadic 版本的东西takeWhile，因为收集所有 pre-Nothing 值可能很昂贵，而且我也不关心它们。

Monadic-liststakeWhile不会收集所有 pre-Nothing 值，除非您明确想要这样做。这将takeWhile来自“列表”包，在此答案中用于您链接到的问题。

至于您希望实现的功能：

{-# LANGUAGE ScopedTypeVariables #-}

import Control.Monad.ListT (ListT) -- from "List" package on hackage
import Data.List.Class (takeWhile, iterateM, lastL)
import Prelude hiding (takeWhile)

thingM :: forall a m. Monad m => (a -> Bool) -> (a -> m a) -> m a -> m a
thingM pred stepM startM =
    lastL $ takeWhile pred list
    where
        list :: ListT m a
        list = iterateM stepM startM
于 2010-05-18T22:37:08.923 回答