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)

错误信息本质上是一样的。它说 "Could not deduce (a ~ ([a] -> a))" 但仍然表明，就编译器而言， a 类型也必须同时是 [a] -> a （因此它也必须是 a ~ [a] -> ([a] -> a)， a ~ [[a] -> a] -> ([a] -> ([a] -> a))，等等（因此第一条错误消息中的 "infinite" 类型引用））。

如果这确实是您想要的类型，可以通过命名它并使它 明确地 递归来使其合法，如

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 的临时变量（或者更好的是 where，以便能够在守卫中使用它们），如

factorise (n, ps)
  | mod n f /= 0  =                        -- is the test correct?
                    v : factorise (v, ps)  -- is it really v : ... ?
  | otherwise     = factorise (n, tail ps)
     where
       f = head ps 
       v = div n f

...除了它永远不会停止ps！您必须包括一个额外的测试才能停止生成主要因素列表。

你能想出办法吗？ :)

Answer 2

我的解决方案（我忘了给出递归的基本情况以及其他一些更正）：

--generating prime list
primes :: Integral a => [a]
primes = sieve [2..]

sieve   :: Integral a => [a] -> [a]
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 :: Integral a => (a, [a]) -> [a]
factorise (n, ps)
    |   n == 1          = []
    |   mod n f == 0    = f : factorise (v, ps)
    |   otherwise       = factorise (n, tail ps)
    where
        f = head ps
        v = div n f

Haskell中递归分解一个整数和一些关于函数的问题

Factorising an integer recursively and some questions about functions in Haskell

primes

haskell

types

prime-factoring

type-signature