

        <cite>Conor</cite>
      <time>0:00</time>
      <p>
          The   Psi   Combinator.   It&#39;s   on   in   Haskell.   We   love   it.   You   got   a   unary   operation.   You   got   a   binary   operation   and   two   arguments   in   common.   You   apply   that   unary   operation   to   both   arguments   and   then   feed   it   to   the   binary   operation.   It&#39;s   super   useful   if   you&#39;re   doing   chunk   buys   and   Haskell.   That&#39;s   called   group   or   group   buy.   Welcome   to   ADSP   the   podcast,   episode   146,   recorded   on   June   21st,   2023.   My   name   is   Connor,   and   today   with   my   co-host   Bryce,   we   continue   to   record   live   from   Italy   on   the   way   to   Venice   during   our   Slovenia   2023   road   trip.   In   today&#39;s   episode,   we   chat   about   improvements   to   our   parallel   stud   unique   implementation,   essential   data   structures,   our   favorite   algorithms   revisited,   and   BQN   superpowers.   Alright,   well,   so   what   am   I   what   am   I   telling   the   listener?   Yeah,   slash   you?
      </p>

        <cite>Bryce</cite>
      <time>1:00</time>
      <p>
          Um   your   your   idea   for   a   implementation   of   unique   that   does   not   need   temporary   storage.
      </p>

        <cite>Conor</cite>
      <time>1:08</time>
      <p>
          Right,   so   we   will   we&#39;ll   we&#39;ll   do   this   with   a   practical   example.   Say   we   have   a   hundred   numbers,   you&#39;re   gonna   chunk   this   up   into   ten   chunks   of   ten.   On   each   of   these   ten   chunks,   you&#39;re   now   gonna   call   a   sequential   unique.   You   don&#39;t   need   this   one   to   be   in   parallel.   The   parallelness   is   the   fact   that   we&#39;re   doing   this   ten   different   times   on   ten   different   chunks.   You   call   unique   on   each   of   these   chunks,   then   once   you&#39;ve   done   that,   you&#39;re   gonna   merge   them,   which   Bryce   asked,   Well,   what   does   that   mean?   You&#39;re   basically   just   gonna   be   copying,   and   you   could   calculate   the   indices   first   if   you   wanted   to   perform   all   the   copies   in   parallel,   or   you   could   just   do   them   one   after   another   sequentially,   where   basically,   because   you&#39;ve   called   unique   on   each   of   these   chunks,   you   basically   have   potentially   removed   some   values,   so   you   need   to   shift   them   all   over.   So   the   copying   is   just   you   know,   copy   the   first   chunk,   copy   the   second   chunk   over   to   where   the   first   chunk   ends,   etc.   And   then   once   you&#39;ve   done   this,   you   still   need   to   perform   one   final   unique,   which   is   gonna   potentially   be   expensive.   Yeah,   so   it   doesn&#39;t   even   work.   Like,   that&#39;s   the   thing.   Yes,   this   avoids   the   umids   the   linear   memory   storage,   but   like   imagine   that   all   your   values   are   unique.   So   like   the   final   the   final   unique   that   you&#39;re   calling   has   to   be   because   it   can&#39;t   be   the   parallel   one,   right?
      </p>

        <cite>Bryce</cite>
      <time>2:27</time>
      <p>
          Because   you   could   yeah,   like   Well,   but   but   why   why   do   you   have   to   do   that   final   unique?
      </p>

        <cite>Conor</cite>
      <time>2:35</time>
      <p>
          Because   if   you   say   in   my   example   of   a   hundred   values,   say   value   number   ten   is   42,   and   value   number   11   is   also   42.   Because   those   each   got   sent   to   a   different   chunk,   there&#39;s   no   looking   back   at   the   what   at   the   equal   value,   and   so   when   you   copy   them   back,   you&#39;re   gonna   end   up   with   those   two   40   kills   42s   still   adjacent   to   each   other.
      </p>

        <cite>Bryce</cite>
      <time>2:56</time>
      <p>
          But   but   all   that   in   that   case   where   you   got   two   chunks,   and   the   first   chunk   has   its   last   value   is   42,   and   the   second   chunk   its   first   value   is   42.   Um   that   that   second   chunk,   that   second   chunk,   all   that   it   needs   to   know   is   what   was   the   last   value   of   that   first   chunk.   This   is   very   this   is   a   very   similar   property   to   what   you   what   chunks   need   to   know   when   you   do   a   scan.   And   so   if   you   can   just   it   it   heck   you   could   use   the   same   the   same   downsweep-up   sweep   technique   that   you   use   for   a   scan,   where   you   have   every   chunk   do   its   its   do   its   serial   unique   and   then   write   to   some   um   O   chunks   array   of   temporary   storage   how   much   what   it&#39;s   what   its   last   value   was,   and   then   um   then   you   have   another   parallel   pass   where   each   chunk   uh   looks   at   the   array   and   says,   hey,   what   was   the   last   value   of   my   of   my   um   predecessor   of   my   not   my   predecessor   of   the   chunk   before   me,   um   and   then   it   can   do   it   can   you   know   do   the   fix-up   that   it   needs   to,   that   if   if   that   last   element   was   the   same   as   the   first   element.   Um   uh   now   it   yeah   that   may   not   work   in   the   face   of   if   I   have   a   a   no,   I   think   that   I   think   it&#39;s   fine.   Even   if   even   if   I   had   like   chunk   one   that   ended   it   with   a   42,   chunk   two   is   all   42s,   and   chunk   three   um   starts   with   a   42.   In   that   case,   chunk   one   is   gonna   write   it&#39;ll   work,   yeah.   Yeah,   it&#39;ll   still   work.   So   that   that   that   I   think   is   a   workable   design.
      </p>

        <cite>Conor</cite>
      <time>4:39</time>
      <p>
          Yeah,   that&#39;s   uh   that&#39;s   a   lot.   Well,   a   lot.   It&#39;s   a   little   bit   trickier   though,   because   now   you&#39;re   basically   you   have   like   overlapping   tiles   or   chunks.
      </p>

        <cite>Bryce</cite>
      <time>4:49</time>
      <p>
          Yeah,   but   it   but   you   have   that   with   you   have   that   with   a   scan   too.
      </p>

        <cite>Conor</cite>
      <time>4:53</time>
      <p>
          Yeah,   but   a   scan   is   designed   to   work   that   way.   Um   yeah,   so   yes,   the   answer   is   yes.   You   can   avoid   your   final   unique   by   making   use   of   the   last   value   from   each   chunk   in   the   next   chunk.
      </p>

        <cite>Bryce</cite>
      <time>5:07</time>
      <p>
          And   I   and   I   suspect   that   that   uh   we   we&#39;ve   just   talked   about   that   using   the   design   of   the   the   simpler   two-pass   uh   uh   scan,   but   I   suspect   that   you   could   implement   um   that   algorithm   with   the   same   the   same   technique   that   that   we   use   for   the   single   pass   decoupled   look   back   scan   and   get   yourself   to   a   I   think   at   least   a   a   single   pass   unique   that   only   needs   O   number   of   chunks   temporary   storage   instead   of   ON   temporary   storage.   So   yeah,   I   think   that&#39;s   better.   So   you&#39;re   gonna   you&#39;re   gonna   go   implement   that   and   uh   send   me   a   PR   for   thrust?
      </p>

        <cite>Conor</cite>
      <time>5:46</time>
      <p>
          No. I&#39;m   busy.
      </p>

        <cite>Bryce</cite>
      <time>5:48</time>
      <p>
          Alright,   alright,   now   now   now   that   we   now   that   we&#39;ve   uh   now   that   we&#39;ve   bottomed   out   on   that,   we   can   we   can   do   a   proper   final   episode.
      </p>

        <cite>Conor</cite>
      <time>5:55</time>
      <p>
          Alright,   what   are   we   chatting   about   now?
      </p>

        <cite>Bryce</cite>
      <time>5:58</time>
      <p>
          I   don&#39;t   know.   You   got   any   topics?
      </p>

        <cite>Conor</cite>
      <time>6:02</time>
      <p>
          We   could   circle   back   140-something   episodes   depending   on   with   this   when   this   comes   out,   and   talk   about   our   favorite   algorithms   now   that   it&#39;s   been   two   and   a   half   years   later,   you   know?   Is   uh   our   favorite   algorithm   still   the   same?   Well,   what   was   our   what   were   our   answers   then?   Mine   was   out   of   product.   I   don&#39;t   know   if   you   remember.   I   think   yours   was   Transform   Reduce.
      </p>

        <cite>Bryce</cite>
      <time>6:27</time>
      <p>
          Yeah.
      </p>

        <cite>Conor</cite>
      <time>6:28</time>
      <p>
          Um   Although   you   might   have   chosen   something   different   because   you   always   say   transform   reduce.
      </p>

        <cite>Bryce</cite>
      <time>6:32</time>
      <p>
          Um   I   mean   I   I   think   today   I   would   simply   say   reduce   because   I   think   that   transform   reduce   is   just   a   simp   is   is   no   special   thing.   It&#39;s   just   uh   a   form   of   reduce,   a   spelling   of   reduce.   And   uh   and   and   I   mean   uh   but   uh   but   perhaps   I   would   say   scan   because   I   think   increasingly   on   these   most   recent   episodes   we&#39;ve   found   uh   we&#39;ve   found   scans   and   s   or   or   uh   okay,   I   I   do   know   what   my   answer   is   gonna   be.   My   answer   is   gonna   be   that   non-commutative   uh   reduced.   The   reduce   that   um   uh   does   not   require   your   operator   to   be   commutative.   Um   and   and   the   reason   that   I   like   that   one   so   much   is   that   it   does   a   reduction,   but   it   lets   you   um   uh   propagate   information   from   from   left   to   right,   um,   and   that   can   be   very,   very   powerful.   So   I   think   that   that&#39;s   that&#39;s   the   reduce   that   um   that   I   would   pick.   Um   and   yes,   you   may   pay   some   performance   penalty   for   using   that   reduce   instead   of   the   uh   the   the   commutative   reduce,   um,   but   uh   I   still   think   that   that&#39;s   the   if   I   if   I   only   had   one   algorithm   tool,   I   would   have   that   one.
      </p>

        <cite>Conor</cite>
      <time>7:46</time>
      <p>
          Lovely.   We   love   that   for   you.   Great   algorithm.
      </p>

        <cite>Bryce</cite>
      <time>7:50</time>
      <p>
          Um   why   don&#39;t   we   talk   why   don&#39;t   we   talk   more   about   data   structures   on   this   podcast?
      </p>

        <cite>Conor</cite>
      <time>7:55</time>
      <p>
          Yeah,   because   they&#39;re   boring.   Uh   yeah,   that&#39;s   an   inflammatory   statement,   but   um,   you   know,   it   there&#39;s   that   famous   quote,   but   it&#39;s   it&#39;s   something   like,   you   know,   100   functions   versus   one   data   structure   or   10   functions   that   work   on   10   data   structures.   Whereas   in   C   we   have   technically   a   hundred   functions   that   work   on   10   data   structures.   But   I   just   like   I   I   I   these   days   I   operate   in   array   land,   and   there&#39;s   really   only   one   data   structure,   and   that&#39;s   the   array,   the   multidimensional   array.   You   know   what?   Sometimes   you   need   a   hash   table,   but   we   got   those   two.   Cucko,   check   it   out,   link   in   the   description.   Parallelized   data   structures   if   you   need   a   hash   map   on   the   GPU.   You   know,   sometimes   you   need   stacks   and   cues,   but   like   you   can   implement   all   those   with   an   array.   It&#39;s   just   a   couple   extra   functions.   And   uh   yeah,   you   know,   I&#39;m   just   um   I   understand   that   there   are   certain   uh   uh   areas   that   require   certain   domains   that   require   fancy,   you   know,   probabilistic   uh   you   know   uh   what   do   they   call   it?   Hyperlog   and   stuff   like   that.   Very   interesting   stuff.   It&#39;s   just   not   uh   it&#39;s   not   what   I&#39;m   focused   on   right   now.   And   I   just   I   like   there&#39;s   nothing   really   I   I   find   it   less   tantalizing   for   my   brain   to   think   about   data   structures   versus   uh   it&#39;s   much   more   tantalizing   uh   to   think   about   algorithms   and   chunk   buys   and   the   missing   algorithms   and   stuff   like   that,   you   know.   We   love   chunk   buy,   we   love   outer   product,   we   love   zip   transform,   we   love   uh   inner   product   or   transform   reduce,   we   love   the   segmented   algorithms,   we   love   them   all   folks,   we   love   them   all.   And   uh   yeah.
      </p>

        <cite>Bryce</cite>
      <time>9:31</time>
      <p>
          I   I   would   I   would   also   posit   that   I   think   in   I   would   posit   that   algorithms   that   there   are   I   would   posit   that   data   structures   are   algorithms.   Um   and   that   that   you   know   when   you   think   about   like   what   a   data   structure   is,   it&#39;s   it&#39;s   like   you   know,   it&#39;s   some   state   and   maybe   some   set   of   invariants   and   then   like   operations   on   that   state.   And   when   we   talk   about   algorithms   here,   like   especially   when   we   talk   about   like   you   know,   reductions   or   or   scans,   like   we   often   talk   about   like   like   what   is   what   is   the   state   that   we   need   to   propagate,   what   is   the   information   that   we   need   to   propagate   um   between   you   know   like   like   with   our   uh   with   our   reduction   or   or   scan   operators.   Um   and   you   know,   sometimes   when   we   talk   about   um   algorithms   like   uh   we   we   we   talked   about   unique   and   uh   how   our   parallel   implementation   thrust   currently   needs   to   maintain   this   ON   temporary   storage,   um   like   that&#39;s   you   know   that&#39;s   state   too.   Um   and   so   you   know   I   think   that   at   the   end   of   the   day,   um   data   structures   are   really   just   persistent   algorithms,   perhaps.
      </p>

        <cite>Conor</cite>
      <time>10:43</time>
      <p>
          Yeah,   I   mean   that&#39;s   a   stretch.   That&#39;s   a   stretch,   but   I   see   what   you&#39;re   trying   to   say.   And   uh   I   remember   back   when   I   was   I   was   uh   actuary   trying   to   get   a   job   at   a   a   major   tech   company,   and   I   was   doing   all   these   lead   code   challenges   and   reading,   you   know,   cracking   the   code,   uh   CTCI,   whatever   it&#39;s   called,   uh   cracking   the   code   interview,   and   you&#39;re   reading   all   these   blogs   on   how   to   best   prepare,   and   like   there   was   this   uh   geez   Louise,   we&#39;ve   got   Mr.   Mazda   riding   right   up   on   me   tail.   We&#39;re   gonna   have   to   get   into   our   right   hand   lane   here.   And   uh   I   just   remember   there   was   this   like   big   uh   Onotation.com   that   uh   had   sort   of   all   these   different   data   structures   that   had   the   time   complexity   of   all   the   operations   that   came   with   these   data   structures,   and   I   just   think   that&#39;s   so   silly.   Like,   you   know   what,   folks?   You   know   what,   folks,   you&#39;re   hearing   it   here   first.   Here&#39;s   what   you   need   to   know   you   need   to   know   uh   your   list   in   in   uh   Python.   We&#39;re   gonna   stick   with   Python,   you   know.   You   need   to   know   your   list   in   Python,   aka   your   vector,   something   that&#39;s   dynamically   resizable,   you   can   append   to,   etc.   You   need   to   know   that.   That&#39;s   your   bread   and   butter.   Everyone&#39;s   rank   one   array,   your   vector,   whatever   you   want   to   call   it.   And   uh   after   that,   you   know,   you   really   don&#39;t   need   much.   You   need   a   hash   set,   you   need   a   hash   map.   Um,   maybe   you   need   some   ordered   uh   ordered   uh   collections.   You   know,   in   Python   you&#39;re   gonna   have   to   import   your   uh   I   believe   it&#39;s   called   the   sorted   collections   module.   In   C   it&#39;s   gonna   be   your   map   and   your   set,   which   is   very   confusing   because   you   know   we   should   have   we   should   have   called   them   ordered   map   and   ordered   set,   and   then   set   and   map   should   have   been   our   hash   containers.   But   you   know   what?   Naming&#39;s   hard.   And   I   really   honestly   think   that&#39;s   it,   you   know.   That&#39;s   uh   I   think   it   once   you&#39;ve   got   your   your   hash   set,   your   hash   map,   and   your   vector   or   your   list,   whatever   you&#39;re   gonna   call   it,   every   once   in   a   while   you   need   something   that&#39;s   sorted,   but   a   lot   of   times   you   don&#39;t   actually   need   that   sorted   container,   you   just   need   a   you   just   need   a   rank   one   array,   you   know,   vector   or   list,   and   then   you   can   just   sort   that   and   you&#39;re   good   to   go.   Um   and   you   know,   all   these   stacks   and   decks   and   cues,   and   yeah,   okay,   it&#39;s   good   to   know   them.   But   like,   are   you   actually   reaching   for   that   stuff?   And   I   know   there&#39;s   a   few   listeners   being   like,   I   used   a   cue   this   one   time,   I   used   a   stack   this   one   time,   but   like   I   think   95%   of   problems   and   stuff   are   solved   with   just,   you   know,   a   couple   hash   containers.   Uh   we&#39;re   going   this   way   because   we   gotta   pay.   And   uh   we&#39;re   gonna.
      </p>

        <cite>Bryce</cite>
      <time>13:19</time>
      <p>
          Ooh,   hopefully   they   take   a   card.   I   mean,   that   does   seem   to   be   an   image   of   a   credit   card.   Right?
      </p>

        <cite>Conor</cite>
      <time>13:25</time>
      <p>
          Uh   it   did   just   say   Visa,   so   we&#39;re   good   to   go.   We&#39;re   gonna   have   to   talk   to   someone.   Do   you   think   they   wanna   be   on   the   pod?
      </p>

        <cite>Bryce</cite>
      <time>13:30</time>
      <p>
          I   think   we   better   not   get   in   trouble   with   European   Victors.
      </p>

        <cite>Conor</cite>
      <time>13:34</time>
      <p>
          Alright   here,   folks,   we&#39;re   doing   it   live!   And   the   car   is   unhappy.   Because   it   thinks   we&#39;re   gonna   crash.
      </p>

        <cite>Bryce</cite>
      <time>13:41</time>
      <p>
          I   guess   we   don&#39;t   have   to   talk   to   somebody.
      </p>

        <cite>Conor</cite>
      <time>13:45</time>
      <p>
          Are   we   recording   still?
      </p>

        <cite>Bryce</cite>
      <time>13:47</time>
      <p>
          Uh   I   did   stop   the   recording   when   I   thought   that   this   was   going   to   be   a   uh   an   incident.   We   uh   managed   to   successfully   pay   the   uh   toll   on   the   Italian   highway.   It&#39;s   very   confusing   because   we   uh   put   the   ticket   in   before   we   selected   the   language,   and   so   all   the   instructions   were   in   Italian,   and   it   was   not   clear   where   to   put   the   credit   card   in   at   all.   Uh   apparently   you   put   it   in   the   same   place   as   the   ticket.
      </p>

        <cite>Conor</cite>
      <time>14:11</time>
      <p>
          Would   have   been   nice.   Would   have   been   nice   if   they   had   a   little   arrow   pointing.   They   had   just   had   visa   signs   everywhere   and   uh   looking   for   a   tap   and   uh   didn&#39;t   think   that   there   would   be   an   overloading   of   functions   for   that   little   ticket   slot. Yes.
      </p>

        <cite>Bryce</cite>
      <time>14:26</time>
      <p>
          Where   were   we   before   we   were   so   rudely   interrupted   by   the   highway?
      </p>

        <cite>Conor</cite>
      <time>14:29</time>
      <p>
          Uh   we   were   talking   about   data   structures.   Oh   right,   and   I   was   just   saying   your   you   got   your   list   in   Python,   your   set,   your   map.   And   they   don&#39;t   even   have   uh   sets.   Oh   no,   that&#39;s   true,   they   do   have   sets   in   Python.   There&#39;s   some   language   that   doesn&#39;t   have   uh   sets,   and   they   they   if   you   want   a   set,   you   just   use   a   valueless   hash   map,   which   I   don&#39;t   like   at   all.   I   don&#39;t   like   at   all.
      </p>

        <cite>Bryce</cite>
      <time>14:51</time>
      <p>
          Um   anyways   that   sort   of   seems   fine   to   me.   It   seems   like   a   s   uh   simpler   model   because   then   you   don&#39;t   you   don&#39;t   have   these   two   kinds   of   things.   Like,   like   just   to   make   a   set   a   special   case   of   a   map,   then   it&#39;s   one   less   thing   you   have   to   to   learn   and   worry   about.   And   then   like   all   of   your   code   that&#39;s   been   written   to   deal   with   maps   will   also   work   with   sets.   Um   that   kind   of   actually   seems   like   a   like   a   good   design   to   me.
      </p>

        <cite>Conor</cite>
      <time>15:17</time>
      <p>
          I   think   you&#39;re   completely   wrong.   If   you&#39;ve   got   no   sets   and   only   a   hash   map,   that   means   you&#39;ve   got   a   bunch   of   APIs   that   are   for   looking   up,   you   know,   values   and   stuff   like   that   that   just   have   no   meaning   because   there&#39;s   no   values   there,   and   it&#39;s   the   same   reason   that   you   know   you&#39;ve   got   the   aliases,   keys   and   values   on   the   C20   range   adapter   elements.   They,   you   know,   they   they&#39;re   they&#39;re   sure   it&#39;s   convenient,   but   it   can   be   confusing.   Um   so   we   don&#39;t   like   it.
      </p>

        <cite>Bryce</cite>
      <time>15:48</time>
      <p>
          Sure,   that   may   be   fair.   Anyways,   I   guess   uh   I   guess   that&#39;s   why   we   don&#39;t   like   talking   about   data   structures   that   much.   I   think   it   also   may   be   a   domain   thing.   It   may   be   just   that   because   we&#39;re   in   uh   compute   and   that   we   mostly   focus   on   the   design   of   parallel   algorithms,   we   are   um   we   just   spend   less   time   thinking   about   uh   data   structures   and   maybe   people   in   different   domains   or   working   in   different   types   of   applications   spend   more   time   thinking   about   it.
      </p>

        <cite>Conor</cite>
      <time>16:13</time>
      <p>
          Yep.   How   how   far?   We&#39;re   19   minutes   away   from   Venice,   folks.
      </p>

        <cite>Bryce</cite>
      <time>16:16</time>
      <p>
          Yeah,   nine   kilometers   until   the   part   where   I&#39;m   gonna   want   to   pay   attention   to   looking   at   Venice   and   not   talking   to   uh   talking   to   the   listener.
      </p>

        <cite>Conor</cite>
      <time>16:25</time>
      <p>
          Wow.   So   rude,   Bryce.   I   want   to   keep   talking   to   the   listener,   folks.
      </p>

        <cite>Bryce</cite>
      <time>16:29</time>
      <p>
          I   could   have   been   ruder.   I   I   could   have   said   I   want   to   pay   attention   to   looking   at   Venice   and   not   talking   to   you.
      </p>

        <cite>Conor</cite>
      <time>16:36</time>
      <p>
          That&#39;s   you   know,   I   think   it   was   more   offensive   when   you   insulted   the   listener,   not   me.   I&#39;m   used   to   it   after   four   days   uh   traveling   with   Bryce.   So   we&#39;re   now   gonna   talk   about   the   things,   the   superpowers,   the   hidden   gems   of   array   languages.   Specifically,   we&#39;re   gonna   focus   on   BQN,   but   a   lot   of   the   array   languages,   uh   J   and   APL,   have   these   features   too.   So   the   first   one,   the   first   one   is   invertible   functions.   Invertible   functions.   Think   about   this,   folks.   Think   about   this.   Say   one   of   my   favorite   functions   that   I   actually   or   algorithms   that   I   didn&#39;t   mention   that   I   think   I   was   gonna   mention   when   I   brought   up   talking   about   our   favorite   algorithms   was   an   algorithm   called   indices.   Sometimes   it&#39;s   called   where,   in   Q   it&#39;s   called   where.   And   in   APL,   I   believe   it&#39;s   called   WHERE,   but   in   J   and   BQN,   I   believe   it&#39;s   called   indices.   And   this   is   if   you&#39;re   given   a   Boolean   list,   a   list   of   ones   and   zeros,   aka   trues   and   falses,   it   returns   you   the   indices   corresponding   to   the   trues.   So   given   the   sequence   10101,   you   get   back   the   values   one,   three,   and   five.   Or   if   you&#39;re   in   BQN,   you   get   back   the   values   zero,   two,   and   four,   depending   on   whether   you&#39;re   a   one   indexed   language   or   a   zero   indexed.   I   prefer   one   indexed   array   languages,   uh,   or   I   just   I   prefer   that   language   choice.   Doesn&#39;t   mean   I   prefer   languages   that   do   that.   Anyways,   but   and   so   that   function   we&#39;ll   call   it   indices,   you   spell   it   differently   in   each   of   the   languages,   but   we&#39;ll   refer   to   it   colloquially   as   indices.   But   what   if   you   go   indices   inverse,   which   is   just   a   little   a   little   uh   equal   sign   in   the   top   right   hand   corner,   a   superscript   equal   sign   in   BQN,   and   it&#39;s   power   to   the   negative   one   in   um,   or   it&#39;s   like   it&#39;s   the   power   which   is   a   star   diurasis   negative   one   in   APL.   If   you   do   indices   inverse   and   you   give   it   the   sequence   one   three   five,   it&#39;ll   give   you   back   a   Boolean   mask   one   zero   one   zero   one.   Isn&#39;t   that   amazing?   That   is   pretty   cool.   Are   all   functions   invertible?   Not   all   functions,   but   a   lot   of   functions.   So   many   functions.
      </p>

        <cite>Bryce</cite>
      <time>18:53</time>
      <p>
          But   what   determines   whether   or   not   a   function   is   invertible?
      </p>

        <cite>Conor</cite>
      <time>18:55</time>
      <p>
          Whether   it   is   implemented.   And   that   is   that   is   a   bad   answer.   Well,   I   mean,   so   in   J,   they   actually   have   a   conjunction,   I   believe,   called   obverse,   where   you   can   actually   implement   your   inverse   of   a   function.   So   you   can   actually   do   that.   And   I   think   just   like   most   of   the   functions   have   it,   so   you   know,   plus   minus,   multiplies,   divides,   etc.   stuff   like   that.   But   uh,   yeah,   you   know,   if   it&#39;s   there,   it&#39;s   there.   And   it&#39;s   just   it&#39;s   friggin&#39;   awesome.   It&#39;s   friggin&#39;   awesome.   It&#39;s   frighten   what   language   can   you   do   that   in?   What   language?   The   answer   is   array   languages,   folks.
      </p>

        <cite>Bryce</cite>
      <time>19:31</time>
      <p>
          You   can&#39;t   do   it   in   any   other   language.   So,   but   but   I   want   to   go   back   to   my   question.   Like,   what   what   property   makes   a   function   invertible?   Surely   not   all   functions   are   invertible.   And   I   think   that   this   is   a   sort   of   a   mathematical   question.   Although   I   I   I   vaguely   recall   quot   discussing   functions   and   their   invertibility   in   my   uh   college   years,   but   I   don&#39;t   remember   any   of   the   details.
      </p>

        <cite>Conor</cite>
      <time>19:53</time>
      <p>
          Yeah,   I   mean   it&#39;s   sure.   It&#39;s   uh   I   mean   there&#39;s   mathematical   uh   stuff   behind   this,   you   know.   It&#39;s   it&#39;s   fine.   We   don&#39;t   need   to   chat   about   that.   The   point   is,   the   point   is   that   there   are   invertible   functions,   which   speaking   of   mathematical,   brings   us   to   the   second   awesome   thing.   This   is   no   particular   order,   folks.
      </p>

        <cite>Bryce</cite>
      <time>20:11</time>
      <p>
          Although   I   think   we   were   getting   pretty   close   to   where   we&#39;re   going   to.
      </p>

        <cite>Conor</cite>
      <time>20:20</time>
      <p>
          Uh   which   we&#39;re   not   there   yet.   So   the   second   uh   the   second   thing   is   under   structural   under.   This   is   similar   to   the   invertibility   of   functions.   So   say   you   want   to   do   a   reverse   scan,   a   write   scan   in   uh   an   array   language   like   BQN.   In   APL,   you   will   actually   have   to   sort   of   just   reverse   your   list,   then   perform   the   scan,   then   reverse   it   again.   J   actually   has   a   primitive   that   enables   you   to   do   it   whatever   direction   you   want,   but   in   BQN,   they&#39;ve   got   under,   which   is   one   circle   with   another   circle   around   it   for   the   symbol.   And   if   you   want   to   do   a   reverse   scan,   you   just   go   scan   under   reverse,   which   basically   means   it   will   apply   a   function,   then   perform   the   operation,   and   then   invert   perform   the   inverse   operation   of   that   function,   which   for   reverse   is   just   reverse.   So   that&#39;s   brilliant.   It&#39;s   so   it&#39;s   so   brilliant   because   there&#39;s   so   many   times.   How   many   times   have   you   been   doing   something   where   you   basically   like   another   example   is   when   you   are   dealing   with   characters,   but   you   want   to   do   some   operation   on   like   the   Unicode   values?   Um,   so   you   can   convert   it   to   like   an   integer,   do   some   kind   of   math,   and   then   convert   it   back   to   a   character   uh   with   you   know   probably   some   modulus   to   make   sure   it&#39;s   still   in   the   right   range.   It&#39;s   fantastic.   But   uh   you   can   do   that   with   uh   under.   You   can   convert   it   to   uh   going   here,   making   a   couple   I   think   so,   couple   a   couple   lane   changes   here,   folks.   Venezia,   that&#39;s   Italian   for   Venice.   And   uh,   anyways,   under   is   great,   uh   inverse   is   great,   and   what   else   is   great?   I   mean   combinators.   Combinators   are   fantastic.   We&#39;re   we&#39;ve   already   we&#39;ve   already   talked   about   combinators.   Go   check   it   out   though.   Check   out   the   B1   combinator,   check   out   the   B   combinator,   check   out   the   Phi   combinator,   check   out   the   Psi   combinator,   folks.   The   Psi   combinator,   it&#39;s   on   in   Haskell.   We   love   it.   You   got   a   unary   operation,   you   got   a   binary   operation,   and   two   arguments   in   coming,   you   apply   that   unary   operation   to   both   both   arguments   and   then   feed   it   to   the   binary   operation.   It&#39;s   super   useful   if   you&#39;re   doing   chunk   by&#39;s   and   Haskell,   that&#39;s   called   group   or   group   by.   And   like   imagine   you   want   to   group   by   some   property   of   the   list   of   things.   So   for   instance,   if   you   want   to   if   you   want   to   create   chunks   of   contiguous   odd   elements   and   contiguous   even   elements,   but   you&#39;re   given   a   list   of   integers.   Well,   what   you   want   to   chunk   on   is   the   value   of   applying   odd   or   even   to   each   of   your   integers   in   your   list.   So   because   you   because   chunk   by   or   group   by   though   takes   a   binary   predicate,   you   odd   is   a   unary   predicate.   So   what   you   want   to   do   is   you   want   to   do   uh   equal   is   your   binary   operation,   and   then   odd   or   even   as   your   unary   operation.   So   it&#39;s   it&#39;s   the   psi   combinator   with   uh   equality   and   uh   an   odd   or   even   function.   We   love   it,   we   love   it,   folks.   The   psi   combinator,   check   it   out.   The   d2   combinator   you   can   use   by   using   both   the   uh   I   believe   it&#39;s   the   sigma   and   delta   combinators   all   at   the   same   time.   We   love   it,   folks.   Check   out   BQN   for   combinators,   for   inverse,   for   under,   and   uh   for   ranked   polymorphism   as   well.   I   think   we   need   to   go.
      </p>

        <cite>Bryce</cite>
      <time>23:29</time>
      <p>
          Um   I   think   we&#39;re   gonna   uh   sign   off   here   for   now.   Yeah,   we   didn&#39;t   need   to   go   straight.   Yeah.   Alright,   we&#39;re   in   Venice,   folks!   We&#39;re   we&#39;re   about   to   get   on   the   bridge.   We   will   be   in   Venice   very   soon.   We   love   it.
      </p>

        <cite>Conor</cite>
      <time>23:42</time>
      <p>
          Be   sure   to   check   these   show   notes   either   in   your   podcast   app   or   at   adspthepodcast.com   for   links   to   any   of   the   things   we   mentioned   in   today&#39;s   episode,   as   well   as   a   GitHub   discussion   where   you   can   leave   questions   and   comments   on   the   thoughts.   Thanks   for   listening,   we   hope   you   enjoyed   and   have   a   great   day.
      </p>