用函数式编程来测试驱动出Prime Factor题目

近年来，函数式编程Funtional Programming大行其道，成为业界的热门话题。2016年端午节期间，我给中国软件匠艺小组的小伙伴们出了一道题目：用TDD的方式驱动出函数式编程版本的”Prime Factor”，不料各路神仙各显神通，争奇斗艳。

“Prime Factor”题目

这是一道经典的TDD题目：对给定的正整数N，求出其所有质因数，经典算法可以通过TDD驱动出二重循环，如下：

1
2
3
4
5
6
7
8
9
10
def calc(i):
	result = []
	for candidate in xrange(2,i):
		while i % candidate == 0 and i > candidate:
			result.append(candidate)
			i /= candidate
	result.append(i)
	return result

assert [2,2,2,3,3] == calc(72)

下面按照交作业的顺序展示一下大家的作品。然而TDD是一个推导的过程，仅仅看最终结果是不够的，能看到中间的状态就更好了。

Ronald麦大仙的Python版本

1
2
3
4
5
6
7
8
def factors_from(i, xs):
    first = [x for x in xs if i % x == 0][0]
    return [first] + factors(i / first)

def factors(i):
    return [] if i < 2 else factors_from(i, xrange(2, i+1)) 
    
assert factors(3*7*11*13) == [3,7,11,13]

梁辰的Ruby版本

TDD过程存储于http://cyber-dojo.org/kata/edit/9B0ED5F482?avatar=lion

1
2
3
4
5
6
7
8
9
def first_divisible_factor start_factor, number
  (start_factor..number).select{|factor| number%factor == 0}[0]
end
 
def factors_of number, start_factor=2
  return [] if number == 1
  factor = first_divisible_factor start_factor, number
  [factor] + factors_of(number/factor, factor)
end

武可的Haskell版本

TDD过程存储于http://cyber-dojo.org/kata/edit/2EF003C866?avatar=zebra

1
2
3
4
5
6
7
8
9
10
11
factorOf _ 1 = []
factorOf p n 
    | exact_div = p : factorOf p (n `div` p)
    | no_more = [n]
    | otherwise = factorOf next_p n
    where 
        exact_div = n `mod` p == 0
        no_more = p * p  > n 
        next_p = p + 1

factor = factorOf 2

Jacky申导的Python版本

TDD过程存储于http://cyber-dojo.org/review/show/2BE7D52F15

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def f(n, p=2):
    if n < 2: return []
    if n % p == 0: return [p] + f(n/p, p)
    return f(n, p+1)

###############################################

from hiker import f
import unittest
 
class TestHiker(unittest.TestCase):
    def test_prime_factor(self):
        self.assertEqual([], f(1))
        self.assertEqual([2], f(2))
        self.assertEqual([3], f(3))
        self.assertEqual([2,2], f(4))
        self.assertEqual([2,3], f(6))
        self.assertEqual([2,2,2], f(8))
        self.assertEqual([3,3], f(9))
        self.assertEqual([2,2,3,3,3,5,5,19], f(2*2*3*3*3*5*5*19))
 
if __name__ == '__main__':
    unittest.main()

更多函数式编程内容见：