map runSTArray trong danh sách STArrays?

Question

Tôi có một chức năng tạo ra đệ quy một danh sách các ma trận phẳng từ một cây phải có thể thay đổi được vì các phần tử của chúng được cập nhật thường xuyên trong quá trình tạo. Cho đến nay tôi đã đưa ra một giải pháp đệ quy mà có chữ ký:

doAll :: .. -> [ST s (STArray s (Int, Int) Int)] 

Lý do tôi không trả lại [UArray (Int,Int) Int] trực tiếp được vì doAll được gọi là đệ quy, sửa đổi các yếu tố của các ma trận trong danh sách và gắn thêm ma trận mới . Tôi không muốn đóng băng và làm tan các ma trận một cách không cần thiết.

Cho đến nay rất tốt. Tôi có thể kiểm tra việc n ma trận -thứ (loại Array (Int, Int) Int) trong ghci

runSTArray (matrices !! 0) 
runSTArray (matrices !! 1) 

và thực sự tôi nhận được kết quả chính xác cho thuật toán của tôi. Tuy nhiên, tôi không tìm thấy một cách để lập bản đồ runSTUArray qua danh sách được trả về bởi doAll:

map (runSTArray) matrices 

Couldn't match expected type `forall s. ST s (STArray s i0 e0)' 
      with actual type `ST s0 (STArray s0 (Int, Int) Int)' 

Vấn đề tương tự sẽ xảy ra nếu tôi cố gắng để đánh giá một cách đệ quy trên danh sách hoặc thử để đánh giá các yếu tố đơn lẻ bọc trong một chức năng

Ai đó có thể giải thích điều gì đang diễn ra (tôi thực sự không hiểu ý nghĩa của từ khóa forall) và cách tôi có thể đánh giá các mảng trong danh sách?

Answer 1

Đây là một hậu quả đáng tiếc của lừa kiểu đó làm cho ST an toàn. Trước tiên, bạn cần biết cách ST hoạt động. Cách duy nhất để lấy từ mã đơn ST đến mã thuần túy là với chức năng runST hoặc các chức năng khác được xây dựng trên nó như runSTArray. Đây là tất cả các hình thức forall s.. Điều này có nghĩa rằng, để xây dựng một mảng từ một STArray, trình biên dịch phải có khả năng xác định rằng nó có thể thay thế bất kỳ kiểu nào nó thích cho biến kiểu s bên trong runST.

Bây giờ, hãy xem xét hàm map :: (a -> b) -> [a] -> [b]. Điều này cho thấy mọi phần tử trong danh sách phải có cùng một loại (a) và do đó cũng giống như s. Nhưng ràng buộc thêm này vi phạm loại runSTArray, tuyên bố rằng trình biên dịch phải có khả năng tự do thay thế các giá trị khác cho s.

Bạn có thể làm việc này bằng cách định nghĩa một hàm mới để đầu đóng băng các mảng bên trong ST đơn nguyên, sau đó chạy kết quả ST hành động:

runSTArrays :: Ix ix => (forall s. [ST s (STArray s ix a)]) -> [Array ix a] 
runSTArrays arrayList = runST $ (sequence arrayList >>= mapM freeze) 

Lưu ý forall yêu cầu tiện ích RankNTypes.

Answer 2

Bạn vừa mới trả về các giới hạn của hệ thống kiểu.

runSTArray có loại xếp hạng cao hơn. Bạn phải vượt qua nó một hành động ST có biến kiểu trạng thái là duy nhất. Tuy nhiên, trong Haskell nó thường không thể có giá trị như vậy trong danh sách.

Toàn bộ điều là một lược đồ thông minh để đảm bảo rằng các giá trị bạn tạo ra trong một hành động ST không thể thoát ra khỏi đó. Có nghĩa là, có vẻ như thiết kế của bạn bị hỏng.

Một gợi ý: bạn không thể xử lý các giá trị trong một hành động ST, như

sequence [ ... your ST s (STArray s x) ...] >>= processing 
    where 
    processing :: [STArray s x] -> ST s (your results)