Tôi đã nhầm lẫn bởi việc thiếu các chức năng này trong giao diện cho loại Sequence, vì Data.List cung cấp các chức năng này. Có vấn đề về hiệu quả ở đây hay chỉ là thiếu nhu cầu cho các chức năng này?Tại sao Data.Sequence không có `insert 'hoặc` insertBy', và làm cách nào để thực hiện chúng một cách hiệu quả?
Và vì chúng không phải là một phần của Data.Sequence, làm thế nào tôi có thể triển khai hiệu quả chúng cho mục đích của tôi?
Đây là những gì tôi đã đưa ra:
> let insertBy cmp x seq = let (s1,s2) = partition (\y -> cmp x y == GT) seq in (s1 |> x) >< s2
> let s = fromList [1,2,3,4,5]
> insertBy compare 2 s
fromList [1,2,2,3,4,5]
Hoặc bạn chỉ có thể bắt chước các phiên bản dành cho danh sách:
{-# LANGUAGE ViewPatterns #-}
module Main
where
import Data.Sequence
insertBy :: (a -> a -> Ordering) -> a -> Seq a -> Seq a
insertBy _ x (viewl -> EmptyL) = singleton x
insertBy cmp x [email protected](viewl -> (y:<ys'))
= case cmp x y of
GT -> y <| insertBy cmp x ys'
_ -> x <| ys
Tôi cho rằng về bản chất nó sẽ nhanh như phương pháp nhanh nhất. Tôi sẽ đánh dấu câu trả lời này là chính xác, bởi vì tôi mới nhận ra mình cần nhiều hơn Sequence, tôi cần thực thi bất biến rằng chuỗi luôn luôn được sắp xếp, để tôi có thể chèn vào thời gian O (log n) thay vì O (n) thời gian. – danharaj
@danharaj, được coi là Data.Set? – luqui
@luqui, tôi có, nhưng những thay đổi về thứ tự của tôi trong quá trình thuật toán tôi đang ngụ ý, Bentley-Ottmann để tham khảo. Kể từ khi quan hệ thứ tự thay đổi, tôi không thể sử dụng Data.Set. Tuy nhiên, những thay đổi về trật tự theo cách cư xử, do đó, tìm kiếm nhị phân là cách để đi. – danharaj
Nó không phải là khá hoàn chỉnh như 'Data.List', nhưng giao diện trình tự phụ thuộc rất nhiều vào các loại lớp. 'map' từ' Functor', 'fold' từ' Có thể gập lại', v.v. Bạn cũng có thể sử dụng ListLike, http://hackage.haskell.org/package/ListLike, có một thể hiện cho kiểu Sequence và sẽ cung cấp cho bạn một giao diện hoàn chỉnh hơn, bao gồm 'insert' và' insertBy'; Tôi nghĩ giao diện giống như ví dụ thứ hai của Mikhail. –