Как избежать явной рекурсии в Haskell

Question

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

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

Как часть моего самообразования в Хаскеле, я стараюсь избегать явной рекурсии (или, по крайней мере, понимать, как), когда могу. Похоже, что в этом случае должно быть простое не явное рекурсивное решение, но у меня возникают проблемы с его выяснением.

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

Я проверил Hoogle на подпись, и ничего не появляется. Бит 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 даст нам новую точку данных.

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 из пакета «Список» , используемого в этом ответе на тот самый вопрос, на который вы ссылаетесь.

Что касается функции, которую вы хотите реализовать:

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