Re: characterization of subset of Monads that respect tail calls?

--===============2075243485112562055==
Content-Type: multipart/alternative; boundary="00000000000082eac405e9af4681"

--00000000000082eac405e9af4681
Content-Type: text/plain; charset="UTF-8"

Hi Tom,

It's possible I'm misunderstanding what you're saying. The definition
tailRecM1, while it typechecks, will not always operate in constant stack
space (at least in PureScript). The paper "Stack Safety for Free" provides
a pretty much analogous definition by way of illustration and says as much
about it.

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).

Thanks,
Asad

On Tue, Sept 27, 2022, 4:00 p.m. Tom Ellis <
[email protected]> wrote:

> On Tue, Sep 27, 2022 at 10:15:29AM +1000, Isaac Elliott wrote:
> >
> https://pursuit.purescript.org/packages/purescript-tailrec/6.1.0/docs/Control.Monad.Rec.Class
> > 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)
> _______________________________________________
> Libraries mailing list
> [email protected]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>

--00000000000082eac405e9af4681
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"auto"><div dir=3D"auto">Hi Tom,<div dir=3D"auto"><br></div><div=
 dir=3D"auto">It&#39;s possible I&#39;m misunderstanding what you&#39;re sa=
ying. The definition tailRecM1, while it typechecks, will not always operat=
e in constant stack space (at least in PureScript). The paper &quot;Stack S=
afety for Free&quot; provides a pretty much analogous definition by way of =
illustration and says as much about it.</div><div dir=3D"auto"><br></div><d=
iv dir=3D"auto">As for tailRecM2, unfortunately this precludes many useful =
and nontrivial MonadRec instances such as Effect and Aff, which admit no su=
ch distributing natural transformation (if this is what you actually meant =
for the first argument to be).</div><div dir=3D"auto"><br></div><div dir=3D=
"auto">Thanks,</div><div dir=3D"auto">Asad</div></div><br><div class=3D"gma=
il_quote"><div dir=3D"ltr" class=3D"gmail_attr">On Tue, Sept 27, 2022, 4:00=
 p.m. Tom Ellis &lt;<a href=3D"mailto:tom-lists-haskell-cafe-2017@jaguarpaw=
.co.uk" target=3D"_blank" rel=3D"noreferrer">tom-lists-haskell-cafe-2017@ja=
guarpaw.co.uk</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quote" sty=
le=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">On Tue=
, Sep 27, 2022 at 10:15:29AM +1000, Isaac Elliott wrote:<br>
&gt; <a href=3D"https://pursuit.purescript.org/packages/purescript-tailrec/=
6.1.0/docs/Control.Monad.Rec.Class" rel=3D"noreferrer noreferrer noreferrer=
" target=3D"_blank">https://pursuit.purescript.org/packages/purescript-tail=
rec/6.1.0/docs/Control.Monad.Rec.Class</a><br>
&gt; seems like a good starting point<br>
<br>
Seems like that package may have missed a trick to encode tail<br>
recursiveness through a distribution property:<br>
<br>
<br>
<br>
{-# LANGUAGE LambdaCase #-}<br>
{-# LANGUAGE DeriveFunctor #-}<br>
<br>
module RecExperiment where<br>
<br>
data Step a b =3D Loop a | Done b<br>
=C2=A0 deriving Functor<br>
<br>
tailRec :: (a -&gt; Step a b) -&gt; a -&gt; b<br>
tailRec f =3D go . f<br>
=C2=A0 where<br>
=C2=A0 go (Loop a) =3D go (f a)<br>
=C2=A0 go (Done b) =3D b<br>
<br>
-- | This works for all monads<br>
tailRecM1 :: Monad m =3D&gt; (a -&gt; m (Step a b)) -&gt; a -&gt; m b<br>
tailRecM1 f a =3D do<br>
=C2=A0 f a &gt;&gt;=3D \case<br>
=C2=A0 =C2=A0 Loop a&#39; -&gt; tailRecM1 f a&#39;<br>
=C2=A0 =C2=A0 Done b -&gt; pure b<br>
<br>
-- | This works for all monads with a &quot;distribute&quot; operation over=
<br>
-- @Step a@ and is guaranteed tail recursive via @tailRec@.<br>
tailRecM2 ::<br>
=C2=A0 Monad m =3D&gt;<br>
=C2=A0 (m (Step a b) -&gt; Step a (m b)) -&gt;<br>
=C2=A0 (a -&gt; m (Step a b)) -&gt;<br>
=C2=A0 a -&gt;<br>
=C2=A0 m b<br>
tailRecM2 distribute f =3D tailRec (distribute . f)<br>
_______________________________________________<br>
Libraries mailing list<br>
<a href=3D"mailto:[email protected]" rel=3D"noreferrer noreferrer" targ=
et=3D"_blank">[email protected]</a><br>
<a href=3D"http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries" rel=
=3D"noreferrer noreferrer noreferrer" target=3D"_blank">http://mail.haskell=
.org/cgi-bin/mailman/listinfo/libraries</a><br>
</blockquote></div></div>

--00000000000082eac405e9af4681--

--===============2075243485112562055==
Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: base64
Content-Disposition: inline

X19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX18KTGlicmFyaWVz
IG1haWxpbmcgbGlzdApMaWJyYXJpZXNAaGFza2VsbC5vcmcKaHR0cDovL21haWwuaGFza2VsbC5v
cmcvY2dpLWJpbi9tYWlsbWFuL2xpc3RpbmZvL2xpYnJhcmllcwo=

--===============2075243485112562055==--