Mutually-Recursive Functions

Discussion in 'Ruby' started by Revence Kalibwani, Jun 7, 2007.

  1. 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?

    Thanks.

    Revence
     
    Revence Kalibwani, Jun 7, 2007
    #1
    1. Advertising

  2. Revence Kalibwani

    Dan Zwell Guest

    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?
    >
    > Thanks.
    >
    > Revence
    >
    >


    Could you show us what you mean? I for one do not know what a mutually
    recursive function is.

    Dan
     
    Dan Zwell, Jun 7, 2007
    #2
    1. Advertising

  3. --------------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. :eek:)
    # 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. :eek:)
    # 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--
     
    Revence Kalibwani, Jun 7, 2007
    #3
  4. Revence Kalibwani

    Bruno Michel Guest

    For the even and odd example, it works if you remplace odd by my_odd in
    the my_even function, and even by my_even in the my_odd function. Like this:

    def my_even(x)
    x == 0 or my_odd(x - 1)
    end

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

    my_even(10) #=> true


    Hope this helps.

    --
    Bruno Michel
     
    Bruno Michel, Jun 7, 2007
    #4
  5. Bruno Michel wrote:
    > For the even and odd example, it works if you remplace odd by my_odd
    > in the my_even function, and even by my_even in the my_odd function.
    > Like this:
    >
    > def my_even(x)
    > x == 0 or my_odd(x - 1)
    > end
    >
    > def my_odd(x)
    > x != 0 and my_even(x - 1)
    > end
    >
    > my_even(10) #=> true
    >
    >
    > Hope this helps.
    >

    Yeah. Solved it. Lots of typos. That happens under stress. Thanks a lot,
    everyone. :)
     
    Revence Kalibwani, Jun 7, 2007
    #5
  6. Revence Kalibwani

    Jano Svitok Guest

    On 6/7/07, Revence Kalibwani <> wrote:
    > Bruno Michel wrote:
    > > For the even and odd example, it works if you remplace odd by my_odd
    > > in the my_even function, and even by my_even in the my_odd function.
    > > Like this:
    > >
    > > def my_even(x)
    > > x == 0 or my_odd(x - 1)
    > > end
    > >
    > > def my_odd(x)
    > > x != 0 and my_even(x - 1)
    > > end
    > >
    > > my_even(10) #=> true
    > >
    > >
    > > Hope this helps.
    > >

    > Yeah. Solved it. Lots of typos. That happens under stress. Thanks a lot,
    > everyone. :)


    For this very case, String#succ and String.succ! might be helpful
    ('A'.succ -> 'B', 'Z'.succ -> 'AA').
     
    Jano Svitok, Jun 7, 2007
    #6
  7. On 6/7/07, Revence Kalibwani <> wrote:
    >
    > # 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:
    >
    >
    >
    >


    I may be missing something, but..

    If you just want to do that then try something like this.

    arr = []
    ("a".."ff").each {|x| arr << x}
    p arr

    Harry


    --

    A Look into Japanese Ruby List in English
    http://www.kakueki.com/
     
    Harry Kakueki, Jun 7, 2007
    #7
  8. Revence Kalibwani

    Guest

    Hi --

    On Thu, 7 Jun 2007, Harry Kakueki wrote:

    > On 6/7/07, Revence Kalibwani <> wrote:
    >>
    >> # 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:
    >>
    >>
    >>
    >>

    >
    > I may be missing something, but..
    >
    > If you just want to do that then try something like this.
    >
    > arr = []
    > ("a".."ff").each {|x| arr << x}
    > p arr


    Work-saving tip for the day:

    p [*"a".."ff"]

    :)


    David

    --
    Q. What is THE Ruby book for Rails developers?
    A. RUBY FOR RAILS by David A. Black (http://www.manning.com/black)
    (See what readers are saying! http://www.rubypal.com/r4rrevs.pdf)
    Q. Where can I get Ruby/Rails on-site training, consulting, coaching?
    A. Ruby Power and Light, LLC (http://www.rubypal.com)
     
    , Jun 7, 2007
    #8
  9. On 6/7/07, <> wrote:
    > Hi --
    >
    > On Thu, 7 Jun 2007, Harry Kakueki wrote:
    >
    > >
    > > I may be missing something, but..
    > >
    > > If you just want to do that then try something like this.
    > >
    > > arr = []
    > > ("a".."ff").each {|x| arr << x}
    > > p arr

    >
    > Work-saving tip for the day:
    >
    > p [*"a".."ff"]
    >
    > :)
    >
    >
    > David
    >
    > --
    > Q. What is THE Ruby book for Rails developers?
    > A. RUBY FOR RAILS by David A. Black (http://www.manning.com/black)
    > (See what readers are saying! http://www.rubypal.com/r4rrevs.pdf)
    > Q. Where can I get Ruby/Rails on-site training, consulting, coaching?
    > A. Ruby Power and Light, LLC (http://www.rubypal.com)
    >
    >

    I was going to do this.

    p ("a".."ff").each {|x| p x}

    But I didn't want it to run off the screen.
    But you did the same thing in a better way.
    Thanks for the tip.

    Harry


    --

    A Look into Japanese Ruby List in English
    http://www.kakueki.com/
     
    Harry Kakueki, Jun 7, 2007
    #9
  10. On 6/7/07, Harry Kakueki <> wrote:
    > On 6/7/07, <> wrote:
    > >
    > > Work-saving tip for the day:
    > >
    > > p [*"a".."ff"]
    > >
    > > :)
    > >
    > >
    > > David
    > >
    > > --
    > > Q. What is THE Ruby book for Rails developers?
    > > A. RUBY FOR RAILS by David A. Black (http://www.manning.com/black)
    > > (See what readers are saying! http://www.rubypal.com/r4rrevs.pdf)
    > > Q. Where can I get Ruby/Rails on-site training, consulting, coaching?
    > > A. Ruby Power and Light, LLC (http://www.rubypal.com)
    > >
    > >

    > I was going to do this.
    >
    > p ("a".."ff").each {|x| p x}
    >
    > Harry
    >

    Oops.
    Don't need 2 p's.

    ("a".."ff").each {|x| p x}

    Harry


    --

    A Look into Japanese Ruby List in English
    http://www.kakueki.com/
     
    Harry Kakueki, Jun 7, 2007
    #10
  11. Revence Kalibwani

    ara.t.howard Guest

    On Jun 7, 2007, at 5:06 AM, wrote:

    > Hi --
    >
    > On Thu, 7 Jun 2007, Harry Kakueki wrote:
    >
    >> On 6/7/07, Revence Kalibwani <> wrote:
    >>> # 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:

    >>
    >> I may be missing something, but..
    >>
    >> If you just want to do that then try something like this.
    >>
    >> arr = []
    >> ("a".."ff").each {|x| arr << x}
    >> p arr

    >
    > Work-saving tip for the day:
    >
    > p [*"a".."ff"]
    >
    > :)
    >


    seems a bit perlish no?

    cfp:~ > cat a.rb
    p ('a' .. 'ff').to_a


    cfp:~ > ruby a.rb
    ["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",
    "aa", "ab", "ac", "ad", "ae", "af", "ag", "ah", "ai", "aj", "ak",
    "al", "am", "an", "ao", "ap", "aq", "ar", "as", "at", "au", "av",
    "aw", "ax", "ay", "az", "ba", "bb", "bc", "bd", "be", "bf", "bg",
    "bh", "bi", "bj", "bk", "bl", "bm", "bn", "bo", "bp", "bq", "br",
    "bs", "bt", "bu", "bv", "bw", "bx", "by", "bz", "ca", "cb", "cc",
    "cd", "ce", "cf", "cg", "ch", "ci", "cj", "ck", "cl", "cm", "cn",
    "co", "cp", "cq", "cr", "cs", "ct", "cu", "cv", "cw", "cx", "cy",
    "cz", "da", "db", "dc", "dd", "de", "df", "dg", "dh", "di", "dj",
    "dk", "dl", "dm", "dn", "do", "dp", "dq", "dr", "ds", "dt", "du",
    "dv", "dw", "dx", "dy", "dz", "ea", "eb", "ec", "ed", "ee", "ef",
    "eg", "eh", "ei", "ej", "ek", "el", "em", "en", "eo", "ep", "eq",
    "er", "es", "et", "eu", "ev", "ew", "ex", "ey", "ez", "fa", "fb",
    "fc", "fd", "fe", "ff"]

    ;-)


    -a
    --
    we can deny everything, except that we have the possibility of being
    better. simply reflect on that.
    h.h. the 14th dalai lama
     
    ara.t.howard, Jun 7, 2007
    #11
  12. Revence Kalibwani

    Guest

    Hi --

    On Thu, 7 Jun 2007, ara.t.howard wrote:

    >
    > On Jun 7, 2007, at 5:06 AM, wrote:
    >
    >> Hi --
    >>
    >> On Thu, 7 Jun 2007, Harry Kakueki wrote:
    >>
    >>> On 6/7/07, Revence Kalibwani <> wrote:
    >>>> # 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:
    >>>
    >>> I may be missing something, but..
    >>>
    >>> If you just want to do that then try something like this.
    >>>
    >>> arr = []
    >>> ("a".."ff").each {|x| arr << x}
    >>> p arr

    >>
    >> Work-saving tip for the day:
    >>
    >> p [*"a".."ff"]
    >>
    >> :)
    >>

    >
    > seems a bit perlish no?


    No, since you asked :) It looks like that thing in Ruby where you
    use the unar[r]ay operator to unarray a range :)


    David

    --
    Q. What is THE Ruby book for Rails developers?
    A. RUBY FOR RAILS by David A. Black (http://www.manning.com/black)
    (See what readers are saying! http://www.rubypal.com/r4rrevs.pdf)
    Q. Where can I get Ruby/Rails on-site training, consulting, coaching?
    A. Ruby Power and Light, LLC (http://www.rubypal.com)
     
    , Jun 7, 2007
    #12
  13. Revence Kalibwani

    vasudevram Guest


    >p [*"a".."ff"]


    David Black's solution above looks like the best for Ruby (hey, he
    wrote the Ruby for Rails book :)

    If Ruby didn't have that ability to enumerate from "a" to "ff" (I know
    it does), this one would also work (in Ruby as well as in other
    languages like Python, with suitable changes for their different
    syntax):

    labels = []
    ["a".."z"].each { |c| labels << c }
    ["a".."z"].each do |c|
    ["a".."z"].each { |c2| labels << (c + c2) }
    end
    # Now do whatever you want with the array 'labels'.]

    ( I'm not at my PC right now, so can't check if its quite right. )

    Vasudev Ram
    Dancing Bison Enterprises
    http://www.dancingbison.com
     
    vasudevram, Jun 7, 2007
    #13
  14. Revence Kalibwani

    bbiker Guest

    On Jun 7, 8:07 am, "Harry Kakueki" <> wrote:
    > On 6/7/07, Harry Kakueki <> wrote:
    >
    >
    >
    > > On 6/7/07, <> wrote:

    >
    > > > Work-saving tip for the day:

    >
    > > > p [*"a".."ff"]

    >
    > > > :)

    >
    > > > David

    >
    > > > --
    > > > Q. What is THE Ruby book for Rails developers?
    > > > A. RUBY FOR RAILS by David A. Black (http://www.manning.com/black)
    > > > (See what readers are saying! http://www.rubypal.com/r4rrevs.pdf)
    > > > Q. Where can I get Ruby/Rails on-site training, consulting, coaching?
    > > > A. Ruby Power and Light, LLC (http://www.rubypal.com)

    >
    > > I was going to do this.

    >
    > > p ("a".."ff").each {|x| p x}

    >
    > > Harry

    >
    > Oops.
    > Don't need 2 p's.
    >
    > ("a".."ff").each {|x| p x}
    >
    > Harry
    >
    > --
    >
    > A Look into Japanese Ruby List in Englishhttp://www.kakueki.com/- Hide quoted text -
    >
    > - Show quoted text -


    I am not exactly sure what the OP was trying to do .. except that it
    has to do with Columns in Excel. It does seems to me to be fairly
    complicated. If this off topic, please excuse.

    In Excel, columns may either have a numeric format or an alpha
    format. Columns range for 1 .. 255 (A .. IV). Since I do quite a bit
    of work using Excel from Ruby via WIN32OLE, I have written a couple of
    helper functions to convert a numeric column value to an alpha column
    value and vice versa. Note that alpha columns in Excel are all caps.

    Here they are, I hope that someone might find them useful.

    # method to convert from numeric column to alpha col
    # accepts numeric column 1 through 256
    # returns alpha column A through IV
    # returns empty string on invalid input
    def n2a_col(num_col)

    # verify that it in the range of 1 to 255
    return nil if num_col < 1 || num_col > 256

    mostSD = num_col / 26 # SD = Significant Digit
    leastSD = num_col % 26

    if leastSD == 0
    mostSD -= 1
    leastSD = 26
    end

    leastSA = ('A'[0] + leastSD - 1 ).chr
    mostSA = mostSD > 0 ? ('A'[0] + mostSD - 1).chr : ''

    mostSA + leastSA
    end

    # method to convert from alpha column to numeric col
    # accepts alpha column A through IV
    # returns numeric column 1 through 255
    # returns 0 on invalid input
    def a2n_col(alpha_col)
    # to uppercase
    alpha_col.upcase

    col_size = alpha_col.size

    case col_size
    when 1
    return 0 if alpha_col < 'A' || alpha_col > 'Z'
    return alpha_col[0] - 'A'[0] + 1
    when 2
    return 0 if alpha_col < 'AA' || alpha_col > 'IV'
    return (alpha_col[0] - 'A'[0] + 1) * 26 + alpha_col[1] - 'A'[0] + 1
    else
    return 0
    end
    end
     
    bbiker, Jun 7, 2007
    #14
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Niklas Matthies
    Replies:
    0
    Views:
    854
    Niklas Matthies
    Oct 24, 2006
  2. jeniffer

    Example of 2 mutually recursive functions

    jeniffer, Apr 13, 2006, in forum: C Programming
    Replies:
    6
    Views:
    330
  3. Peter Olcott
    Replies:
    4
    Views:
    348
    Markus Schoder
    Jun 4, 2006
  4. Marco
    Replies:
    4
    Views:
    331
  5. vamsi
    Replies:
    21
    Views:
    2,113
    Keith Thompson
    Mar 9, 2009
Loading...

Share This Page