功能性学习困境

Question

我是函数式语言的初学者,我正试图在Haskell中完成整个过程.这是一个快速而肮脏的功能,可以找到数字的所有因素:

factors :: (Integral a) => a -> [a]
factors x = filter (\z -> x `mod` z == 0) [2..x `div` 2]

工作正常,但我发现对于大数字来说,它是无法忍受的.所以我让自己变得更好了:

factorcalc :: (Integral a) => a -> a -> [a] -> [a]
factorcalc x y z
    | y `elem` z      = sort z
    | x `mod` y == 0  = factorcalc x (y+1) (z ++ [y] ++ [(x `div` y)])
    | otherwise       = factorcalc x (y+1) z

但这是我的问题:即使代码有效,并且可以减少我的程序执行时间的几个小时,这很可怕!

它充满了丑陋的命令性思维:它不断更新循环中的计数器和数据结构,直到它完成.由于你不能在纯粹的函数式编程中改变状态,我通过将数据保存在参数中来欺骗,函数只是一遍又一遍地传递给自己.

我可能错了,但必须有更好的方法来做同样的事情......

Answer 1

请注意,原始问题要求所有因素,而不仅仅是主要因素.素数因素较少,可能会更快找到它们.也许这就是OQ想要的.也许不是.但是让我们解决原始问题并将"乐趣"重新放回"功能"中!

一些观察:

• 这两个函数不会产生相同的输出 - 如果x是一个完美的正方形,第二个函数包括平方根两次.

• 第一个函数枚举检查与x大小成比例的许多潜在因素; 第二个函数只检查与平方根成正比x,然后停止(带有上面提到的错误).

• 第一个函数(factors)从2分配所有整数的列表n div 2,其中第二个函数从不分配列表,而是在参数中一次访问一个较少的整数.我运行了优化器-O并查看了输出-ddump-simpl,GHC只是不够聪明,不能优化那些分配.

• factorcalc是尾递归的,这意味着它编译成一个紧密的机器代码循环; filter不是也不是.

一些实验表明平方根是杀手:

这是一个样本函数,它将x的因子从z减少到2:

factors_from x 1 = []
factors_from x z 
  | x `mod` z == 0 = z : factors_from x (z-1)
  | otherwise      =     factors_from x (z-1)

factors'' x = factors_from x (x `div` 2)

它有点快,因为它没有分配,但它仍然不是尾递归.

这是一个尾递归版本,更忠实于原作:

factors_from' x 1 l = l
factors_from' x z l
  | x `mod` z == 0 = factors_from' x (z-1) (z:l)
  | otherwise      = factors_from' x (z-1) l

factors''' x = factors_from x (x `div` 2)

这仍然比factorcalc因为它枚举从2到2的所有整数慢x div 2,而factorcalc在平方根处停止.

有了这些知识,我们现在可以创建一个功能更强大的版本factorcalc,复制它的速度和错误:

factors'''' x = sort $ uncurry (++) $ unzip $ takeWhile (uncurry (<=)) $ 
                [ (z, x `div` z) | z <- [2..x], x `mod` z == 0 ]

我没有完全确定时间,但是给了1亿作为输入,它都是factorcalc瞬间终止,其他的都需要几秒钟.

功能的工作原理和原因留给读者练习:-)

附录:好的,为了缓解眼球出血,这里有一个稍微更健全的版本(并且没有bug):

saneFactors x = sort $ concat $ takeWhile small $
                [ pair z | z <- [2..], x `mod` z == 0 ]
    where pair z = if z * z == x then [z] else [z, x `div` z]
          small [z, z'] = z < z'
          small [z]     = True