A type class which captures stack-safe monadic tail recursion
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
src/Control/Monad/Rec Fix tailRecM documentation Aug 9, 2018
test/Test Updates for 0.12 Apr 16, 2018
.gitignore
.travis.yml Update for PureScript 0.11 Mar 26, 2017
LICENSE Update dependencies, license May 23, 2018
README.md Either/Left/Right => Step/Loop/Done in README.md Jan 19, 2017
bower.json Update dependencies, license May 23, 2018
package.json Update dependencies, license May 23, 2018

README.md

purescript-tailrec

Latest release Build status

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

Installation

bower i purescript-tailrec

Usage

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

pow :: Number -> Number -> Number
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 :: Number -> Number -> 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 :: Number -> Number -> Number
pow n p = tailRec go { accum: 1, power: p }
  where
  go :: _ -> Step _ Number
  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.