在Haskell中避免顯式遞歸

Question

下面的簡單函數迭代地應用給定的一元函數，直到它遇到一個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之類的東西，因爲收集所有的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會給我們一個新的數據點。

Answer 1

許多避免顯式遞歸的關鍵是構建內置的遞歸組合器，它通常用於非常通用的未提升值。在Functor，Monad或其他提升類型中執行相同的操作有時可以使用基本提升操作，如fmap,<*>，>>=等。在某些情況下，預升級版本已經存在，如mapM,zipWithM等。其他時間，如takeWhile，提升並不重要，也不提供內置版本。

您的函數的確具有某些應該是標準組合器的提升版本的特性。因此，首先，讓我們帶出的單子重建功能你隱式起重：

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變壓器這樣的簽名，但這在標準庫中也不存在，單子變壓器無論如何都是絕望之坑。第三種方法可能是找到某種方法來將Maybe和未知單子概括爲MonadPlus或類似的東西。

當然，也可能有其他方法有不同的結構，但我懷疑你可能會發現類似的尷尬與任何功能，需要遞歸進入一個單子，例如，每一步從概念上引入另一個層必須與>>=，join被淘汰等

總結：在書面沒有明確的遞歸最好的表達，使用遞歸組合子（的unfoldM一番風味）首先檢查你的函數不存在。你可以自己編寫組合器（就像人們用takeWhileM完成的那樣），去Hackage尋找monadic遞歸組合器，或者直接離開你的代碼。

Answer 2

我不希望像takeWhile的monadic版本的東西，因爲收集所有pre-nothing值可能會很昂貴，而且我也不關心它們。

一元列表takeWhile不會收集所有的無前值，除非您明確要這樣做。這將是takeWhile從"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