Bitmap lười biếng vô hạn

Question

Tôi đang cố gắng xây dựng một cấu trúc dữ liệu lười biếng chứa một bitmap vô hạn. Tôi muốn hỗ trợ các hoạt động sau đây:

1. true :: InfBitMap

   Trả về một bitmap vô hạn của True, ví dụ: tất cả các vị trí nên có giá trị True.

2. falsify :: InfBitMap -> [Int] -> InfBitMap

   Đặt tất cả các vị trí trong danh sách để False. Danh sách này có thể là vô hạn. Ví dụ, falsify true [0,2 ..] sẽ trả về một danh sách trong đó tất cả (và chỉ) các vị trí lẻ là True.

3. check :: InfBitMap -> Int -> Bool

   Kiểm tra giá trị của chỉ số.

Đây là những gì tôi có thể làm cho đến nay.

-- InfBitMap will look like [(@), (@, @), (@, @, @, @)..] 
type InfBitMap = [Seq Bool] 

true :: InfBitMap 
true = iterate (\x -> x >< x) $ singleton True 

-- O(L * log N) where N is the biggest index in the list checked for later 
-- and L is the length of the index list. It is assumed that the list is 
-- sorted and unique. 
falsify :: InfBitMap -> [Int] -> InfBitMap 
falsify ls is = map (falsify' is) ls 
    where 
     -- Update each sequence with all indices within its length 
     -- Basically composes a list of (update pos False) for all positions 
     -- within the length of the sequence and then applies it. 
     falsify' is l = foldl' (.) id 
           (map ((flip update) False) 
            (takeWhile (< length l) is)) 
         $ l 
-- O(log N) where N is the index. 
check :: InfBitMap -> Int -> Bool 
check ls i = index (fromJust $ find ((> i) . length) ls) i 

tôi tự hỏi nếu có một số khái niệm Haskellish/cấu trúc dữ liệu mà tôi đang thiếu đó sẽ làm cho mã của tôi thanh lịch hơn/hiệu quả hơn (hằng số không quan trọng với tôi, chỉ cần theo thứ tự). Tôi đã cố gắng nhìn vào dây khóa kéo và ống kính nhưng họ dường như không giúp đỡ. Tôi muốn giữ sự phức tạp của các bản cập nhật và kiểm tra logarit (có lẽ chỉ là lôgarit phân bổ).

Lưu ý: trước khi ai đó nghi ngờ điều đó, đây không phải là vấn đề về bài tập về nhà!

Cập nhật:

Nó chỉ xảy ra với tôi kiểm tra có thể được cải thiện để:

-- O(log N) where N is the index. 
-- Returns "collapsed" bitmap for later more efficient checks. 
check :: InfBitMap -> Int -> (Bool, InfBitMap) 
check ls i = (index l i, ls') 
    where 
     ls'@(l:_) = dropWhile ((<= i) . length) ls 

Mà có thể được biến thành một đơn nguyên cho mã sạch sẽ.

Answer 1

Biến thể nhỏ trên integer trie nổi tiếng dường như được áp dụng tại đây.

{-# LANGUAGE DeriveFunctor #-} 

data Trie a = Trie a (Trie a) (Trie a) deriving (Functor) 

true :: Trie Bool 
true = Trie True true true 

-- O(log(index)) 
check :: Trie a -> Int -> a 
check t i | i < 0 = error "negative index" 
check t i = go t (i + 1) where 
    go (Trie a _ _) 1 = a 
    go (Trie _ l r) i = go (if even i then l else r) (div i 2) 

--O(log(index)) 
modify :: Trie a -> Int -> (a -> a) -> Trie a 
modify t i f | i < 0 = error "negative index" 
modify t i f = go t (i + 1) where 
    go (Trie a l r) 1 = Trie (f a) l r 
    go (Trie a l r) i | even i = Trie a (go l (div i 2)) r 
    go (Trie a l r) i = Trie a l (go r (div i 2)) 

Đáng tiếc là chúng ta không thể sử dụng để thực hiện modifyfalsify bởi vì chúng tôi không thể xử lý danh sách vô hạn của chỉ số như vậy (tất cả các sửa đổi phải được thực hiện trước một phần tử của Trie có thể được kiểm tra). Thay vào đó, chúng ta nên làm một cái gì đó giống như một hợp nhất:

ascIndexModify :: Trie a -> [(Int, a -> a)] -> Trie a 
ascIndexModify t is = go 1 t is where 
    go _ t [] = t 
    go i t@(Trie a l r) ((i', f):is) = case compare i (i' + 1) of 
     LT -> Trie a (go (2*i) l ((i', f):is)) (go (2*i+1) r ((i', f):is)) 
     GT -> go i t is 
     EQ -> Trie (f a) (go (2*i) l is) (go (2*i+1) r is) 

falsify :: Trie Bool -> [Int] -> Trie Bool 
falsify t is = ascIndexModify t [(i, const False) | i <- is] 

chúng tôi giả định tăng dần chặt chẽ chỉ số trong is, vì nếu không chúng tôi sẽ bỏ qua nơi trong Trie hoặc thậm chí có được không chấm dứt, ví dụ như trong check (falsify t (repeat 0)) 1.

Độ phức tạp thời gian là một chút phức tạp do sự lười biếng. Trong check (falsify t is) index, chúng tôi phải trả thêm chi phí cho một số so sánh log 2 index liên tục và số lượng so sánh thêm length (filter (<index) is) (i. E. Chi phí của tất cả các chỉ số nhỏ hơn những gì chúng tôi đang tìm kiếm). Bạn có thể nói đó là O(max(log(index), length(filter (<index) is)). Dù sao, nó chắc chắn tốt hơn so với O(length is * log (index)) mà chúng tôi sẽ nhận được cho một falsify được triển khai cho hữu hạn is-sử dụng modify.

Chúng tôi phải ghi nhớ rằng các nút cây được đánh giá một lần và sau đó check -s cho cùng một chỉ mục sau check đầu tiên không phải trả thêm bất kỳ chi phí nào cho falsify. Một lần nữa, sự lười biếng làm cho điều này trở nên phức tạp hơn một chút.

Điều này falsify cũng hoạt động khá tốt khi chúng tôi muốn duyệt qua tiền tố của một trie. Thực hiện chức năng này toList:

trieToList :: Trie a -> [a] 
trieToList t = go [t] where 
    go ts = [a | Trie a _ _ <- ts] 
      ++ go (do {Trie _ l r <- ts; [l, r]}) 

Đây là lần truyền đầu tiên theo chiều rộng tiêu chuẩn, theo thời gian tuyến tính. Thời gian truyền tải vẫn là tuyến tính khi chúng tôi tính toán take n $ trieToList (falsify t is), vì falsify phát sinh tối đa n + length (filter (<n) is) so sánh bổ sung, tối đa là 2 * n, giả sử tăng nghiêm ngặt is.

(lưu ý bên lề: yêu cầu không gian của bề ngang đầu tiên là khá đau đớn, nhưng tôi không thể nhìn thấy một cách đơn giản để giúp nó, kể từ khi làm sâu sắc lặp đi lặp lại thậm chí tệ hơn ở đây, bởi vì có toàn bộ cây phải được tổ chức trong bộ nhớ, trong khi bfs chỉ phải nhớ mức đáy của cây).

Answer 2

Một cách để thể hiện điều này là một hàm.

true = const True 

falsify ls is = \i -> not (i `elem` is) && ls i 

check ls i = ls i 

Chức năng đúng và giả mạo tốt và hiệu quả. Chức năng kiểm tra có thể xấu như tuyến tính. Có thể cải thiện hiệu quả của cùng một ý tưởng cơ bản. Tôi thích sự thanh lịch của nó.