Functional Programming

Posts tagged with "Functional Programming."
  • 1

    MAR
    2012

    The Right Ruby Mix

    Ruby is a melting pot language. It borrows ideas from many things that came before. It combines several different programming philosophies.

    This aspect of the language can be a plus. It means that Ruby is suited to multiple applications. It also opens up some pragmatic shortcuts. Even better, it sometimes encourages us to think about problems using a different lens of thought.

    Of course, this cuts both ways. Ruby living at the intersection of many ideas does have some downsides. First, there's more to learn than you find with some simpler languages. There's a cost for the extra knowledge we have to track. Even worse though, in my opinion, is that it's sometimes hard to know exactly what Ruby's style really is.

    Going Off Script

    One culture Ruby borrowed heavily from is that of the so called "Scripting Languages." The main source of these features was Perl, in my opinion, but you can also find influences from Bash and other sources. I found this comforting since I came to Ruby from Perl, but the truth is that it bothers some people.

    Read more…

  • 22

    FEB
    2006

    Currying

    All the examples in this chapter are trivially translated (switch sub { ... } to lambda { ... }). Ironically, I have never seen a chunk of idiomatic Ruby do anything like this. Rubyists clearly favor blocks for this sort of work. Have a look at the stream addition and multiplication examples of this chapter, for example. You can also see this when MJD trying to create a suitable inject() for Perl (he calls it reduce/fold).

    Another interesting point about this chapter is how much of it is spent warring with Perl's syntax. MJD really struggles to introduce a block-like syntax for curried methods and is outright defeated in a couple of attempts. I really like how easily Ruby yields to our attempts to reprogram her, in sharp contrast to her sister language.

    Continuing that line of thought, here's my best effort at the Poor Man's Currying library:

    #!/usr/bin/env ruby -w
    
    class Proc
      def curry(&args_munger)
        lambda { |*args| call(*args_munger[args]) }
      end
    end
    
    class Object
      def curry(new_name, old_name, &args_munger)
        ([Class, Module].include?(self.class) ? self : self.class).class_eval do
          define_method(new_name) { |*args| send(old_name, *args_munger[args]) }
        end
      end
    end
    

    Read more…

  • 20

    FEB
    2006

    Infinite Streams

    I've tried to summarize this chapter a couple of times now, but I keep getting tripped up over syntax. So, let's talk about that…

    Functional Perl

    Obviously, the examples in the book can be more or less directly translated. Here's a sample from the first couple of pages:

    #!/usr/local/bin/ruby -w
    
    ### Stream Methods ###
    
    def node(head, tail)
      [head, tail]
    end
    
    def head(stream)
      stream.first
    end
    
    def tail(stream)
      tail = stream.last
      if tail.is_a?(Proc)
        tail.call
      else
        tail
      end
    end
    
    def drop(stream)
      head                 = head(stream)
      stream[0], stream[1] = Array(tail(stream))
      head
    end
    
    def show(stream, limit = nil)
      while head(stream) && (limit.nil? or (limit -= 1) > -1)
        print drop(stream), $, || " "
      end
      print $/
    end
    
    ### Examples ###
    
    def upto(from, to)
      return if from > to
      node(from, lambda { upto(from + 1, to) })
    end
    show(upto(3, 6))  # => 3 4 5 6
    
    def upfrom(start)
      node(start, lambda { upfrom(start + 1) })
    end
    show(upfrom(7), 10)  # => 7 8 9 10 11 12 13 14 15 16
    

    Read more…

  • 31

    JAN
    2006

    Iterators (Chapters 4 and 5)

    Due to a printing error, these two chapters actually came out longer than intended. Originally their contents were: "Use Ruby."

    All jokes aside, there's really not a whole lot for me to talk about from these chapters, since iterators are so internal to Ruby. Readers from our camp should run into a lot less surprises here that the intended audience. Just translate MDJ's anonymous subroutines to blocks, replace his returns with yields, and you are 90% of the way there.

    Here are translations for some of the examples in these chapters. I think these all come out cleaner and more natural in Ruby, but you be the judge:

    Permutations

    #!/usr/local/bin/ruby -w
    
    def permute(items)
      0.upto(1.0/0.0) do |count|
        pattern = count_to_pattern(count, items.size) or break
        puts "Pattern #{pattern.join(' ')}:" if $DEBUG
        yield(pattern_to_permutation(pattern, items.dup))
      end
    end
    
    def pattern_to_permutation(pattern, items)
      pattern.inject(Array.new) { |results, i| results + items.slice!(i, 1) }
    end
    
    def count_to_pattern(count, item_count)
      pattern = (1..item_count).inject(Array.new) do |pat, i|
        pat.unshift(count % i)
        count /= i
        pat
      end
      count.zero? ? pattern : nil
    end
    
    if ARGV.empty?
      abort "Usage:  #{File.basename($PROGRAM_NAME)} LIST_OF_ITEMS"
    end
    
    permute(ARGV) { |perm| puts(($DEBUG ? "  " : "") + perm.join(" ")) }
    

    Read more…

  • 20

    JAN
    2006

    Caching and Memoization

    I felt this chapter had a lot going for it, in places, but occasionally got lost in the details. All in all though, it's good stuff.

    Caching

    Obviously a powerful technique here and all of it translates to Ruby with little effort. Here's a direct translation of the RGB_to_CMYK() subroutine:

    #!/usr/local/bin/ruby -w
    
    $cache = Hash.new
    
    def rgb_to_cmyk(*rgb)
      return $cache[rgb] if $cache.include?(rgb)
      c, m, y     = rgb.map { |color| 255 - color }
      k           = [c, m, y].min
      $cache[rgb] = [c, m, y].map { |color| color - k } + [k]
    end
    
    unless ARGV.size == 3 && ARGV.all? { |n| n =~ /\A\d+\Z/ }
      abort "Usage:  #{File.basename($PROGRAM_NAME)} RED GREEN BLUE"
    end
    
    puts rgb_to_cmyk(*ARGV.map { |num| num.to_i }).join(", ")
    

    There are several interesting syntax differences in there. For example, I had to use a global variable for the $cache because Ruby methods don't have access to local variables. Another option would be to use a lambda(). These are probably good indicators that we would wrap this in an object and use instance variables normally.

    Read more…

  • 17

    JAN
    2006

    Dispatch Tables

    I think in Ruby we tend to do a lot of this kind of work with method_missing(). I told you, Functional OO Programming.

    Here's my attempt at something close to a direct translation of the RPN calculator example:

    #!/usr/local/bin/ruby -w
    
    $stack = Array.new
    
    def rpn(expression, operations_table)
      tokens = expression.split(" ")
      tokens.each do |token|
        type = token =~ /\A\d+\Z/ ? :number : nil
    
        operations_table[type || token][token]
      end
    
      $stack.pop
    end
    
    if ARGV.size == 2 && ARGV.first == "-i" && ARGV.last =~ /\A[-+*\/0-9 ]+\Z/
      require "pp"
    
      def ast_to_infix(ast)
        if ast.is_a?(Array)
          op, left, right = ast
          "(#{ast_to_infix(left)} #{op} #{ast_to_infix(right)})"
        else
          ast.to_s
        end
      end
    
      ast_table = Hash.new do |table, token|
        lambda { |op| s = $stack.pop; $stack << [op, $stack.pop, s] }
      end.merge(:number => lambda { |num| $stack << num.to_i })
    
      puts "AST:"
      pp(ast = rpn(ARGV.last, ast_table))
      puts "Infix:"
      pp ast_to_infix(ast)
    elsif ARGV.size == 1 && ARGV.first =~ /\A[-+*\/0-9 ]+\Z/
      calculation_table = Hash.new do |table, token|
        raise "Unknown token:  #{token}."
        end.merge(
          :number => lambda { |num| $stack << num.to_i },
          "+"     => lambda { $stack << $stack.pop + $stack.pop },
          "-"     => lambda { s = $stack.pop; $stack << $stack.pop - s },
          "*"     => lambda { $stack << $stack.pop * $stack.pop },
          "/"     => lambda { d = $stack.pop; $stack << $stack.pop / d }
        )
    
        puts rpn(ARGV.first, calculation_table)
    else
      puts "Usage:  #{File.basename($PROGRAM_NAME)} [-i] RPN_EXPRESSION"
    end
    

    Read more…

  • 17

    JAN
    2006

    Recursion and Callbacks

    I'm currently reading through Higher-Order Perl, by Mark Jason Dominus. (Yes, I read books about things other than Ruby.)

    So far, I'm enjoying the title quite a bit. It certainly has me thinking and the Perl in it is very clean and easy to understand. That helps me translate the concepts to my language of interest.

    I'll post some of my Ruby translations of the books example code here as I go along. Others familiar with the book might enjoy looking over them. Be warned, my comments might not make much sense to those who haven't read the book.

    Recursion

    The book starts with some very simple recursion examples trivially translated. Here's one for manually translating Integers to binary Strings (a long way to say str.to_i.to_s(2) in Ruby):

    #!/usr/local/bin/ruby -w
    
    def binary(number)
      return number.to_s if [0, 1].include?(number)
    
      k, b = number.divmod(2)
      binary(k) + b.to_s
    end
    
    unless !ARGV.empty? && ARGV.all? { |n| n =~ /\A\d+\Z/ }
      abort "Usage:  #{File.basename($PROGRAM_NAME)} DECIMAL_NUMBERS"
    end
    
    puts ARGV.map { |num| binary(num.to_i) }.join(" ")
    

    Read more…