Brain going crazy with recursive functions

[5lvqbwl02]

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)

 

[Arnaud Delobelle]

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 not sure what your code does but there is a canonical way to
transform a loop the call of a recursive function. I don't think I can
put it into words easily so I've demonstrated it
below on your 'locate_zero' function.

def find_zero(square):
"The normal imperative way in simple Python."
i = 0
for row in square:
j = 0
for n in row:
if n == 0:
return i, j
j += 1
i += 1

def func_find_zero(square):
"""
The translation into recursive calls. A function is created for
each loop. There are no mutations.
"""
def square_loop(square, i):
def row_loop(row, j):
if row:
if row[0] == 0:
return i, j
else:
return row_loop(row[1:], j+1)
if square:
res = row_loop(square[0], 0)
if res is not None:
return res
else:
return square_loop(square[1:], i+1)
return square_loop(square, 0)

I've intentionally made both function 'non-clever' to make the translation
process more apparent.

 

[Lie Ryan]

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, ()))