Haskell - не удалось сопоставить тип [] с вводом-выводом

Я новичок в Хаскеле. Почему я получаю сообщение об ошибке

(Не удалось сопоставить тип «[]» с «IO» — Haskell) в следующем коде.

В основном мне нужно только время работы алгоритма без результата.

Только хочу измерить время алгоритма.

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)

types main match haskell quicksort
person MatejKr    schedule 17.07.2015    source источник

Ответы (2)


arrow_upward
6
arrow_downward

Ваша функция 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, которая была специально создана для сравнительного анализа.

person Sibi    schedule 17.07.2015
comment
Благодарю вас. Проблема в том, что теперь я получаю не время алгоритма, а время алгоритма и время печати. - person MatejKr; 17.07.2015
comment
@MatejKr Я обновил ответ, чтобы не использовать печать, а вместо этого принудительно выполнять вычисления с использованием оператора Bang. - person Sibi; 17.07.2015
comment
Почему я получаю недопустимый рисунок челки (используйте BangPattern). Я новичок в haskell. Спасибо. - person MatejKr; 17.07.2015
comment
@MatejKr Поместите {-#LANGUAGE BangPatterns#-} поверх вашего файла. - person Sibi; 17.07.2015
comment
Узор челки здесь неправильный. Это не приведет к полной оценке и не приведет к правильному результату. Просто используйте что-то вроде критерия для сравнительного анализа, а не изобретайте велосипед. - person kosmikus; 17.07.2015
comment
Не могли бы Вы уточнить. Я новичок в Haskell и не знаю, как это сделать. Спасибо - person MatejKr; 17.07.2015
comment
@kosmikus Почему BangPatterns не приведет к полной оценке здесь? Хотя я согласен, что этот критерий следует использовать для бенчмаркинга. @MatejKr Это библиотека Haskell, используемая для сравнительного анализа. - person Sibi; 17.07.2015
comment
Потому что образцы челки обычно не вызывают полной оценки, а оценивают только нормальную форму слабой головы. И qsort1 возвращает список. - person kosmikus; 17.07.2015

arrow_upward
0
arrow_downward

Я использовал метод ниже, и он отлично работает:

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