Ruby functional programming

04 May 2009

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.
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]
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 > 1
array << current[-1] if current == 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
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] += 1
else
array[-1] = array[-1][-1] if array[-1] == 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
# HELP NEEDED

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

# 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