From: Revence Kalibwani <revence27@...>
Date: 2007-06-07T19:03:05+09:00
Subject: Re: Mutually-Recursive Functions

--------------080502090604050007040806
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

Dan Zwell wrote:
> Revence Kalibwani wrote:
>> Ruby doesn't seem to do mutually-recursive functions. Or is it some 
>> particular idiom I know not about? I am using an array to implement 
>> them, and it stinks a bit. Any way to do it?
>>
>
> Could you show us what you mean? I for one do not know what a mutually 
> recursive function is.
I have written it all out. Now, since I'm fresh to this list, I dunno if 
attachments show. Indulge me, please. I'll paste all the code (it's a 
bit literate') and also attach it (as mutrec.rb). :-)
By the way, ruby -v is: 1.8.5

#!	/usr/bin/ruby
#	Two examples of a mutually-recursive function.

#	These are functions that depend on each other - recursively.

#	even and odd:
#	If a number is zero, then it is even. Otherwise, it is even if the one before it is odd.
#	A number is odd if it is not zero. Otherwise, it is odd if it the one before it is even. :o)
#	This is the canonical example.
def my_even(x)
	x == 0 or odd(x - 1)
end

def my_odd(x)
	x != 0 and even(x - 1)
end

#	That is, of course, a silly way to implemet even and odd. So, let me give you the problem
#	I was trying to solve.
#
#	To generate the lettering similar to that above the spreadsheet columns, where the first
#	column has 'A', the second 'B' ... the twenty-sixth 'Z'. Then, the twenty-seventh has
#	'AA', the twenty-eight has 'AB', and so on. This is recursive by nature. Here is what
#	should work:


Letters = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J',
		   'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T',
		   'U', 'V', 'W', 'X', 'Y', 'Z']

def alphabetise(pos)
	pile_letters(0, pos)	#	LABEL: 1
end
def pile_chars(thus_far, pos)
	len = Letters.length
	if pos < len then
		Letters[pos]
	else
		alphabeticise(thus_far) + pile_chars(thus_far + 1, pos - len)
	end
	
end

#	Labels:
#	1.	That's where it fails. I guess 'tis because the scope is searched backwards
#		from that point.
#		OCaml, for example, requires me to put the `and' keyword between mutually-recursive 
#		functions. I'd not mind doing that in Ruby, but I don't know how. n00b. ;-)
#		Also, it works in That Other Language.
#

#	Now, the (dirty) solution I found. I think you will help me with how to get it done
#	without all this voodoo:

Funcs = [lambda do |pos|
			Funcs[1].call(0, pos)
		end,
		lambda do |thus_far, pos|
			len = Letters.length
			if pos < len then
				Letters[pos]
			else
				Funcs[0].call(thus_far) + Funcs[1].call(thus_far + 1, pos - len)
			end
		end]

def main(args)
	puts Funcs[0].call((26 * 26) - 1)	#	Prints A to Z. But see how un-Rubyistic it is!
	#	puts alphabetise(675)			#	This fails.
	#	if my_even 4 and my_odd 5 then 0 else 1 end		#	This also fails
	0
end

exit(main(ARGV))



--------------080502090604050007040806
Content-Type: text/plain;
 name="mutrec.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
 filename="mutrec.rb"

#!	/usr/bin/ruby
#	Two examples of a mutually-recursive function.

#	These are functions that depend on each other - recursively.

#	even and odd:
#	If a number is zero, then it is even. Otherwise, it is even if the one before it is odd.
#	A number is odd if it is not zero. Otherwise, it is odd if it the one before it is even. :o)
#	This is the canonical example.
def my_even(x)
	x == 0 or odd(x - 1)
end

def my_odd(x)
	x != 0 and even(x - 1)
end

#	That is, of course, a silly way to implemet even and odd. So, let me give you the problem
#	I was trying to solve.
#
#	To generate the lettering similar to that above the spreadsheet columns, where the first
#	column has 'A', the second 'B' ... the twenty-sixth 'Z'. Then, the twenty-seventh has
#	'AA', the twenty-eight has 'AB', and so on. This is recursive by nature. Here is what
#	should work:


Letters = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J',
		   'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T',
		   'U', 'V', 'W', 'X', 'Y', 'Z']

def alphabetise(pos)
	pile_letters(0, pos)	#	LABEL: 1
end
def pile_chars(thus_far, pos)
	len = Letters.length
	if pos < len then
		Letters[pos]
	else
		alphabeticise(thus_far) + pile_chars(thus_far + 1, pos - len)
	end
	
end

#	Labels:
#	1.	That's where it fails. I guess 'tis because the scope is searched backwards
#		from that point.
#		OCaml, for example, requires me to put the `and' keyword between mutually-recursive 
#		functions. I'd not mind doing that in Ruby, but I don't know how. n00b. ;-)
#		Also, it works in That Other Language.
#

#	Now, the (dirty) solution I found. I think you will help me with how to get it done
#	without all this voodoo:

Funcs = [lambda do |pos|
			Funcs[1].call(0, pos)
		end,
		lambda do |thus_far, pos|
			len = Letters.length
			if pos < len then
				Letters[pos]
			else
				Funcs[0].call(thus_far) + Funcs[1].call(thus_far + 1, pos - len)
			end
		end]

def main(args)
	puts Funcs[0].call((26 * 26) - 1)	#	Prints A to Z. But see how un-Rubyistic it is!
	#	puts alphabetise(675)			#	This fails.
	#	if my_even 4 and my_odd 5 then 0 else 1 end		#	This also fails
	0
end

exit(main(ARGV))

--------------080502090604050007040806--