Haskell

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 绑定中：

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

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

Haskell - Couldn't match type [] with IO

types

match

main

quicksort