Brain going crazy with recursive functions

[James Stroud]

5lvqbwl02 at sneakemail.com wrote:
> I'm trying to solve the 9-tile puzzle using as functional an approach
> as possible.  I've recently finished reading SICP and am deliberately
> avoiding easy python-isms for the more convoluted scheme/functional
> methods.  The following function is trivial to do with for loops and
> directly accessing arrays with [] syntax.  I'm trying to limit myself
> to the types of idioms/semantics one finds in minimal scheme, such as
> in SICP.  I want eventually to port this to scheme, but I know python
> better, so that's where I'm starting.
> 
> My current problem is the following.  The 9-tile puzzle consists of a
> list of lists like this [[1,2,3],[4,5,6],[7,8,0]], where the numbers
> can be jumbled up.  I'm looking for the location of the zero using
> *only* recursion and operators that are similar to car/cdr.  The
> return value should be the row,col of the zero.  For example above the
> return value would be (2,2).
> 
> I'm also trying to define a single "linear_search(...)" function which
> does the search for within the row (an inner list above) and within
> the whole list.  linear_search takes as an argument a "truth_function"
> which does the actual work.  What's tricky is that the truth function
> for the array-as-a-whole is also the linear_search for a row.  Once
> I'm in linear_search for the array, I also call linear_search for each
> row.
> 
> The problem is the line where it says acc.insert(0,idx) looks fishy to
> me.  It works fine and returns the row,col of the location of the zero
> tile, but it seems to be mutating a variable, and that's the thing I'm
> trying to avoid.  In a sense, it's not hard enough and python is
> making this too easy :)  (although it took a bit of mind-wrenching to
> get to this point.  Recursion makes you either dumber or smarter, I'm
> not sure which).
> 
> How do I accumulate the inner value of the search so it pops out at
> the end, without resorting to a mutable variable?  I did a bit of
> search and the word "monad" came up, but I'm not sure what that is (I
> know it relates to haskell and some other purely functional stuff, but
> I get very lost when trying to read that stuff).
> 
> def linear_search(array, truth_func, acc):
> 	# Goes through each element of array and applies truth_func.
> 	# Returns index if found, otherwise returns None
> 	def linear_search_iter(idx, truth_func, arr, acc):
> 		if arr:
> 			tf = truth_func(arr[0])
> 			if tf or type(tf) is int:
> 				acc.insert(0,idx)
> 				return idx, acc+[idx]
> 			else:
> 				return linear_search_iter(idx+1, truth_func, arr[1:], acc)
> 	return linear_search_iter(0, truth_func, array, acc)
> 
> 
> 
> def locate_zero(p):
> 	# Locates empty tile.  Returns (r,c) tuple
> 	def find_zero_in_row(row):
> 		return linear_search(row, lambda x: x==0, acc)
> 
> 	acc = []
> 	ls = linear_search(p, find_zero_in_row, acc)
> 	print acc
> 	return acc

> thanks
> Michael

I am honestly getting lost in your code. The following fulfills your 
requirements as far as I can tell. It uses None as a sentinel for the 
truth function matching no elements of the array. Some assignments are 
made within the code simply to make it more readable. They are not 
necessary. The first element that the truth function evaluates to True 
is returned.

I hope it helps.

James

def linear_search(array, truth_func, loc=(0,0)):
   idx1, idx2 = loc
   if idx1 >= len(array):
     return None
   if idx2 >= len(array[idx1]):
     return linear_search(array, truth_func, (idx1+1, 0))
   value = array[idx1][idx2]
   tf = truth_func(value)
   if tf:
     return loc
   else:
     return linear_search(array, truth_func, (idx1, idx2+1))

a = [[5, 3, 4], [2, 0, 1], [8, 6, 7]]
linear_search(a, lambda x: x==0)