Haskell - 无法匹配类型[]和IO

Question

我是Haskell的新手，为什么会得到以下代码中的错误信息（在Haskell中类型“[]”与“IO”无法匹配）。

在主函数中，我只需要算法运行时间而不是结果。

只想测量算法时间。

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) 

- MatejKr

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：

使用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 这样专门用于基准测试的库。

- Sibi

---

@MatejKr 在你的文件顶部加上 {-#LANGUAGE BangPatterns#-}。 - Sibi

感叹号模式在这里不正确。它不会强制进行完全评估，也不会导致正确的结果。只需使用类似于 criterion 的基准测试工具，而不是试图重新发明轮子。 - kosmikus

你能具体一些吗？我是Haskell的新手，不知道该怎么做。谢谢。 - MatejKr

@kosmikus 为什么 BangPatterns 在这里不会导致完全评估？尽管我认为应该使用标准进行基准测试。 @MatejKr 它是一个用于基准测试的 Haskell 库。 - Sibi

因为惊叹号模式通常不会导致完全评估，而只会评估为弱头正常形式。而qsort1返回一个列表。 - kosmikus

Answer 2

我使用了下面的方法，它运行良好：

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

- MatejKr