lambdaway :: even

lambdaway :: even_odd

6 | list | login |load

| |

_h1 even & odd

_p The standard way to compute {b even} and {b odd} is using the {b %} operator

{pre
'{def even 
 {lambda {:n}
  {= {% :n 2} 0}}}
-> {def even 
 {lambda {:n}
  {= {% :n 2} 0}}}

'{def odd 
 {lambda {:n}
  {= {% :n 2} 1}}}
-> {def odd 
 {lambda {:n}
  {= {% :n 2} 1}}}

'{even 123} -> {even 123}
'{even 124} -> {even 124}
'{odd 123} -> {odd 123}
'{odd 124} -> {odd 124}
}

_p Another way is to use [{b *, /, round}]

{pre
'{def even5
 {lambda {:n}
  {= {* {round {/ :n 2}} 2} :n}}}
-> {def even5
 {lambda {:n}
  {= {* {round {/ :n 2}} 2} :n}}}

'{even5 123} -> {even5 123}
'{even5 124} -> {even5 124}

'{even5 123456789} -> {even5 123456789}
'{even5 1234567890} -> {even5 1234567890}

but it deosn't work for big numbers

'{even5 1234567890123456789} -> {even5 1234567890123456789}
'{even5 12345678901234567890} -> {even5 12345678901234567890}
}

_p Using two mutually recursive functions we can use nothing but {b -} and {b =}.

{pre
'{def even1
 {lambda {:n}
  {if {= :n 0}
   then true 
   else {odd1 {- :n 1}}}}}
-> {def even1
 {lambda {:n}
  {if {= :n 0}
   then true 
   else {odd1 {- :n 1}}}}}

'{def odd1
 {lambda {:n}
  {if {= :n 0} 
   then false 
   else {even1 {- :n 1}}}}}
-> {def odd1
 {lambda {:n}
  {if {= :n 0} 
   then false 
   else {even1 {- :n 1}}}}}

'{even1 123} -> {even1 123}
'{even1 124} -> {even1 124}
'{odd1 123} -> {odd1 123}
'{odd1 124} -> {odd1 124}
}

_p It's a bad and slow algorithm, '{even4 1234} rises a stack overflow. Let's replace the mutally recursivity by double recursivity.

{pre
'{def even2
 {lambda {:n}
  {if {= :n 0}
   then true 
   else {{lambda {:n}
         {if {= :n 0} 
          then false 
          else {even2 {- :n 1}}}}
                     {- :n 1}}}}} 
-> {def even2
 {lambda {:n}
  {if {= :n 0}
   then true 
   else {{lambda {:n}
         {if {= :n 0} 
          then false 
          else {even2 {- :n 1}}}}
                     {- :n 1}}}}}

'{even2 123} -> {even2 123}
'{even2 124} -> {even2 124}
}

_p We build an "almost-recursive" equivalent function which will be used twice.

{pre
'{def even3
 {lambda {:f :n}
  {if {= :n 0}
   then true 
   else {{lambda {:f :n}
         {if {= :n 0} 
          then false 
          else {:f :f {- :n 1}}}} 
                   :f {- :n 1}}}}} 
-> {def even3
 {lambda {:f :n}
  {if {= :n 0}
   then true 
   else {{lambda {:f :n}
         {if {= :n 0} 
          then false 
          else {:f :f {- :n 1}}}} 
                   :f {- :n 1}}}}}

'{even3 even3 123} -> {even3 even3 123}
'{even3 even3 124} -> {even3 even3 124}
}

_p Finally we introduce the Ω-combinator {b '{lambda {:f} {:f :f}}}

{pre
'{{{lambda {:f} {:f :f}} even3} 123} -> {{{lambda {:f} {:f :f}} even3} 123}
'{{{lambda {:f} {:f :f}} even3} 124} -> {{{lambda {:f} {:f :f}} even3} 124}

'{def even4
 {lambda {:n}
  {{{lambda {:f} {:f :f}} 
   {lambda {:f :n}
    {if {= :n 0}
     then true 
     else {{lambda {:f :n}
            {if {= :n 0} 
             then false 
             else {:f :f {- :n 1}}}} 
                      :f {- :n 1}}}}} :n}}}
-> {def even4
 {lambda {:n}
  {{{lambda {:f} {:f :f}} 
   {lambda {:f :n}
    {if {= :n 0}
     then true 
     else {{lambda {:f :n}
            {if {= :n 0} 
             then false 
             else {:f :f {- :n 1}}}} 
                      :f {- :n 1}}}}} :n}}}

'{even4 123}
-> {even4 123}
'{even4 124}
-> {even4 124}
}

_p The last way will always work and is fast, using the {b W.last} lambdatalk primitive which is O(1).

{pre
'{def even6
 {lambda {:n}
  {= {W.last :n} 0}}}
-> {def even6
 {lambda {:n}
  {= {W.last :n} 0}}}

'{even6 12345678901234567891234567890123456789} -> {even6 12345678901234567891234567890123456789}
'{even6 1234567890123456789012345678901234567890} -> {even6 1234567890123456789012345678901234567890}
}

_p Probably better than using bitshifts.

_h2 refs

_ul [[even-odd|https://www.geeksforgeeks.org/3-ways-check-number-odd-even-without-using-modulus-operator-set-2-can-merge-httpswww-geeksforgeeks-orgcheck-whether-given-number-even-odd/]]
_ul ...