时间戳

首页 > 解决方案 > 递归分解整数以及有关 Haskell 中函数的一些问题

haskell - 递归分解整数以及有关 Haskell 中函数的一些问题

问题描述

我刚从 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，说 I cannot construct the infinite type: a ~ [a] -> a，这是为什么？

其次，虽然我理解创建无限列表背后的逻辑，但为什么不必明确说明函数sieve的类型，类型是否隐含？对于factorise功能，我必须这样做吗？

最后，是否有更简洁的方法来编写上述算法（我理解它非常有效）？

标签： haskelltypesprimesprime-factoringtype-signature

解决方案

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

--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

推荐阅读