Brain going crazy with recursive functions

[Lie Ryan]

On Sat, 06 Dec 2008 23:33:35 -0800, 5lvqbwl02 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
> 
> locate_zero([[5, 3, 4], [2, 0, 1], [8, 6, 7]]) correctly returns (1,1)

In most functional languages, their natural data types differs. For 
example, Haskell's list is a linked list, which if expressed in python 
would look like this:

Python: [1, 2, 3, 4, 5]
Haskell-in-Python: [1, [2, [3, [4, [5, []]]]]]

linked list is more natural to use with recursive functions, so your 
locate zero would be like this:

def search_tile(row, depth = 0):
    head, tail = row
    if head == 0: 
        return depth
    elif len(tail) == 0:
        return None
    else:
        return search_tile(tail, depth + 1)

def search_row(grid, depth = 0):
    head, tail = grid
    st = search_tile(head)
    if st is not None:
        return depth, st
    elif tail == []:
        return None
    else:
        return search_row(tail, depth + 1)

Now, you noticed that lots of the code is similar, we want to generalize 
it. It's easy:

def search_linear(list_, checker, depth = 0):
    head, tail = list_
    if checker(head):
        return depth, () if checker(head) is True else checker(head)
        # I intentionally doesn't factor out checker(head)
        # as most functional language would automatically
        # do so because side-effect is impossible
    elif tail == ():
        return ()
    else:
        return search_linear(tail, checker, depth + 1)

data = (1, (2, (3, (0, ()))))
print search_linear(data, lambda x: x == 0)
# (3, ())

data = (0, (2, (3, (4, ()))))
print search_linear(data, lambda x: x == 0)
#(0, ())

data = (1, (2, (3, (4, ()))))
print search_linear(data, lambda x: x == 0)
#()

data = ((5, (3, (4, ()))), ((2, (0, (1, ()))), ((8, (6, (7, ()))), ())))
print search_linear(data, lambda row: search_linear(row, lambda tile: 
tile == 0))
#(1, (1, ()))