代码之家 › 专栏 › 技术社区 › Travis Brown

避免haskell中的显式递归

monads functional-programming haskell

Travis Brown · 技术社区 · 15 年前

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

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

作为我在Haskell的自我教育的一部分,我尽量避免使用显式递归(或者至少理解如何使用)。在这种情况下,似乎应该有一个简单的非显式递归解决方案,但是我很难找到它。

我不想要这样的东西 a monadic version 属于 takeWhile 因为收集所有的无前期价值可能会很昂贵,而且我也不在乎它们。

我查了胡格尔的签名,结果什么也没出现。这个 m (Maybe a) 有一点让我觉得单子变压器可能在这里有用,但我还没有真正的直觉,我需要想出细节。

这可能是令人难堪的容易做这件事,也可能是令人难堪的容易明白为什么不能或不应该做,但这不会是我第一次用自卑作为教学策略。

更新: 当然,我可以提供一个谓词而不是使用 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 会给我们一个新的数据点。

2 回复 | 直到 15 年前

C. A. McCann Ravikant Cherukuri 15 年前

避免显式递归的许多方法是组成内置的递归组合器,这些组合器通常用于非常通用的未赋值。在一个函数、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

不幸的是,在这一点上,我们有点卡住了,因为(据我所知)没有一元展开和提升,就像 取而代之 ,不是琐碎的。另一件有意义的事情是一个更为普遍的展开,带有如下签名: (MonadMaybe m) => (b -> m (a, b)) -> b -> m [a] 和一个随行的 MaybeT Transformer,但标准库中也不存在,Monad Transformer无论如何都有点绝望。第三种方法可能是找到某种方法来概括两者 Maybe 而无名的Monad out as MonadPlus 或者类似的东西。

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

总之:首先检查您编写的函数,最好不使用显式递归来表示,使用递归组合器(某种风格的 unfoldM )那是不存在的。你可以自己写组合词(就像人们所做的那样) takeWhileM )继续挖掘一元递归组合器的黑客技术,或者保持代码原样。

Community CDub 8 年前

我不想要像单音版的 takeWhile 因为收集所有的无前期价值可能会很昂贵,而且我也不在乎它们。

一元列表 取而代之 除非您明确希望这样做,否则不要收集所有pre-nothing值。这将是 取而代之 从 "List" package ,用于 this answer 与你所联系的问题有关。

关于您希望实现的功能:

{-# 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