The Power of Recursion
The main ideas behind this chapter is:
- Learning to think with recursion (Divide and Concquer with Recursion)
- Often forgotten but prior to thinking functional one should be fluent with thinking with recursion. Most juniors and many seniors suffer with recursion
- The goal is to build a foundation
non recursive version of fibonacci
1 def fibs(n)
2 ff = []
3 a = b = 1
4 n.times { ff << a; a,b = b,a+b }
5 ff
6 end
Basic Algorithms
- Faculty, etc
Sometimes you need assistance
Alternative title: sometimes you need a helper function.
- Fibonacci is good example to learn about accumulators
- Learning to think with accumulators
examples
1 def fib_acc(count, a, b, r)
2 count == 0 ? r : fib(count-1, b, a+b, r << a)
3 end
4
5 def fib(count)
6 fib_acc(count, 1, 1, [])
7 end
8 fib(10) # => [1,1,2,3,5,...
Avoid utility functions with default argements
1 def fib(count, a = 1, b = 1 , r = [])
2 count == 0 ? r : fib(count-1, b, a+b, r << a)
3 end
4 fib(10) # => [1,1,2,3,5,...
- r is the accumulator
- count is the terminator
- a and b are the ‘variables’
Exercises
Sorting Algorithms
Sorting algorithms at a level of complexity. They remain very relevant from and educatinal point of view.
Key elements to address:
- Talk about sort stability
- Introduce Time and Space complexity
Merge sort
first explain the algorithm
some prelude stuff we need
1 class Array
2 # prepend a to the array
3 def >> a
4 self.unshift a
5 end
6 end
the identity function
1 id = ->(x) { x }
splitting an array in parts
1 split_in = ->(n, xs) { xs.each_slice( (xs.length+1)/n ).to_a }.curry
2 split_in_half = split_in.(2)
merge as a lambda, generalized
1 merge_by = ->(f, xs, ys) do
2
3 return xs if ys.empty?
4 return ys if xs.empty?
5
6 x, *xt = xs
7 y, *yt = ys
8
9 return merge_by.(f, xt, ys) >> x if f.(x) <= f.(y)
10 return merge_by.(f, xs, yt) >> y
11
12 end.curry
13 merge = merge_by.(id)
once we have merge, merge sort is trivial
1 msort = ->(xs) do
2
3 return xs if xs.length <= 1 # stopcondition
4
5 left, right = split_in_half.(xs)
6 merge.( msort.(left) , msort.(right) )
7
8 end
generalized version with derived specific version for default sort order
1 msort_by = ->(f, xs) do
2
3 return xs if xs.length <= 1 # stopcondition
4
5 left, right = split_in_half.(xs)
6 merge_by.( f, msort_by.(f, left) , msort_by.(f, right) )
7
8 end.curry
9 msort = msort_by.(id)
tests
1 msort.([])
2 msort.([4,3,2,1])
3 msort.([3,2,1])
4 msort.([9,4,2,3,1,3,5,9])
5 msort.([9,4,2,3,1,3,5,9,9,4,2,3,1,3,5,9])
Quick sort
Declarative Implementation (1)
# from https://gist.github.com/aspyct/3433278 def quicksort(array, from=0, to=nil)
1 if to == nil
2 # Sort the whole array, by default
3 to = array.count - 1
4 end
5
6 if from >= to
7 # Done sorting
8 return
9 end
10
11 # Take a pivot value, at the far left
12 pivot = array[from]
13
14 # Min and Max pointers
15 min = from
16 max = to
17
18 # Current free slot
19 free = min
20
21 while min < max
22 if free == min # Evaluate array[max]
23 if array[max] <= pivot # Smaller than pivot, must move
24 array[free] = array[max]
25 min += 1
26 free = max
27 else
28 max -= 1
29 end
30 elsif free == max # Evaluate array[min]
31 if array[min] >= pivot # Bigger than pivot, must move
32 array[free] = array[min]
33 max -= 1
34 free = min
35 else
36 min += 1
37 end
38 else
39 raise "Inconsistent state"
40 end
41 end
42
43 array[free] = pivot
44
45 quicksort array, from, free - 1
46 quicksort array, free + 1, to
end
Declarative Implementation (2)
# from http://opennfo.wordpress.com/2009/02/15/quicksort-in-ruby/ def quicksort(list, p, r) if p < r then q = partition(list, p, r) quicksort(list, p, q-1) quicksort(list, q+1, r) end end
def partition(list, p, r)
pivot = list[r]
i = p - 1
p.upto(r-1) do |j|
if list[j] <= pivot
i = i+1
list[i], list[j] = list[j],list[i]
end
end
list[i+1],list[r] = list[r],list[i+1]
return i + 1
end
Functional Variant
# functional version def qsort(list) return [] if list.size == 0 pivot, *xs = *list less, more = xs.partition { |y| y < pivot } qsort(less) + [pivot] + qsort(more) end
Exercises
Backtracking Algorithms
- 8 Queens
classic solution with basic recursion
1 module RecurseQueens
2 def self.unsafe ( i,j, a,b )
3 j == b || i == a || i+j == a+b || i-j == a-b
4 end
5 def self.safe (partial, n)
6 partial.each_with_index.map { |r,i| unsafe( n, partial.length, r, i) }.no\
7 ne?
8 end
9 def self.solve (m, partial = [], solutions = [])
10 if m == 0
11 solutions << partial
12 return solutions
13 else
14 (0..7).each { |n| solve(m-1, (partial + [n]), solutions) if safe(partial\
15 , n) }
16 return solutions
17 end
18 end
19 end
classic solution with a pure ruby list comprehension
1 module Queens
2 def self.unsafe ( i,j, a,b )
3 j == b || i == a || i+j == a+b || i-j == a-b
4 end
5 def self.safe (partial, n)
6 partial.each_with_index.map { |r,i| unsafe( n, partial.length, r, i) }.no\
7 ne?
8 end
9 def self.solve (m = 8)
10 return [[]] if m == 0
11 solve(m-1).map { |partial| (0..7).map { |r| partial + [r] if safe(partial,\
12 r) }.compact }.flatten(1)
13 end
14 end
15
16 pp Queens::solve.length
classic solution with using comprise list comprehensions
1 module Qns
2 def self.unsafe ( i,j, a,b )
3 j == b || i == a || i+j == a+b || i-j == a-b
4 end
5 def self.safe (partial, n)
6 partial.each_with_index.map { |r,i| unsafe( n, partial.length, r, i) }.no\
7 ne?
8 end
9 def self.solve (m = 8)
10 return [[]] if m == 0
11 listcomp(
12 partial: solve(m-1),
13 n: -> { (0..7).select { |i| Qns::safe(partial,i) } }
14 ) { partial + [n] }
15 end
16 end
17
18 pp Qns::solve.length
with ‘verstehen’ list comprehensions
1 module QnsV
2 def self.attacks ( i,j, a,b )
3 j == b || i == a || i+j == a+b || i-j == a-b
4 end
5 def self.safe (partial, n)
6 partial.each_with_index.map { |r,i| attacks( n, partial.length, r, i) }.n\
7 one?
8 end
9 def self.solve (m = 8)
10 return [[]] if m == 0 # stop condition
11 list { partial + [n] }.
12 for(:partial).in { QnsV::solve(m-1) }.
13 for(:n).in { 0..7 }.
14 if { QnsV::safe(partial, n) }.
15 comprehend
16 end
17 end
with lambda’s, defining some basics
1 unsafe = ->(i,j,a,b) { j == b || i == a || i+j == a+b || i-j == a-b }.curry
2 # first check is not really needed and can be removed
3
4 safe = ->(queens, n) do
5 unsafe_to = unsafe.(n,queens.length)
6 queens.each_with_index.map { |r,i| unsafe_to.(r,i) }.none?
7 end
pure ruby list comprehension
1 queens = ->(m) do
2 return [[]] if m == 0
3 queens.(m-1).map { |p| (0..7).map { |r| p + [r] if safe.(p, r) }.compact }.f\
4 latten(1)
5 end
with list comprehension
1 qs = ->(m) do
2 return [[]] if m == 0
3 listcomp( p: qs.(m-1), r: -> { (0..7).select { |r| safe.(p,r) } } ) { p + [\
4 r] }
5 end
with list comprehension (generalized version)
1 require 'comprise'
2
3 qns = ->(size, m = size) do
4 return [[]] if m == 0
5 listcomp(
6 partial: qns.(size, m-1),
7 n: -> { (0..(size-1)).select { |i| safe.(partial,i) } }
8 ) { partial + [n] }
9 end
with lazylist
1 require 'lazylist'
2
3 # lazy liss requires functions to be defined as constants
4 Lqns = ->(m) do
5 return [[]] if m == 0
6 list { partial + [n] }.where( partial: Lqns.(m-1), n: 0..7) { safe.(partial,\
7 n) }
8 end
- Horse Walk
- Sudoku Solver