项目Euler 3 - Haskell

Question

我正在努力解决Haskell中的Project Euler问题.我已经得到了下面的问题3的解决方案,我已经在小数字上进行了测试并且它可以正常工作,但是由于通过首先导出所有素数数字来实现蛮力,所以对于较大的数字它是指数级慢的.

-- Project Euler 3

module Main 
    where

import System.IO
import Data.List

main = do
    hSetBuffering stdin LineBuffering
    putStrLn "This program returns the prime factors of a given integer"
    putStrLn "Please enter a number"
    nums <- getPrimes
    putStrLn "The prime factors are: "
    print (sort nums)


getPrimes = do
    userNum <- getLine
    let n = read userNum :: Int
    let xs = [2..n]
    return $ getFactors n (primeGen xs)

--primeGen :: (Integral a) => [a] -> [a]
primeGen [] = []
primeGen (x:xs) = 
    if x >= 2
    then x:primeGen (filter (\n->n`mod` x/=0) xs)
    else 1:[2]

--getFactors
getFactors :: (Integral a) => a -> [a] -> [a]
getFactors n xs = [ x | x <- xs, n `mod` x == 0]

我已经看过这里的解决方案了,可以看看它是如何通过第一个后卫进行优化的factor.我不明白的是:

primes = 2 : filter ((==1) . length . primeFactors) [3,5..]

特别是第一个论点filter.

((==1) . length . primeFactors)

由于primeFactors本身就是一个函数,我不明白它是如何在这种情况下使用的.有人可以解释一下这里发生了什么吗？

Answer 1

如果要ghci在命令行上打开并键入

Prelude> :t filter

你会得到一个输出

filter :: (a -> Bool) -> [a] -> [a]

这意味着filter需要2个参数.

• (a -> Bool)是一个接受单个输入的函数,并返回一个Bool.
• [a] 是一个任何类型的列表,因为它与第一个参数的类型相同.

filter将循环遍历其第二个参数列表中的每个元素,并将其应用于作为其第一个参数的函数.如果第一个参数返回True,则会将其添加到结果列表中.

再次,在ghci,如果你要打字

Prelude> :t (((==1) . length . primeFactors))

你应该得到

(((==1) . length . primeFactors)) :: a -> Bool

(==1) 是部分应用的功能.

Prelude> :t (==)
(==) :: Eq a => a -> a -> Bool
Prelude> :t (==1)
(==1) :: (Eq a, Num a) => a -> Bool

它只需要一个参数而不是两个.

意味着在一起,它将采用单个参数,并返回一个布尔值.

它的工作方式如下.

• primeFactors将采用一个参数,并计算结果,这是一个[Int].
• length 将获取此列表,并计算列表的长度,并返回一个 Int
• (==1)将查看返回的值length是否等于1.

如果列表的长度是1,则表示它是素数.