Lấy khoảng giữa Ix trong khoảng thời gian O (1) trong Haskell

Question

Tôi đang chơi với this mã kata trong Haskell và tôi đã xem qua câu hỏi trong chủ đề.

Điều quan trọng để tìm điểm giữa của mảng có chỉ mục là giá trị số, nhưng chỉ mục mảng của Haskell có thể là bất kỳ trường hợp nào của typeclass Ix, bao gồm, ví dụ, tuple (Int, Word, Card) là một thể hiện của Ix nhưng không phải của Num.

Một cách để lấy điểm giữa của mảng là truy vấn chiều dài của nó, truy vấn danh sách chỉ mục và thả một nửa danh sách đó, nhưng điều này yêu cầu thời gian O (n).

Có ai biết cách lập chỉ mục để làm điều đó trong thời gian không? Tôi cảm thấy như có nên có một, kể từ khi một phạm vi Ix là vụ phải biject với một phạm vi số nguyên.

Answer 1

Ix typeclass chỉ yêu cầu tiêm từ các giá trị loại i đến giá trị Int. index cùng với range thể cung cấp cho chúng tôi bản đồ nghịch đảo:

index' :: (Ix i) => (i, i) -> Int -> i 
index' b x = range b ! x 

Như bạn thấy index' đánh giá ít nhất là trong thời gian tuyến tính. Ngoài ra, chúng tôi không thể có ý tưởng về thời gian hoạt động của range b. Nó được đánh giá theo cách mà người dùng đã định nghĩa trong định nghĩa cá thể. Vì vậy, tối ưu hóa cần thiết trong trường hợp của bạn (có được trung điểm của một mảng) có thể diễn ra nếu và chỉ khi chúng ta có một số loại index' hoạt động trong thời gian không đổi. Vì Ix typeclass không cung cấp cho chúng tôi ánh xạ thời gian liên tục từ Int đến i, chúng tôi nên yêu cầu người dùng cho điều đó. Hãy xem xét mã tiếp theo:

midpoint :: (Ix j) => (Int -> j) -> Array j e -> e 
midpoint f a = a ! f middle 
       where middle = rangeSize (bounds a) `div` 2 

Sự phức tạp của việc lấy điểm giữa của mảng phụ thuộc vào độ phức tạp do người dùng xác định f. Vì vậy, nếu các giá trị của loại chỉ mục của chúng tôi i có thể trong thời gian không đổi được đánh giá từ các giá trị Int và ngược lại - chúng tôi nhận được điểm giữa trong thời gian không đổi.

Cũng xem xét ixmap chức năng từ Data.Ix:

ixmap :: (Ix i, Ix j) => (i, i) -> (i -> j) -> Array j e -> Array i e