Ruby functional programming

Learning functional programming using Ruby by solving the Ninety-Nine Prolog problems.

As I read a blogpost written by Gabriel, about solving the 22 of the Ninety-Nine Prolog problems, I thought this would be a good opportunity to improve my functional programming skills in Ruby (I will probably also try to solve some of these problems in either Erlang or Haskell to improve my knowledge of these languages as well). Gabriel also links to the Scala solutions if this is more your cup of tea.

So far I have solved almost all of the Working with Prolog lists problems, with the exception of problem 26 and problem 27. I just can’t wrap my head around how to solve these, not even on paper, and the solution given in Prolog doesn’t exactly help me. Solving these problems in Ruby turned out to be quite simple for most of the problems, close to cheating even for some, as all you need is built into Ruby. I have tried to use a functional style of programming for the solutions, but for some, for example problem 28, I didn’t manage.

For these first problems, I mainly use the Enumarable::inject, which combines the elements of enum by applying the block to an accumulator value (memo) and each element in turn. The hard part is mostly defining the data structure to use, without it, it will be impossible to even solve the problem in a functional fashion.

The following solutions can be downloaded here, with corresponding specs.

  # P01 - Find the last element of a list.
  # built in

  # P02 - Find the last but one element of a list.
  def second_to_last
    self[-2]
  end

  # P03 - Find the K'th element of a list.
  # Using Prolog's notion of lists starting with index 1.
  def kth(k)
    self[k - 1]
  end

  # P04 - Find the number of elements of a list.
  # built in

  # P05 - Reverse a list.
  # built in

  # P06 - Find out whether a list is a palindrome.
  def palindrome?
    self == self.reverse
  end

  # P07 - Flatten a nested list structure.
  # built in

  # P08 - Eliminate consecutive duplicates of list elements.
  def eliminate_consecutive_duplicates
    self.inject([]) do |array, current| 
        array << current unless array[-1] == current
        array
    end
  end

  # P09 - Pack consecutive duplicates of list elements into sublists.
  def pack_consecutive_duplicates
    self.inject([[]]) do |array, current|
        if array[-1][-1] == current or array[-1][-1].nil?
            array[-1] << current
        else
            array << [current]
        end
        array
    end
  end

  # P10 - Run-length encoding of a list.
  def run_length_encode
    self.pack_consecutive_duplicates.inject([]) do |array, current|
        array << [current.size, current[0]]
        array  
    end
  end

  # P11 - Modified run-length encoding.
  def modified_run_length_encode
    self.run_length_encode.inject([]) do |array, current|
        array << current if current[0] > 1
        array << current[-1] if current[0] == 1
        array
    end
  end

  # P12 - Decode a run-length encoded list.
  def decode_modified_run_length_encoded
    self.inject([]) do |array, current|
        if current.kind_of? Array
          array << [current[-1]] * current[0]
        else
          array << current
        end
        array
    end.flatten
  end

  # P13 - Run-length encoding of a list (direct solution).
  def direct_run_length_encode
    self.inject([[0, nil]]) do |array, current|
      if array[-1][-1] == current or array[-1][-1].nil?
          array[-1][-1] = current
          array[-1][0] += 1 
      else
          array[-1] = array[-1][-1] if array[-1][0] == 1
          array << [1, current]
      end
      array
    end
  end

  # P14 & P15 - Duplicate the elements of a list n times, 2 by default.
  def duplicate_elements(n = 2)
    self.inject([]) do |array, current|
      array << [current] * n
      array
    end.flatten
  end  

  # P16 (**) Drop every N'th element from a list.
  def drop_every_nth(n)
    self.inject([[]]) do |array, current|
      if array[-1].size == n
        array << [current]
      else
        array[-1] << current
      end
      array
    end.inject([]) do |array, list|
      list.pop if list.size == n
      array << list
    end.flatten
  end

  # P17 (*) Split a list into two parts; the length of the first part is given.
  def split_in_two(split)
    [self[0...split], self[split..-1]]
  end

  # P18 (**) Extract a slice from a list.
  # built in

  # P19 (**) Rotate a list N places to the left.
  def rotate(n)
    self[n..-1].concat(self[0...n])
  end

  # P20 (*) Remove the K'th element from a list.
  # built in

  # P21 (*) Insert an element at a given position into a list.
  # built in

  # P22 (*) Create a list containing all integers within a given range.
  # built in

  # P23 (**) Extract a given number of randomly selected elements from a list.
  def randomly_select(n)    
    list = []
    n.times do
      list << self[rand * size]
    end
    list
  end

  # P24 (*) Lotto: Draw N different random numbers from the set 1..M.
  def randomly_select_different(n)
    old_self = self
    list = []
    n.times do
      list << old_self.delete_at(rand * size)
    end
    list
  end

  # P25 (*) Generate a random permutation of the elements of a list.
  def randomize
    randomly_select_different(self.size)
  end

  # P26 (**) Generate the combinations of K distinct objects chosen from the N elements of a list

  # P27 (**) Group the elements of a set into disjoint subsets.

  # P28 (**) Sorting a list of lists according to length of sublists
  # a
  def sort_sublists_by_length
    sort_by { |array| array.size }
  end

  # b
  def sort_sublists_by_length_frequency
    length_frequency = {}

    each do |sublist|
      length_frequency[sublist.size] ||= 0
      length_frequency[sublist.size] += 1
    end 

    sort_by { |array| length_frequency[array.size]}
  end