Re: [boost] [Hana] Informal review request

Subject: Re: [boost] [Hana] Informal review request
From: Louis Dionne (ldionne.2_at_[hidden])
Date: 2015-03-17 13:39:50

Eric Niebler <eniebler <at> boost.org> writes:

> 
> On 3/16/2015 4:43 PM, Louis Dionne wrote:
> <snip>
> >    However, there is a more serious
> >    incompatibility stemming from how `reverse_fold` is usually specified
> >    and understood: as starting from the end. This causes a problem for
> >    infinite data structures, which obviously have no reachable end. Instead,
> >    `foldr` is usually specified recursively in a way that makes it possible
> >    to right-fold infinite data structures (and it is indeed possible to do
> >    so in Haskell and with MPL11). There is no real support for infinite data
> >    structures in Hana right now, but simple Concept generalizations which I
> >    have been thinking about might make this possible. In summary$Ý…¹ÐÑ¼(ø€ø€€€µ…­”ÍÕÉ”$´¹½Ð‰±½­¥¹œµåÍ•±˜¥˜$µ…­”Ñ¡”™½±‘°½™½±‘É€¡…¹”°‰ÕÐ(ø€ø€€€É•ÍЁ…ÍÍÕÉ•Ñ¡…Ё$Õ¹‘•ÉÍѽ½Ù•ÉäÝ•±°Ñ¡”Á•½Á±”Ì‘•Í¥É”¸(ø€(ø$Á•Éͽ¹…±±ä‘½¸ÐÍ•”„Áɽ‰±•´Ý¥Ñ ­••Á¥¹œ™½±‘ȝ͕́µ…¹Ñ¥Ì‰ÕÐ(ø¡…¹¥¹œÑ¡”¹…µ”Ñ¼É•Ù•ÉÍ•}™½±°¥˜Ñ¡…Н́ݡ…ЁÁ•½Á±”Ý…¹Ð¸()Q¡”Áɽ‰±•´¥ÌÑ¡…Ё¥¸Ñ¡”¥¹™¥¹¥Ñ”…Í”°¥ÐÌ¹½Ð„€‰É•Ù•ÉÍ”ˆ™½±…¹åµ½É”°)…¹¡•¹”Ñ¡”¹…µ”‰•½µ•ÌÙ•É䁵¥Í±•…‘¥¹œ¸½ÈÑ¡½Í”Ñ¡…Ёµ¥¡Ð‰”É•…‘¥¹œ€)Ñ¡¥Ì…¹Ý½¹‘•É¥¹œÝ¡…Ё$µ•…¸‰ä¹½¸µÍÑÉ¥Ð™½±‘Ì°¡•É”Ì¡½Ü™½±‘É€…¸€)‰”‘•™¥¹•É•ÕÉÍ¥Ù•±äè((€€€Ñ•µÁ±…Ñ”€ñÑåÁ•¹…µ”M•ÅÕ•¹”°ÑåÁ•¹…µ”MÑ…Ñ”°ÑåÁ•¹…µ”ø(€€€…ÕѼ™½±‘È¡M•ÅÕ•¹”áÌ°MÑ…Ñ”Ì°˜¤ì(€€€€€€€¥˜€¡¥Í}•µÁÑä¡á̤¤(€€€€€€€€€€€É•ÑÕɸÌì(€€€€€€€•±Í”€(€€€€€€€€€€€É•ÑÕɸ˜¡¡•…¡á̤°™½±‘È¡Ñ…¥°¡áÌ2Âb’“°¢Ð ¤–â7G&–7BWfÇVF–öâ6öçFW‡BÂv†VâF†RVÇ6R'&æ6‚—2F¶VâÂF†RœÚ]™p¨Ø[țۘ\È™]™\ˆ]˜[X]Yˆ\È[ÝÜÂœ›ØÙ\ÜÚ[™È[™š[š]H\ÝÈ^š[H[™Üš][™ÈÚܝXÚ\˜ÝZ][™È[ÛÜš]\ÈœÝXÚ\‚ˆ[\]H\[˜[YHÙ\]Y[˜ÙK\[˜[YH™YXØ]O‚ˆ›ÛÛ[žWÛÙŠÙ\]Y[˜ÙHË™YXØ]H™Y
Hˆ™]\›ˆ›ÛŠË˜[ÙK×J]]È]]ÈJHˆ™]\›ˆ™Y

H™Y
JNˆJNˆB‚š[\XÚ]Kˆ[ˆHX›Ý™H^[\KYˆ™Y

X™]\›œÈYH›Ü‚œÛÛYH[ˆHÛÜœ™\ÜÛ™[™È™Y
JX\È™]™\ˆ]˜[X]Y˜™XØ]\ÙHÚܝXÚ\˜ÝZ]ˈ™XØ]\ÙHÙIÜ™H[ˆH\Ý]XØ[››Û‹\ÝšXÝ]˜[X][ÛˆÛÜ›\ÈØ]\Ù\ÈX›ÝÈ™H]˜[X]Y˜][ˆÝÙ]™\‹Yˆ[ÝHÛȘXÚÈÈHYš[š][ÛˆÙˆ›Û˜X›Ý™KHXØ\È[ˆ^™\ÜÚ[ÛˆÙˆH›Ü›B‚ˆ›ÛŠZ[
ÊKËŠB‚Ú\™Hˆ\ÈÝ\ˆ[X™H[ˆHny_of` algorithm. So basically, we're
saying that the recursive call to `foldr` is not evaluated, and hence
our `any_of` algorithm short-circuits automatically. 

So anyway, my point is that seeing right-folds as

    f(x1, f(x2, f(x3, ...f(xN, state)))

is slightly more general than seeing them as starting from the end,
because it allows for the case where there's no end. That being said,
I'm aware that we're _not_ in Haskell and so it does not really apply
to Hana. I'd just like to make sure that I (or someone else) won't find
a nice application for infinite data structures in Hana that would make
me regret that choice.

But writing this, I have the germ of an idea that these lazy folds
might be nothing more than a monadic fold with the Lazy Monad, whicݽձÉ•Í½±Ù”Ñ¡”¥ÍÍÕ”¸$¡…Ù”Ñ¼±½½¬¥¹Ñ¼Ñ¡¥Ì™ÕÉÑ¡•È‰•™½É”$…¸)ͅ䁅¹åÑ¡¥¹œ¸(((ø€ø€Ü¸%¸„‘¥™™•É•¹ÐÑ¡É•…lÙt°¥ÐÝ…́Í՝•ÍÑ•Ñ¡…Ёѡ”1½¥…°€(ø€ø€€€½¹•ÁЁ͡½Õ±¥¹Ñ•É…ÐÝ•±°Ý¥Ñ 1…é䁍½µÁÕÑ…Ñ¥½¹Ì¸$¡…Ù”‰•Õ¸€(ø€ø€€€Ñ¼¥¹Ù•ÍÑ¥…Ñ”Á½ÍÍ¥‰±”Ý…ǻ½˜¹¥•±äÑ她œ‰½Ñ Ñ½•Ñ¡•È°…́…¸€(ø€ø€€€‰”Í••¸…ЁlÝt°…¹Ý¥±°ÑÉäÑ¼¡…Ù”Í½µ•Ñ¡¥¹œ‘•™¥¹¥Ñ¥Ù”‰•™½É”„€(ø€ø€€€™½Éµ…°É•Ù¥•Ü¸(ø€(ø€ølÝt¡ÑÑÀè¼½±‘¥½¹¹”¹¥Ñ¡Õˆ¹¥¼¼ÈÀÄÔ¼À̼Äؽ±…饹•Í̵…̵„µ½µ½¹…(ø€(øݕͽµ”¸$´É•…±±ä±½½­¥¹œ™½É݅ɐÑ¼É•…‘¥¹œÑ¡¥Ì¸()́¥ÐÍÑ…¹‘Ì°$™¥¹Ñ¡”Á½ÍЁѼ‰”„‰¥Ð‰½É¥¹œ‰•…ÕÍ”Ñ¡•É”Ì)¹¼¥¹Ñ•É•ÍÑ¥¹œÕÍ”…Í”…Ёѡ”•¹¸$´Ñ¡¥¹­¥¹œ…‰½ÕЁ•áÁ…¹‘¥¹œ)½¸¡½ÜÝ”…¸½µÁ½Í”±…é䁍½µÁÕÑ…Ñ¥½¹Ì€¡…́ÁÁ±¥…ѥٕ́…¹5½¹…‘̤°)Ý¡¥ ¥ÌÉ•…±±äÑ¡”™Õ¸Á…ÉЁ…¹…±F†R'BF†Bv—fW2W2&WGG§6VÖçF–72f÷"6ö×÷6–ær&&—G&'’Ƨ’6ö×WFF–öç2âÆö6ÆÇ’Â’†fP§&÷F÷G—VBæWr–eöv—F‚&÷F‚Ƨ’æBæöâÖƧ’6VÖçF–72v†–6‚’›Øš[™È›ÜˆŽ\K[‚ˆÛÛ™][Û˜[HÙ[XÝ[™ÈHÝXœÝ]][Û‹È™H™]H[œØ]\Ù˜XÝÜžK‚ˆÛÈ]XÚXYÚXËÛÈY™šXÝ[ÈÜ›ÚË[™ÛÝ[]™[ˆØ]\ÙH\œ›ÜœÈžBˆØ]\Ú[™È[˜Y™\[[œÝ[X][ÛœÈÙˆ[™ÜÈ›ÝYX[È™Bˆ[œÝ[X]YKHÚXÚYX[œÈ[™ÜÈ™YYÈ™H›ÝXÝ	ÙY]Ë]ˈBˆÛÝ[™Y™\ˆHÚ[\\‹[Ü™H™YXÝX›H[ÛÜš]K]™[ˆ]H^[œÙBˆ\ÜÈ]H[X™\Ë‚‚’HÛÈYÜ™YH]T	ÜÈ[X™H^™\ÜÚ[ÛœÈ\™H›È[‹\ÜXÚX[Hš[\[Y[ˆ›Üˆ[˜KHÛÝ[Z[H›ÜˆÛÛY][™È]XÚÚ[\\ˆ™XØ]\ÙBš]ÛÝ[\Ý™HHØ^HÈ]ZXÚÛHÛÛ\ÜÙH\K[]™[ÛÛ\]][ÛœÈ[‚›Ü™\ˆÈØ]™HHÛÝ\HÙˆ[™\ˈ›Üˆ[Ü™HÛÛ\^ÛÛ\]][ÛœË^H›Ü[š[Ûˆ\ÈÝ[]Û™HÚÝ[\ÙHZ[ˆ[˜Ý[ۜ˂‚‚”™YØ\™Ë“ÝZ\€