{λ way

user:anonymous

_h1 binary search
_p Following [[https://rosettacode.org/wiki/Binary_search|https://rosettacode.org/wiki/Binary_search]]. This is the SCHEME code:

{pre

(define (binary-search value vector)
  (let helper ((low 0)
               (high (- (vector-length vector) 1)))
    (if (< high low)
        #f
        (let ((middle (quotient (+ low high) 2)))
          (cond ((> (vector-ref vector middle) value)
                 (helper low (- middle 1)))
                ((< (vector-ref vector middle) value)
                 (helper (+ middle 1) high))
                (else middle))))))

}

_p This is the '{lambda talk} code:

{pre
'{def BS 
   {def BS.rec
     {lambda {:a :v :i0 :i1}
       {let { {:a :a} {:v :v} {:i0 :i0} {:i1 :i1}
              {:m {floor {* {+ :i0 :i1} 0.5}}} } 
         {if {< :i1 :i0}
          then :v is not found
          else {if {> {array.item :a :m} :v}
          then {BS.rec :a :v :i0 {- :m 1} }
          else {if {< {array.item :a :m} :v}
          then {BS.rec :a :v {+ :m 1} :i1 }
          else :v is at array[:m] }}}}} }
   {lambda {:a :v}
     {BS.rec :a :v 0 {- {array.length :a} 1}} }} 
-> {def BS 
 {def BS.r {lambda {:a :v :i0 :i1}
  {let { {:a :a} {:v :v} {:i0 :i0} {:i1 :i1}
         {:m {floor {* {+ :i0 :i1} 0.5}}} } 
  {if {< :i1 :i0}
   then :v is not found
   else {if {> {array.item :a :m} :v}
   then {BS.r :a :v :i0 {- :m 1} }
   else {if {< {array.item :a :m} :v}
   then {BS.r :a :v {+ :m 1} :i1 }
   else :v is at array[:m] }}}}} }
 {lambda {:a :v}
  {BS.r :a :v 0 {- {array.length :a} 1}} }}
}

_p {b Note:} The {code let} special form is a syntaxic sugar for the call to an inner {code lambda}, see [[let]]. Because a {code lambda} doesn't create a closure, outer function's arguments must be duplicated/redefined in the {code let}'s arguments, hence {code '{:a :a} '{:v :v} '{:i0 :i0} '{:i1 :i1}}.

_p Testing:

{pre {@ style="word-wrap: break-word; white-space:pre-wrap;"}
'{def A {array 12 14 16 18 20 22 25 27 30}}
-> {def A {array 12 14 16 18 20 22 25 27 30}} = {A}

'{BS {A} -1}  -> {BS {A} -1}
'{BS {A} 24}  -> {BS {A} 24}
'{BS {A} 25}  -> {BS {A} 25}
'{BS {A} 123} -> {BS {A} 123}

'{def B {array {serie 1 100000 2}}} 
-> {def B {array {serie 1 100000 2}}} = [1,3,5,... 99997,99999]  // ~ 50,000 terms

'{BS {B} 100}   -> {BS {B} 100}
'{BS {B} 12345} -> {BS {B} 12345}
}

_p About speed (on a MacBook Pro 2 GHz Intel core i7 - 8 Go 1600 MHz DDR3):
_ul in the previous '{lambda talk}{sup 1} version : {b 9100ms} 
_ul in the current '{lambda talk}{sup 2} version : {b 32ms}, a gain of {b x300}!

_p Added in [[Rosetta|https://rosettacode.org/wiki/Binary_search#Lambdatalk]].