Haskell - ไม่สามารถจับคู่ประเภท [] กับ IO

ฉันยังใหม่กับ 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 monad คุณสามารถใส่มันลงในการเชื่อมโยงการอนุญาตแทน:

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