Почему в Data.Sequence нет `insert 'или` insertBy', и как мне эффективно их реализовать?

Question

Меня смутило отсутствие этих функций в интерфейсе для типа Sequence, поскольку Data.List предоставляет эти функции.Есть ли здесь проблема с эффективностью или это просто отсутствие спроса на эти функции?

И поскольку они не являются частью Data.Sequence, как я могу эффективно реализовать их для своих целей?

Answer 1

Вот что я придумала:

> 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]

Или вы можете просто изменить версию для списков:

{-# 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 ys@(viewl -> (y:<ys'))
 = case cmp x y of
     GT -> y <| insertBy cmp x ys'
     _  -> x <| ys