Không thể tìm thấy chữ ký thích hợp cho hàm bằng STUArray (không thể GHC)

Question

Tôi đã xây dựng một hàm để tìm định thức của ma trận bằng ST-Monad và STArrays không được hộp (STUArray). Loại cho ma trận như sau:

newtype Matrix e = Matrix (Array Int (UArray Int e)) 

có nghĩa là, mảng không thay đổi chứa mảng không có hộp không thay đổi có chứa các phần tử. Điều này sẽ yêu cầu tôi thêm Predicate IArray UArray e vào các chức năng xử lý Matrix, do đó yêu cầu FlexibleContexts. Ok, xong rồi.

Chức năng sử dụng để tính toán các yếu tố quyết định có chữ ký sau đây:

detST :: (IArray UArray e, MArray (STUArray s) e (ST s), 
      Num e, Eq e, Division e) 
    => Array Int (UArray Int e) -> ST s e 

Tôi đang yêu cầu cũng để thêm Predicate MArray (STUArray s) e (ST s) từ trong nội bộ các mảng được chuyển đổi thành các mảng có thể thay đổi (bên ngoài đóng hộp, bên trong không có hộp bọc) .

Chức năng này có thể được sử dụng như sau:

main = do 
    let m@(Matrix x) = matrix [ [1,-2,3,234] 
           , [5,2,3,-3] 
           , [7,18,3,40] 
           , [2,9,71,0] ] 
     d = runST (detST x) :: Int -- needed for type check, ambiguous otherwise 

print d 

trình, tiền phạt. Nhưng nhìn nó xấu đến mức nào! Tất nhiên tôi không muốn cho đi các bên trong của Matrix (ít nhất là không xa hơn các vị ngữ gắn liền với chức năng của tôi đã làm cho tôi). Tôi muốn xác định chức năng sau:

det :: Matrix e -> e 

Và tôi không thể.

tôi đã cố gắng mà không có một chữ ký thích hợp:

det (Matrix arr) = runST (detST arr) 

thất bại. Đủ công bằng, tôi sẽ để bộ não của tôi hoạt động: detST yêu cầu IArray UArray e, MArray (STUArray s) e (ST s), Num e, Eq e, Division e, do đó, det, phải không?

det :: (IArray UArray e, MArray (STUArray s) e (ST s), 
      Num e, Eq e, Division e) => Matrix e -> e 

không thành công. Nhưng tôi không thấy như thế nào. Thông điệp mà GHC (7.4.2) mang lại cho tôi là:

Could not deduce (MArray (STUArray s) t (ST s)) 
    arising from a use of `detST' 

nhưng thuật ngữ chính xác là ở vị!

GHC gợi ý:

add (MArray (STUArray s) t (ST s)) to the context of 
    a type expected by the context: ST s t 
    or the inferred type of 
    det :: (Eq t, Num t, IArray UArray t, Division t) => Matrix t -> t 
or add an instance declaration for (MArray (STUArray s) t (ST s)) 

Được rồi. Theo sự hiểu biết của tôi, tôi đã làm điều đầu tiên đó. Cũng có tồn tại một cá thể cho rằng (MArray ...) (nếu không, làm thế nào tôi có thể đã sử dụng nó thành công trong chính ?!).

Tôi không chắc chắn về những gì là sai ở đây. Tôi tin rằng nó có liên quan đến trạng thái ST "ẩn" trong s và rằng số của detST là một số khác s so với s trong det sẽ là, nhưng tôi không biết cách viết loại này.

Định nghĩa đúng của det là gì và tại sao ?!

Chương trình không có det biên dịch tốt bằng cách chỉ sử dụng FlexibleContexts, không cảnh báo với -Wall.Bạn có thể tìm thấy mã nguồn hoàn chỉnh as a gist here.

Answer 1

tôi quản lý để có được điều này để làm việc bằng cách sử dụng thủ thuật được mô tả bởi Keegan McAllister in this article:

{-# LANGUAGE FlexibleContexts, ScopedTypeVariables, RankNTypes, GADTs #-} 

data Evidence s e where 
    Evidence :: (MArray (STUArray s) e (ST s)) => Evidence s e 

data ElemType e = ElemType (forall s. Evidence s e) 

det :: forall e . (IArray UArray e, Num e, Eq e, Division e) 
     => ElemType e -> Matrix e -> e 
det (ElemType e) mat = runST (f e mat) 
    where 
    f :: Evidence s e -> Matrix e -> ST s e 
    f Evidence (Matrix arr) = detST arr 

Cách sử dụng:

main :: IO() 
main = do 
    let m = matrix [ [1,-2,3,234] 
        , [5,2,3,-3] 
        , [7,18,3,40] 
        , [2,9,71,0] ] 
    print $ det (ElemType Evidence) (m :: Matrix Int) 

Vấn đề bắt nguồn từ việc thiếu các ràng buộc-rank cao - runST có loại (forall s. ST s a) -> a, vì vậy bạn cần một ràng buộc như forall s . MArray (STUArray s) e (ST s), không được GHC hỗ trợ. Thủ thuật này cho phép bạn thuyết phục trình kiểm tra kiểu mà ràng buộc thực sự nắm giữ. Thảo luận sâu hơn về vấn đề này có sẵn trong bài viết tôi đã liên kết ở trên.