From: Christian Neukirchen <chneukirchen@...>
Date: 2006-09-07T22:39:36+09:00
Subject: Re: Binary Search Using Lambda

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