Избегание явной рекурсии в Haskell

Question

Следующая простая функция применяет данную монадическую функцию итеративно, пока она не ударит ничто, и в этот момент она возвращает последнее значение, отличное от Ничего. Он делает то, что мне нужно, и я понимаю, как это работает.

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, так как это может быть дорого собрать все значения до-Ничего, и я все равно их не волнует.

Я проверил Hoogle на подпись, и ничего не появляется. Сбой m (Maybe a) заставляет меня думать, что здесь может быть полезен трансформатор монады, но у меня нет действительно интуиций, которые мне нужны, чтобы придумать детали (пока).

Возможно, это или смущающе легко сделать это, или смущающе легко понять, почему это невозможно или не должно быть сделано, но это было бы не в первый раз, когда я использовал самосознание как педагогическую стратегию.

Update: Я мог бы, конечно, обеспечить предикат вместо использования 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 

К сожалению, на данный момент мы вроде застрял, потому что (к моему знанию) нет монадического разворота и подъема, как, например, takeWhile, а не тривиально. Еще одна вещь, которая может иметь смысл, - это более общий разворот с сигнатурой вроде (MonadMaybe m) => (b -> m (a, b)) -> b -> m [a] и сопроводительным трансформатором MaybeT, но это тоже не существует в стандартных библиотеках, а монадные трансформаторы - это, как ни странно, Пит Отчаяния. Третий подход может заключаться в том, чтобы найти способ обобщить как Maybe так и неизвестную монаду как MonadPlus или что-то подобное.

Конечно, могут быть другие подходы с другой структурой, но я подозреваю, что вы, вероятно, найдете такую ​​же неловкость с любой функцией, которая должна быть рекурсивной, «войдет» в монаду, например, каждый шаг концептуально вводит другой слой, который должен быть устранен с >>=, join и т.д.

В заключении: при первой проверке вашей функции, как написано лучше всего выражаются без явной рекурсии, используя рекурсивный комбинатор (некоторый привкус unfoldM), который не существует. Вы можете написать комбинатор самостоятельно (как это делали люди с takeWhileM), идите копаться в Hackage для монадических рекурсивных комбинаторов или просто оставляйте свой код как есть.

Answer 2

Я не хочу что-то вроде монадической версии takeWhile, так как это может быть дорогостоящим, чтобы собрать все ценности, предварительно ничего, и я не забочусь о них в любом случае.

Monadic-lists takeWhile не собирает все значения pre-Nothing, если вы явно не хотите этого делать. Это будет 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