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

Question

我是 Haskell 的新手。为什么我收到错误消息

(Couldn't match type '[]' with 'IO' — Haskell) in folowing code.

主要我只需要运行算法的时间而没有结果。

只想测量算法时间。

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 monad 中执行的操作。相反，您可以将其放在 let 绑定(bind)中:

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 这样的库。这是专门为基准测试而设计的。