Bản đồM trong Haskell có nghiêm ngặt không? Tại sao chương trình này bị tràn ngăn xếp?

Question

Các chương trình sau đây chấm dứt một cách chính xác:

import System.Random 

randomList = mapM (\_->getStdRandom (randomR (0, 50000::Int))) [0..5000] 

main = do 
    randomInts <- randomList 
    print $ take 5 randomInts 

Chạy:

$ runhaskell test.hs 
[26156,7258,29057,40002,26339] 

Tuy nhiên, cho ăn nó với một danh sách vô hạn, chương trình không bao giờ chấm dứt, và khi biên soạn, cuối cùng đưa ra một lỗi stack overflow!

import System.Random 

randomList = mapM (\_->getStdRandom (randomR (0, 50000::Int))) [0..] 

main = do 
    randomInts <- randomList 
    print $ take 5 randomInts 

chạy,

$ ./test 
Stack space overflow: current size 8388608 bytes. 
Use `+RTS -Ksize -RTS' to increase it. 

tôi mong đợi chương trình để uể oải đánh giá getStdRandom mỗi khi tôi chọn một mục ra khỏi danh sách, hoàn thiện sau khi làm như vậy 5 lần. Tại sao nó cố gắng để đánh giá toàn bộ danh sách?

Cảm ơn.

Có cách nào tốt hơn để có danh sách số ngẫu nhiên vô hạn không? Tôi muốn chuyển danh sách này thành một hàm thuần túy.

EDIT: Một số đọc nhiều tiết lộ rằng chức năng

randomList r = do g <- getStdGen 
        return $ randomRs r g 

là những gì tôi đang tìm kiếm.

EDIT2: sau khi đọc câu trả lời của camccann, tôi nhận thấy rằng getStdGen đang nhận được hạt giống mới trên mọi cuộc gọi. Thay vào đó, tốt hơn để sử dụng chức năng này như một one-shot phát danh sách ngẫu nhiên đơn giản:

import System.Random 

randomList :: Random a => a -> a -> IO [a] 
randomList r g = do s <- newStdGen 
        return $ randomRs (r,g) s 

main = do r <- randomList 0 (50::Int) 
      print $ take 5 r 

Nhưng tôi vẫn không hiểu tại sao mapM cuộc gọi của tôi đã không chấm dứt. Rõ ràng là không liên quan đến các số ngẫu nhiên, nhưng có thể liên quan đến mapM.

Ví dụ, tôi thấy rằng những điều sau đây cũng không chấm dứt:

randomList = mapM (\_->return 0) [0..] 

main = do 
    randomInts <- randomList 
    print $ take 50000 randomInts 

gì cho? Nhân tiện, IMHO, chức năng trên randomInts phải ở trong System.Random. Nó cực kỳ thuận tiện để có thể rất chỉ đơn giản là tạo một danh sách ngẫu nhiên trong đơn nguyên IO và chuyển nó vào một hàm thuần túy khi cần, tôi không thấy tại sao điều này không nên ở trong thư viện chuẩn.

Answer 1

tôi sẽ làm một cái gì đó nhiều như thế này, randomRs phép làm công việc với một RandomGen ban đầu:

#! /usr/bin/env runhaskell 

import Control.Monad 
import System.Random 


randomList :: RandomGen g => g -> [Int] 
randomList = randomRs (0, 50000) 

main :: IO() 
main = do 
    randomInts <- liftM randomList newStdGen 
    print $ take 5 randomInts 

Đối với sự lười biếng, những gì đang xảy ra ở đây là mapM là (sequence . map)

loại của nó là: mapM :: (Monad m) => (a -> m b) -> [a] -> m [b]

Lập bản đồ hàm, tạo [m b] và sau đó cần thực hiện tất cả các hành động đó để thực hiện m [b]. Đó là chuỗi sẽ không bao giờ vượt qua danh sách vô hạn.

này được giải thích tốt hơn trong câu trả lời cho một câu hỏi trước: Is Haskell's mapM not lazy?

Answer 2

con số ngẫu nhiên nói chung là không nghiêm ngặt, nhưng monadic ràng buộc là - vấn đề ở đây là mapM có thiết lập trình tự hoàn toàn danh sách. Hãy xem xét chữ ký loại của nó, (a -> m b) -> [a] -> m [b]; như điều này ngụ ý, những gì nó làm là đầu tiên map danh sách loại [a] vào danh sách loại [m b], sau đó sequence danh sách đó để nhận kết quả loại m [b]. Vì vậy, khi bạn ràng buộc kết quả của việc áp dụng mapM, ví dụ: bằng cách đặt nó ở bên phải của <-, điều này có nghĩa là "ánh xạ chức năng này trong danh sách, sau đó thực hiện từng hành động đơn lẻ và kết hợp kết quả trở lại vào một danh sách duy nhất". Nếu danh sách là vô hạn, điều này tất nhiên sẽ không chấm dứt.

Nếu bạn chỉ muốn một luồng các số ngẫu nhiên, bạn cần tạo danh sách mà không cần sử dụng một đơn nguyên cho mỗi số. Tôi không hoàn toàn chắc chắn lý do tại sao bạn đã sử dụng thiết kế mà bạn có, nhưng ý tưởng cơ bản là: Cho một giá trị hạt giống, sử dụng trình tạo số giả ngẫu nhiên để tạo ra một cặp 1) một số ngẫu nhiên 2) một hạt giống mới , sau đó lặp lại với hạt giống mới. Bất kỳ hạt giống nhất định nào cũng sẽ cung cấp cùng một trình tự mỗi lần. Vì vậy, bạn có thể sử dụng hàm getStdGen, sẽ cung cấp một hạt giống tươi trong đơn vị IO; bạn có thể sử dụng hạt giống đó để tạo ra một chuỗi vô hạn trong mã hoàn toàn thuần khiết.

Thực tế, System.Random cung cấp các chức năng chính xác cho mục đích đó, randoms hoặc randomRs thay vì random và randomR.

Nếu vì một số lý do bạn muốn tự mình làm, điều bạn muốn về cơ bản là mở ra. Chức năng unfoldr từ Data.List có chữ ký số (b -> Maybe (a, b)) -> b -> [a], tương đối tự giải thích: Với giá trị loại b, nó áp dụng hàm để nhận được loại a và giá trị máy phát mới loại b hoặc Nothing để cho biết kết thúc chuỗi.

Bạn muốn danh sách vô hạn, vì vậy sẽ không bao giờ phải trả lại Nothing. Như vậy, một phần áp dụng randomR đến phạm vi mong muốn và sáng tác nó với Just cho này:

Just . randomR (0, 50000::Int) :: (RandomGen a) => a -> Maybe (Int, a) 

ăn đó vào unfoldr cho này:

unfoldr (Just . randomR (0, 50000::Int)) :: (RandomGen a) => a -> [Int] 

... mà không chính xác như nó tuyên bố: Cho một Ví dụ của RandomGen, nó sẽ tạo ra một danh sách các số ngẫu nhiên được tạo từ một hạt giống ngẫu nhiên (và lười biếng).