避免在Haskell中使用显式递归

Question

避免在Haskell中使用显式递归

10

下面这个简单的函数会反复应用一个给定的单子函数，直到遇到Nothing为止，此时它会返回最后一个非Nothing值。这正是我所需要的，并且我知道它是如何工作的。

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

作为学习Haskell的一部分，我试图在适当时候避免使用显式递归（或者至少理解如何避免）。在这种情况下，似乎应该有一个简单的非显式递归解决方案，但我很难想明白。

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

我检查了Hoogle的签名，没有显示出任何东西。`m（Maybe a）`的部分让我觉得单子变换器在这里可能有用，但我还没有需要提供细节的直觉（尚未）。

这可能很容易做到，或者很容易看出为什么不能或不应该这样做，但这不会是我作为教育策略使用自我尴尬的第一次。

更新：当然，我可以提供谓词，而不是使用Maybe：类似于`（a -＆gt; Bool） -＆gt;（a -＆gt; m a） -＆gt; 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 这样的代码将会给我们提供一个新的数据点。

- Travis Brown

2

lastJustM = fix (liftM2 ap ((>>=) .) . (flip (maybe . return) .))（好吧我用了 pointfree。） - kennytm

1

@KennyTM：谢谢！我甚至没有想到尝试pointfree，因为我不知道它能处理这种情况。现在我只需要弄清楚它是如何工作的。 - Travis Brown

1

有一种算法可以使用少量组合子将任何东西转化为无点形式；这就是pointfree所使用的。当然，结果可能有用也可能没用 :) - Antal Spector-Zabusky

1

不要被名称所困惑，pointfree 的正确术语是“无点风格”。而且，liftM2 在 ((->) r) 单子中工作吗？这总是提高代码的清晰度... - C. A. McCann

2

fix 的真正问题在于它除了“如果我搞砸了就崩溃程序”之外没有任何语义价值。而 map 和 fold 等函数的价值在于，只要你不对无限列表进行左折叠，它们完美地定义了它们执行的操作，并且不会让你走上错误的道路。 - C. A. McCann

显示剩余3条评论

2个回答

3

我不想要类似于takeWhile的单子版本，因为收集所有的pre-Nothing值可能会很昂贵，而且我也不关心它们。
单子列表takeWhile除非你明确想要这样做，否则不会收集所有的pre-Nothing值。这将是“List”包中的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

- yairchu

我对学习单子列表很感兴趣——例如，我仍然不完全理解它们如何避免收集值。我还没有机会仔细阅读维基上的“正确使用ListT”页面，但您有没有其他起点的建议，这些起点可能不容易通过谷歌搜索“listt haskell”，“monadic lists”等找到？ - Travis Brown

1

@Travis Brown：我不确定你在这里所说的“收集值”是什么意思。如果列表元素被丢弃得越来越快，那么完整的列表实际上永远不会一次性构建出来。这就是我之前所说的关于列表是“控制结构”的意思——折叠列表基本上是具有预先指定调用堆栈的递归，通常是惰性的。 - C. A. McCann

@camccann：我觉得我对单子和惰性的交互方式感到困惑。在我有机会再进行一些阅读和思考之前，我会闭嘴的。感谢你们的回答。 - Travis Brown

@Travis Brown：懒惰有时候是好的，但有时候却不是。总的来说，单子并不是很重要，但是 >>= 操作中隐藏的机制可以增加不同程度的严格性。Identity 强制绑定链，State 强制对状态参数的使用进行额外的严格性检查，IO 强制对涉及外部世界的事物进行完全的严格性检查等等。所有这些单子列表组合器的作用都是尽可能地避免强制执行不必要的操作；否则，天真的 takeWhileM f xs = sequence xs >>= (return . takeWhile f) 就会起作用。 - C. A. McCann

1

@Travis Brown：对于普通列表，takeWhile 并不一定意味着 takeWhiled 部分的列表被存储在内存中——这完全取决于之后对结果列表的操作。同样的情况也出现在这里。单子 takeWhile 不会在“调用它”时消耗列表，而是返回另一个列表。根据之后对它的操作，它可能会被存储在内存中或者不会。在这种情况下，它没有被存储在内存中，因为 lastL 在不保存其值的情况下消耗了它。 - yairchu

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- C. A. McCann · Accepted Answer

避免显式递归的方法之一是组合内置递归组合器，这些组合器通常用于非常通用的未提升值。在Functor、Monad或其他提升类型中使用基本提升操作（如fmap、<*>, >>=等）有时可以实现相同的功能。在某些情况下，已经存在预提升版本，例如mapM、zipWithM等。而对于像takeWhile这样的函数，提升并不是微不足道的，并且没有内置版本提供。

您的函数确实具有应该成为标准组合器提升版本的特征。因此，首先让我们去掉monad以重构您隐式提升的函数：

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

这里的“last”一词给了我们一个提示；非显式递归通常使用临时列表作为控制结构。所以你需要的是应用于迭代函数生成的列表的“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或类似东西的方法。

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

总之：首先检查你编写的函数最好不要使用显式递归来表达，而是使用递归组合器（某种unfoldM的口味），该组合器不存在。你可以自己编写组合器（就像人们使用takeWhileM一样），在Hackage上查找单子递归组合器，或者只是保留你的代码。