递归构造整数以及有关Haskell中函数的一些问题

Question

我刚从Python那里开始学习Haskell，并且我对函数有一些疑问。我编写了以下代码：

--generating prime list
primes = sieve [2..]
sieve (p:ps) = p : sieve [x | x <- ps, mod x p /= 0]

--factorising function
--takes an input of a number and a list of primes and outputs a list of its prime factors
factorise (n,ps)
    | mod n head ps /= 0    = div n head ps : factorise (div n head ps, ps)
    | otherwise             = factorise (n,tail ps)

[首先，当我尝试编译时，收到与n有关的错误，说我cannot construct the infinite type: a ~ [a] -> a，这是为什么？

[其次，虽然我了解创建无限列表的逻辑，但是为什么不必显式声明函数sieve的类型，则隐含了这些类型？对于factorise功能，我必须吗？

最后，还有一种更简洁的方法来编写上述算法（我知道这是非常有效的）？

Answer 1

在这里和那里添加一些括号解决了问题：

factorise (n, ps)
    | mod n (head ps) /= 0  = div n (head ps) : factorise (div n (head ps), ps)
    | otherwise             = factorise (n, tail ps)

括号在Haskell中用于分组。 mod n (head ps)是mod对两个参数n和head ps的应用；没有括号的情况mod n head ps是mod对三个参数n，head和ps`的应用，但这只是不进行类型检查。

确实在错误修复后，所有类型均被成功推断为，>]

primes :: Integral a => [a]
sieve   :: Integral a => [a] -> [a]
factorise :: Integral a => (a, [a]) -> [a]
现在，您可以根据需要对它们进行专业化，如

primes :: [Integer]
sieve   :: [Integer] -> [Integer]
factorise :: (a ~ Integer) => (a, [a]) -> [a]
（（为factorise编写类型的后一种方法需要启用GADTs扩展名。

对于包含类型签名的原始代码，

factorise :: Integral a => (a, [a]) -> [a]
factorise (n,ps)
    | mod n head ps /= 0    = div n head ps : factorise (div n head ps, ps)
    | otherwise             = factorise (n,tail ps)
错误消息本质上是相同的。它说“无法推断(a ~ ([a] -> a))”，但仍然表明，编译器可以看到，a类型也必须同时为[a] -> a（因此也必须为a ~ [a] -> ([a] -> a)，a ~ [[a] -> a] -> ([a] -> ([a] -> a))等）（因此，第一条错误消息中将出现“无限”类型引用）。

如果确实是您想要的类型，则可以通过对其进行命名并使其显式

递归，从而使它合法，

data T a = MkT ([T a] -> T a)
允许此[[是

。 Haskell非常有能力具有递归类型。毕竟，简单的list类型是递归的，就像由[]定义的一样

data [] a = [] | a : ([] a)
data L a = Nil | Cons a (L a)

[我将在factorise中解决效率问题，待以后讲。尽管使用sieve非常简单：它的
main
问题是它一次只产生一个素数，而在每一步中它完全能够产生更多甚至更多的素数。

您能找到一种方法吗？

---

您的factorise函数是简单的试验除法分解算法的完美呈现（除了一些简单的错误）。提高简洁性的唯一方法是在let中引入临时变量，如[]

factorise (n, ps)
  | mod n (head ps) /= 0  = let f = head ps      -- is the test correct?
                                v = div n f 
                            in  _ : factorise (v, ps)  -- fill _ in
  | otherwise             = factorise (n, tail ps)

...除非永不停止！您必须包括其他测试才能停止生成主要因子列表。
您能找到一种方法吗？ ：）