Haskell-无法将类型 [] 与 IO 匹配

Question

我是Haskell的新人。为什么我得到错误信息

(无法匹配类型'[]'与'IO' - Haskell)以下代码。

在main中，我只需要没有结果的算法运行时间。

只想测量算法时间

qsort1 :: Ord a => [a] -> [a]
qsort1 []     = []
qsort1 (p:xs) = qsort1 lesser ++ [p] ++ qsort1 greater
    where
        lesser  = [ y | y <- xs, y < p ]
        greater = [ y | y <- xs, y >= p ]
main = do
    start <- getCurrentTime
    qsort1 (take 1000000 $ randomRs (1, 100000) (mkStdGen 42))
    end <- getCurrentTime
    print (diffUTCTime end start) 

Answer 1

您的main函数不正确。除非qsort1是IO动作，否则您不能在IO单子中执行它。相反，你可以把它放在let绑定中:

main = do
    start <- getCurrentTime
    let x = qsort1 (take 1000000 $ randomRs ((1 :: Int), 100000) (mkStdGen 42))
    end <- getCurrentTime
    print (diffUTCTime end start) 

还请注意，我已经明确地为1提供了一个类型注释，以避免一些编译错误。

但是，由于惰性求值，实际上您无法找到执行排序所花费的总时间。x永远不会被计算，因为它从未在程序中使用过。如果你运行main，它会给你这个绝对错误的输出:

λ> main
0.000001s

你可以用这个来计算:

main = do
    start <- getCurrentTime
    let x = qsort1 (take 1000000 $ randomRs ((1 :: Int), 100000) (mkStdGen 42))
    print x
    end <- getCurrentTime
    print (diffUTCTime end start)  

除了打印，您还可以使用BangPatterns扩展来强制计算qsort1:

main = do
    start <- getCurrentTime
    let !x = qsort1 (take 1000000 $ randomRs ((1 :: Int), 100000) (mkStdGen 42))
    end <- getCurrentTime
    print (diffUTCTime end start)   

BangPatterns不会像@kosmikus指出的那样导致完全评估。可以使用criterion这样的库，它是专门为基准测试而设计的。

Answer 2

我使用了下面的方法，它工作得很好:

main = do
        let arr = take 1000000 $ randomRs ((1 :: Int), 10000000) (mkStdGen 59)
        defaultMain [
          bgroup "qs" [ bench "1"  $ nf quickSort arr ]
          ]