Byłem zdezorientowany brakiem tych funkcji w interfejsie typu Sekwencja, ponieważ Data.List udostępnia te funkcje. Czy jest tu problem z wydajnością, czy jest to po prostu brak zapotrzebowania na te funkcje?Dlaczego Data.Sequence nie ma "wstawić" lub "wstawić" i jak skutecznie je wdrożyć?
A ponieważ nie są częścią Data.Sequence, w jaki sposób mogę skutecznie wdrożyć je do moich celów?
Oto co wymyśliłem:
> 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]
Albo może po prostu naśladować wersję dla list:
{-# 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
Przypuszczam, że byłoby to zasadniczo tak szybkie, jak najszybsza metoda. Mam zamiar oznaczyć tę odpowiedź jako poprawną, ponieważ właśnie uświadomiłem sobie, że potrzebuję czegoś więcej niż Sekwencja, muszę wymusić niezmiennik, że sekwencja jest zawsze uporządkowana, tak że mogę zrobić wstawienie w czasie O (log n) zamiast O (n) czas. – danharaj
@danharaj, za Data.Set? – luqui
@luqui, mam, ale moje zamówienie zmienia się w trakcie wprowadzanego algorytmu, Bentley-Ottmann w celach informacyjnych. Ponieważ relacja zleceń zmienia się, nie mogę używać Data.Set. Jednak kolejność zmian zachowuje się tak, więc szukanie binarne jest drogą do zrobienia. – danharaj
To nie całkiem tak kompletne jak 'Data.List', ale interfejs Sequence opiera się głównie na klasach typów. 'map' od' Functor', 'fold' od' Foldable', itp. Możesz także użyć ListLike, http://hackage.haskell.org/package/ListLike, który ma instancję typu Sequence i da ci znacznie bardziej kompletny interfejs, w tym 'insert' i' insertBy'; Myślę, że interfejs jest taki sam jak drugi przykład Michaiła. –