On Tue, Sep 27, 2022 at 10:15:29AM +1000, Isaac Elliott wrote:

https://pursuit.purescript.org/packages/purescript-tailrec/6.1.0/docs/Contro... seems like a good starting point

Seems like that package may have missed a trick to encode tail recursiveness through a distribution property: {-# LANGUAGE LambdaCase #-} {-# LANGUAGE DeriveFunctor #-} module RecExperiment where data Step a b = Loop a | Done b deriving Functor tailRec :: (a -> Step a b) -> a -> b tailRec f = go . f where go (Loop a) = go (f a) go (Done b) = b -- | This works for all monads tailRecM1 :: Monad m => (a -> m (Step a b)) -> a -> m b tailRecM1 f a = do f a >>= \case Loop a' -> tailRecM1 f a' Done b -> pure b -- | This works for all monads with a "distribute" operation over -- @Step a@ and is guaranteed tail recursive via @tailRec@. tailRecM2 :: Monad m => (m (Step a b) -> Step a (m b)) -> (a -> m (Step a b)) -> a -> m b tailRecM2 distribute f = tailRec (distribute . f)

On Tue, Sep 27, 2022 at 05:24:43PM -0400, A S wrote:

The definition tailRecM1, while it typechecks, will not always operate in constant stack space

Correct.

As for tailRecM2, unfortunately this precludes many useful and nontrivial MonadRec instances such as Effect and Aff, which admit no such distributing natural transformation (if this is what you actually meant for the first argument to be).

Correct, the distribution property is too strong to capture all MonadRec instances. However, it does capture Maybe, Either e and Identity. To capture (r ->)/Reader we need something more general (tailRecM3) which is sadly significantly less pleasant, but unless I am much mistaken it captures all instances of tailRecM that use tailRec. Maybe it's too unpleasant to be used in practice as an alternative of a direct implementation of tailRecM. Tom {-# LANGUAGE LambdaCase #-} module Rec where import Data.Functor.Identity (Identity(Identity)) data Step a b = Loop a | Done b onDone :: (b -> b') -> Step a b -> Step a b' onDone f = \case Loop a -> Loop a Done b -> Done (f b) tailRec :: (a -> Step a b) -> a -> b tailRec f = go . f where go (Loop a) = go (f a) go (Done b) = b -- | This works for all monads but is not necessarily stack safe. tailRecM1 :: Monad m => (a -> m (Step a b)) -> a -> m b tailRecM1 f a = do f a >>= \case Loop a' -> tailRecM1 f a' Done b -> pure b -- | This works for all monads with a particular distribution property -- and is stack safe through the use of @tailRec@. tailRecM3 :: Monad m => ((a -> m (Step a b)) -> m (a -> Step a l)) -> (l -> m b) -> (a -> m (Step a b)) -> a -> m b tailRecM3 distribute finish f a = do g <- distribute f finish (tailRec g a) tailRecReader :: (a -> r -> Step a b) -> a -> r -> b tailRecReader = tailRecM3 (\f r a -> f a r) (\b _ -> b) tailRecDistribute :: Monad m => (m (Step a b) -> Step a (m b)) -> (a -> m (Step a b)) -> a -> m b tailRecDistribute distribute = tailRecM3 (\f -> pure (\a -> distribute (f a))) id tailRecMaybe :: (a -> Maybe (Step a b)) -> a -> Maybe b tailRecMaybe = tailRecDistribute $ \case Nothing -> Done Nothing Just j -> onDone pure j tailRecEither :: (a -> Either e (Step a b)) -> a -> Either e b tailRecEither = tailRecDistribute $ \case Left e -> Done (Left e) Right r -> onDone pure r tailRecIdentity :: (a -> Identity (Step a b)) -> a -> Identity b tailRecIdentity = tailRecDistribute $ \case Identity i -> onDone pure i