purescript/purescript-tailrec

A type class which captures stack-safe monadic tail recursion

purescript-tailrec

A type class which captures stack-safe monadic tail recursion.

Installation

spago install tailrec

Usage

The PureScript compiler performs tail-call elimination for self-recursive functions, so that a function like

pow :: Int -> Int -> Int
pow n p = go { accum: 1, power: p }
  where
  go { accum: acc, power: 0 } = acc
  go { accum: acc, power: p } = go { accum: acc * n, power: p - 1 }

gets compiled into an efficient while loop.

However, we do not get the same benefit when using monadic recursion:

powWriter :: Int -> Int -> Writer Product Unit
powWriter n = go
  where
  go 0 = return unit
  go m = do
    tell n
    go (m - 1)

However, we can refactor the original function to isolate the recursive function call:

pow :: Int -> Int -> Int
pow n p = tailRec go { accum: 1, power: p }
  where
  go :: _ -> Step _ Int
  go { accum: acc, power: 0 } = Done acc
  go { accum: acc, power: p } = Loop { accum: acc * n, power: p - 1 }

where the tailRec function is defined in the Control.Monad.Rec.Class module, with type:

tailRec :: forall a b. (a -> Step a b) -> a -> b

In the body of the loop, instead of calling the go function recursively, we return a value using the Loop constructor. To break from the loop, we use the Done constructor.

This pattern can be generalized to several monad transformers from the purescript-transformers library using the following type class:

class Monad m <= MonadRec m where
  tailRecM :: forall a b. (a -> m (Step a b)) -> a -> m b

Documentation

Module documentation is published on Pursuit.

purescript-tailrec's Issues

Make Function instance of MonadRec

In sanctuary-type-classes we have made function instance of MonadRec so it could be implemented here too.

tailRecEff space leak

https://github.com/purescript/purescript-tailrec/blob/master/src/Control/Monad/Rec/Class.purs#L126

The reference to a will be unnecessarily held while the loop is run.

Add whileJust and untilJust

I have defined this helpers in different projects, and others have done the same too, for example untilJust is same as loop, filtered,untilSuccessful. I would like to add this basic and useful helpers to this lib:

-- | While supplied computation evaluates to `Just _`, it will be
-- | evaluated repeatedly and results will be combined using monoid instance.
whileJust :: forall a m. Monoid a => MonadRec m => m (Maybe a) -> m a
whileJust m = tailRecM (\v -> m <#> maybe (Done v) (Loop <<< (v <> _))) mempty

-- | Supplied computation will be executed repeatedly until it evaluates
-- | to `Just value` and then that `value` will be returned.
untilJust :: forall a m. MonadRec m => m (Maybe a) -> m a
untilJust m = tailRecM (\_ -> m <#> maybe (Loop unit) Done) unit

They are defined in here too http://hackage.haskell.org/package/monad-loops-0.4.3/docs/Control-Monad-Loops.html, There is also it's PS version of this lib, but looks like it's unmaintained https://github.com/mlang/purescript-monad-loops

---

One argument against adding this funcitons is that it will open can of warms and we would wanna add more and more later and it should instead be done in separate purescript-monad-loops like lib.

I get that the that point, but I think adding whileJust and untilJust will be worthwhile as they are useful and sort of basic constructs.

to convince why I think {while,until}Just are basic functions see this implementations:

whileM :: forall a m. MonadRec m => Monoid a => m Boolean -> m a -> m a
whileM mCondition mRes = whileJust do
  condition <- mCondition
  if condition then mRes <#> Just else pure $ Nothing

untilM :: forall a m. Monoid a => MonadRec m => m a -> m Boolean -> m a
untilM mRes mCondition = whileJust do
  res <- mRes
  condition <- mCondition
  pure $ if condition then Nothing else Just res

iterateWhile :: forall a m. MonadRec m => (a -> Boolean) -> m a -> m a
iterateWhile p = iterateUntil $ not p

iterateUntil :: forall a m. MonadRec m => (a -> Boolean) -> m a -> m a
iterateUntil p x = x >>= iterateUntilM p (const x)

iterateUntilM :: forall a m. MonadRec m => (a -> Boolean) -> (a -> m a) -> a -> m a
iterateUntilM p f = execStateT $ whileM (gets p) (get >>= f >>> lift >>= put)

Define MonadRec for Maybe

purescript/purescript-maybe#33 (comment)

MonadEffect instance

Would this work?

instance monadEffectRec :: MonadEffect m => MonadRec m where
  tailRecM = liftEffect <<< tailRecM

Unknown value U.unsafeCoerceEff

This library gets installed when i try to install purescript-arrays with pulp 10 and psc 0.10.2, but it fails during compilation with the following error:

purescript-invariant#2.0.0 bower_components/purescript-invariant
└── purescript-prelude#2.5.0
* Building project in /home/francesco/repos/crumbs
Compiling Control.Monad.Rec.Class
Error found:
in module Control.Monad.Rec.Class
at /home/francesco/repos/crumbs/bower_components/purescript-tailrec/src/Control/Monad/Rec/Class.purs line 128, column 8 - line 128, column 31

  Unknown value U.unsafeCoerceEff


See https://github.com/purescript/purescript/wiki/Error-Code-UnknownName for more information,
or to contribute content related to this error.


* ERROR: Subcommand terminated with exit code 1

Probably i'm doing something obviously wrong like using the wrong compiler version or something similar, but i'm not sure. The version of purescript-arrays that my Bower client is trying to install is the most recent, 3.2.1