中国剩余问题的Haskell解法

神奇的原贴算法题看程序员的魅力
无穷列表在解决这个问题上有很好的直观性.

{--
如果3个人一桌，多2个人。
如果5个人一桌，多4个人。
如果7个人一桌，多6个人。
如果9个人一桌，多8个人。
如果11个人一桌，正好。请问这屋里多少人？ 
--}



main = f 1 1 1 1 2 k l m n o where
    k = [3 * x + 2 | x <- [1..]]
    l = [5 * x + 4 | x <- [1..]]
    m = [7 * x + 6 | x <- [1..]]
    n = [9 * x + 8 | x <- [1..]]
    o = [11 * x | x <- [1..]]

-- f :: Integer -> Integer -> Integer -> Integer -> [Integer] -> [Integer] -> [Integer] -> [Integer] ->Integer
f a1 a2 a3 a4 a5 (b1:l1) (b2:l2) (b3:l3) (b4:l4) (b5:l5)
    | a1 == a2 && a2 == a3 && a3 == a4 && a4 == a5 = a1 : (f 1 a2 a3 a4 a5 (b1:l1) (b2:l2) (b3:l3) (b4:l4) (b5:l5))
    | a1 <= a2 && a1 <= a3 && a1 <= a4 && a1 <= a5 && b1 <= b2 && b1 <= b3 && b1 <= b4 && b1 <= b5 = f b1 a2 a3 a4 a5 l1 (b2:l2) (b3:l3) (b4:l4) (b5:l5)
    | a1 <= a2 && a1 <= a3 && a1 <= a4 && a1 <= a5 && b2 <= b1 && b2 <= b3 && b2 <= b4 && b2 <= b5 = f b2 a2 a3 a4 a5 (b1:l1) l2 (b3:l3) (b4:l4) (b5:l5)
    | a1 <= a2 && a1 <= a3 && a1 <= a4 && a1 <= a5 && b3 <= b1 && b3 <= b2 && b3 <= b4 && b3 <= b5 = f b3 a2 a3 a4 a5 (b1:l1) (b2:l2) l3 (b4:l4) (b5:l5)
    | a1 <= a2 && a1 <= a3 && a1 <= a4 && a1 <= a5 && b4 <= b1 && b4 <= b2 && b4 <= b3 && b4 <= b5 = f b4 a2 a3 a4 a5 (b1:l1) (b2:l2) (b3:l3) l4 (b5:l5)
    | a1 <= a2 && a1 <= a3 && a1 <= a4 && a1 <= a5 && b5 <= b1 && b5 <= b2 && b5 <= b3 && b5 <= b4 = f b5 a2 a3 a4 a5 (b1:l1) (b2:l2) (b3:l3) (b4:l4) l5
    | a2 <= a1 && a2 <= a3 && a2 <= a4 && a2 <= a5 && b1 <= b2 && b1 <= b3 && b1 <= b4 && b1 <= b5 = f a1 b1 a3 a4 a5 l1 (b2:l2) (b3:l3) (b4:l4) (b5:l5)
    | a2 <= a1 && a2 <= a3 && a2 <= a4 && a2 <= a5 && b2 <= b1 && b2 <= b3 && b2 <= b4 && b2 <= b5 = f a1 b2 a3 a4 a5 (b1:l1) l2 (b3:l3) (b4:l4) (b5:l5)
    | a2 <= a1 && a2 <= a3 && a2 <= a4 && a2 <= a5 && b3 <= b1 && b3 <= b2 && b3 <= b4 && b3 <= b5 = f a1 b3 a3 a4 a5 (b1:l1) (b2:l2) l3 (b4:l4) (b5:l5)
    | a2 <= a1 && a2 <= a3 && a2 <= a4 && a2 <= a5 && b4 <= b1 && b4 <= b2 && b4 <= b3 && b4 <= b5 = f a1 b4 a3 a4 a5 (b1:l1) (b2:l2) (b3:l3) l4 (b5:l5)
    | a2 <= a1 && a2 <= a3 && a2 <= a4 && a2 <= a5 && b5 <= b1 && b5 <= b2 && b5 <= b3 && b5 <= b4 = f a1 b5 a3 a4 a5 (b1:l1) (b2:l2) (b3:l3) (b4:l4) l5
    | a3 <= a1 && a3 <= a2 && a3 <= a4 && a3 <= a5 && b1 <= b2 && b1 <= b3 && b1 <= b4 && b1 <= b5 = f a1 a2 b1 a4 a5 l1 (b2:l2) (b3:l3) (b4:l4) (b5:l5)
    | a3 <= a1 && a3 <= a2 && a3 <= a4 && a3 <= a5 && b2 <= b1 && b2 <= b3 && b2 <= b4 && b2 <= b5 = f a1 a2 b2 a4 a5 (b1:l1) l2 (b3:l3) (b4:l4) (b5:l5)
    | a3 <= a1 && a3 <= a2 && a3 <= a4 && a3 <= a5 && b3 <= b1 && b3 <= b2 && b3 <= b4 && b3 <= b5 = f a1 a2 b3 a4 a5 (b1:l1) (b2:l2) l3 (b4:l4) (b5:l5)
    | a3 <= a1 && a3 <= a2 && a3 <= a4 && a3 <= a5 && b4 <= b1 && b4 <= b2 && b4 <= b3 && b4 <= b5 = f a1 a2 b4 a4 a5 (b1:l1) (b2:l2) (b3:l3) l4 (b5:l5)
    | a3 <= a1 && a3 <= a2 && a3 <= a4 && a3 <= a5 && b5 <= b1 && b5 <= b2 && b5 <= b3 && b5 <= b4 = f a1 a2 b5 a4 a5 (b1:l1) (b2:l2) (b3:l3) (b4:l4) l5
    | a4 <= a1 && a4 <= a2 && a4 <= a3 && a4 <= a5 && b1 <= b2 && b1 <= b3 && b1 <= b4 && b1 <= b5 = f a1 a2 a3 b1 a5 l1 (b2:l2) (b3:l3) (b4:l4) (b5:l5)
    | a4 <= a1 && a4 <= a2 && a4 <= a3 && a4 <= a5 && b2 <= b1 && b2 <= b3 && b2 <= b4 && b2 <= b5 = f a1 a2 a3 b2 a5 (b1:l1) l2 (b3:l3) (b4:l4) (b5:l5)
    | a4 <= a1 && a4 <= a2 && a4 <= a3 && a4 <= a5 && b3 <= b1 && b3 <= b2 && b3 <= b4 && b3 <= b5 = f a1 a2 a3 b3 a5 (b1:l1) (b2:l2) l3 (b4:l4) (b5:l5)
    | a4 <= a1 && a4 <= a2 && a4 <= a3 && a4 <= a5 && b4 <= b1 && b4 <= b2 && b4 <= b3 && b4 <= b5 = f a1 a2 a3 b4 a5 (b1:l1) (b2:l2) (b3:l3) l4 (b5:l5)
    | a4 <= a1 && a4 <= a2 && a4 <= a3 && a4 <= a5 && b5 <= b1 && b5 <= b2 && b5 <= b3 && b5 <= b4 = f a1 a2 a3 b5 a5 (b1:l1) (b2:l2) (b3:l3) (b4:l4) l5
    | a5 <= a1 && a5 <= a2 && a5 <= a3 && a5 <= a4 && b1 <= b2 && b1 <= b3 && b1 <= b4 && b1 <= b5 = f a1 a2 a3 a4 b1 l1 (b2:l2) (b3:l3) (b4:l4) (b5:l5)
    | a5 <= a1 && a5 <= a2 && a5 <= a3 && a5 <= a4 && b2 <= b1 && b2 <= b3 && b2 <= b4 && b2 <= b5 = f a1 a2 a3 a4 b2 (b1:l1) l2 (b3:l3) (b4:l4) (b5:l5)
    | a5 <= a1 && a5 <= a2 && a5 <= a3 && a5 <= a4 && b3 <= b1 && b3 <= b2 && b3 <= b4 && b3 <= b5 = f a1 a2 a3 a4 b3 (b1:l1) (b2:l2) l3 (b4:l4) (b5:l5)
    | a5 <= a1 && a5 <= a2 && a5 <= a3 && a5 <= a4 && b4 <= b1 && b4 <= b2 && b4 <= b3 && b4 <= b5 = f a1 a2 a3 a4 b4 (b1:l1) (b2:l2) (b3:l3) l4 (b5:l5)
    | a5 <= a1 && a5 <= a2 && a5 <= a3 && a5 <= a4 && b5 <= b1 && b5 <= b2 && b5 <= b3 && b5 <= b4 = f a1 a2 a3 a4 b5 (b1:l1) (b2:l2) (b3:l3) (b4:l4) l5

代码很可怕,实际上这个代码是由另一段Haskell程序生成的.
思路异常简单:对5个同余数列Merge操作,并将最近5个数据保存到寄器中,遇到5个相同的数字,得到一个结果.
结果:

Main> main
[2519,5984,9449,12914,16379,19844,23309,26774,30239,33704,37169,40634,44099,47564,51029,54494,57959,61424,64889,68354,71819,75284,78749,82214,85679,89144,92609,96074,99539,103004,106469,109934,113399,116864,120329,123794,127259,130724,134189,137654,141119,144584{Interrupted!}