# Binary Search Using Lambda

Greetings,

I've been playing around with various ways to write a function that does a binary search on an array of integers.
Below is one of my implementations. I'm wondering if it is possible to avoid passing the function to itself
in order to achieve the recursive call. While I'm defining the function's body, is there a special syntax to define
a recursive call to the function being defined?

I'm also interested in any feedback folks may have to offer regarding the below implementation.

Thanks,
Steven

# Attempts to locate "int" in "int_array"
# if "int" is found, this function will return
# the index of "int's" location. If "int" is not
# found, this function will return -1. This function
# assumes that "int_array" is already sorted in
# ascending order.

···

#
# Example: chop(3, [1, 2, 3, 4, 5]) #=> 2

def chop(int, int_array)
func = lambda { |low, high, int, int_array, f|
return -1 if high < low
mid = low + ((high-low) / 2)

if int < int_array[mid]
high = mid-1
elsif int > int_array[mid]
low = mid+1
else
return mid
end

f.call(low, high, int, int_array, f)
}

func.call(0, int_array.size-1, int, int_array, func)
end

You don't need one.

% cat recursion_diversion.rb
func = lambda do |x|
if x == 0
puts "Recursing"
func.call(1)
else
puts "Done"
end
end

func.call( 0 )

% ruby recursion_diversion.rb
Recursing
Done

···

On Sep 4, 2006, at 10:59 PM, Steven Hansen wrote:

Greetings,

I've been playing around with various ways to write a function that does a binary search on an array of integers.
Below is one of my implementations. I'm wondering if it is possible to avoid passing the function to itself
in order to achieve the recursive call.

Steven Hansen <runner@berkeley.edu> writes:

Greetings,

I've been playing around with various ways to write a function that
does a binary search on an array of integers.
Below is one of my implementations. I'm wondering if it is possible
to avoid passing the function to itself
in order to achieve the recursive call. While I'm defining the
function's body, is there a special syntax to define
a recursive call to the function being defined?

I'm also interested in any feedback folks may have to offer regarding
the below implementation.

Thanks,
Steven

# Attempts to locate "int" in "int_array"
# if "int" is found, this function will return
# the index of "int's" location. If "int" is not
# found, this function will return -1. This function
# assumes that "int_array" is already sorted in
# ascending order.
#
# Example: chop(3, [1, 2, 3, 4, 5]) #=> 2

def chop(int, int_array)
func = lambda { |low, high, int, int_array, f|
return -1 if high < low
mid = low + ((high-low) / 2)

if int < int_array[mid]
high = mid-1
elsif int > int_array[mid]
low = mid+1
else
return mid
end

f.call(low, high, int, int_array, f)
}

func.call(0, int_array.size-1, int, int_array, func)
end

I can't resist from using the Y combinator:

Y = lambda { |f|
g = lambda { |h|
lambda { |x|
f[h[h]][x]
}
}
g[g]
}

# untested
def chop(int, int_array)
Y.call(lambda { |func| lambda { |low, high, int, int_array|
return nil if high < low
mid = low + ((high-low) / 2)

if int < int_array[mid]
high = mid-1
elsif int > int_array[mid]
low = mid+1
else
return mid
end

func.call(low, high, int, int_array)
}}).call(0, int_array.size-1, int, int_array)
end

···

--
Christian Neukirchen <chneukirchen@gmail.com> http://chneukirchen.org

Cool, thanks Logan.

···

On Sep 4, 2006, at 8:09 PM, Logan Capaldo wrote:

On Sep 4, 2006, at 10:59 PM, Steven Hansen wrote:

Greetings,

I've been playing around with various ways to write a function that does a binary search on an array of integers.
Below is one of my implementations. I'm wondering if it is possible to avoid passing the function to itself
in order to achieve the recursive call.

You don't need one.

% cat recursion_diversion.rb
func = lambda do |x|
if x == 0
puts "Recursing"
func.call(1)
else
puts "Done"
end
end

func.call( 0 )

% ruby recursion_diversion.rb
Recursing
Done

Sweet! Y-Combinator in ruby. You do realize, now that you've done the "hard part" what this will do to advance the state of the art in ruby obfuscation?

···

On Sep 7, 2006, at 9:39 AM, Christian Neukirchen wrote:

I can't resist from using the Y combinator:

Y = lambda { |f|
g = lambda { |h|
lambda { |x|
f[h[h]][x]
}
}
g[g]
}

Logan Capaldo <logancapaldo@gmail.com> writes:

I can't resist from using the Y combinator:

Y = lambda { |f|
g = lambda { |h|
lambda { |x|
f[h[h]][x]
}
}
g[g]
}

Sweet! Y-Combinator in ruby. You do realize, now that you've done the
"hard part" what this will do to advance the state of the art in ruby
obfuscation?

*yawn*. BTDT:
-rw-rw-r-- 1 chris chris 222 Oct 25 2003 /Users/chris/projects/ruby/y.rb
-rw-rw-r-- 1 chris chris 285 Oct 25 2003 /Users/chris/projects/ruby/jarh2.rb

s=",GreEkcaSh BODybuILDER ALBreChtAMMOonIa tSUNEMATsuJ";
puts lambda{|f|h=lambda{|h|lambda{|x|f[h[h]][x]}};h[h]}[
lambda{|f|lambda do|h|h[0]?f[h[1..-1]]<<h[0]:[];end}][s.
delete(*%w{A-Z ^JR})].#See King James text of the bible:
pack("c*")## "Y do ye not understand my speech?", John 8

···

On Sep 7, 2006, at 9:39 AM, Christian Neukirchen wrote:

--
Christian Neukirchen <chneukirchen@gmail.com> http://chneukirchen.org