Предотвращение явной рекурсии в Haskell
Следующая простая функция применяет данную одноместную функцию многократно, пока она не поражает Ничто, в которой точке она возвращает последнее, которое неничто не оценивает. Это делает то, в чем я нуждаюсь, и я понимаю, как это работает.
lastJustM :: (Monad m) => (a -> m (Maybe a)) -> a -> m a
lastJustM g x = g x >>= maybe (return x) (lastJustM g)
Как часть моего самообразования в Haskell я стараюсь избегать явной рекурсии (или, по крайней мере, поймите, как к) каждый раз, когда я могу. Кажется, что в этом случае должно быть простое неявно рекурсивное решение, но я испытываю затруднения при понимании этого.
Я не хочу что-то как одноместная версия takeWhile, так как могло быть дорого собраться весь, предничто не оценивает, и я не забочусь о них так или иначе.
Я проверил Hoogle на подпись, и ничто не обнаруживается. m (Maybe a) бит заставляет меня думать, что преобразователь монады мог бы быть полезным здесь, но у меня действительно нет интуиций, я должен был бы придумать детали (все же).
Вероятно, или смущающе легко сделать это или смущающе легкий видеть, почему это не может или не должно быть сделано, но это не будет первым разом, когда я использовал самозатруднение в качестве педагогической стратегии.
Обновление: Я мог, конечно, обеспечить предикат вместо использования Maybe: что-то как (a -> Bool) -> (a -> m a) -> a (возвращение последнего значения, для которого предикат верен), работал бы точно также. То, чем я интересуюсь, является способом записать любую версию без явной рекурсии, с помощью стандарта combinators.
Фон: вот упрощенный рабочий пример для контекста: предположите, что мы интересуемся случайными блужданиями в квадрате единицы, но мы только заботимся о точках выхода. У нас есть функция следующего шага:
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 ответа
Во многом предотвращение явной рекурсии связано с составлением встроенных рекурсивных комбинаторов, которые обычно работают с очень общими неподтвержденными значениями. То же самое в Functor, Monad или другом поднятом типе иногда работает с использованием базовых операций поднятия, таких как fmap , <*> , >> = и скоро. В некоторых случаях предварительная версия уже присутствует, например, mapM , zipWithM и так далее. В других случаях, как в случае takeWhile , подъем не является тривиальным, и встроенная версия не предоставляется.
Ваша функция действительно имеет характеристики чего-то, что должно быть улучшенной версией стандартных комбинаторов. Итак, сначала давайте выделим монаду, чтобы восстановить функцию, которую вы неявно поднимаете:
lastJust :: (a -> Maybe a) -> a -> a
Слово «последняя» здесь дает нам подсказку; неявная рекурсия часто использует временные списки в качестве управляющих структур. Итак, вам нужно применить последний к списку, сгенерированному повторением функции до получения 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 и т. д.
Вкратце: на первый взгляд ваша функция в том виде, в котором она написана, лучше всего выражается без явной рекурсии с использованием рекурсивного комбинатора (некоторый вариант unwoldM ), которого не существует. Вы можете написать комбинатор самостоятельно (как люди сделали с takeWhileM ), покопаться в Hackage в поисках монадических рекурсивных комбинаторов или просто оставить свой код как есть.
Мне не нужно что-то вроде монадической версии
takeWhile, так как сбор всех значений до Nothing может быть дорогостоящим, и я все равно не забочусь о них.
Монадические списки takeWhile не собирает все значения до 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