一些经典算法的 Haskell 实现

一些经典算法的 Haskell 实现

1. Sieve of Eratosthenes

算法描述见 

Haskell 实现

-- Sieve.hs

sieve :: [Integer] -> [Integer]
sieve (x:xs) = x : sieve xs'
             where xs' = filter (\y -> y `mod` x /= 0) xs

primes = 2 : sieve [3,5..]

加了平方优化后的版本

isPrime :: Integer -> [Integer] -> Bool
isPrime p (x:xs)
    | x*x > p = True
    | p `mod` x == 0 = False
    | otherwise = isPrime p xs

primes = 2 : [ p | p <- [3,5..], isPrime p primes ]


---

2. Quick Sort

算法描述见 

Haskell 实现

-- Qsort.hs
qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort (filter (<= x) xs) ++ [x] ++ qsort (filter (> x) xs)


---

未完待续！