Estaba confundido por la falta de estas funciones en la interfaz para el tipo de secuencia, ya que Data.List proporciona estas funciones. ¿Hay un problema de eficiencia aquí o es solo la falta de demanda de estas funciones?¿Por qué Data.Sequence no tiene `insert 'o` insertBy', y cómo los implemento de manera eficiente?
Y como no forman parte de Data.Sequence, ¿cómo puedo implementarlos eficientemente para mis propósitos?
Esto es lo que ocurrió:
> 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]
o simplemente puede imitar la versión de listas:
{-# 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
Supongo que sería esencialmente tan rápido como el método más rápido. Voy a marcar esta respuesta como correcta, porque me acabo de dar cuenta de que necesito más que Secuencia, necesito aplicar lo invariante de que la secuencia siempre está ordenada, de modo que puedo hacer la inserción en el tiempo O (log n) en lugar de O (n) tiempo – danharaj
@danharaj, considerado Data.Set? – luqui
@luqui, tengo, pero mi pedido cambia durante el curso del algoritmo que estoy implementando, Bentley-Ottmann como referencia. Como la relación de orden cambia, no puedo usar Data.Set. Sin embargo, el orden cambia de una manera conducida, por lo que una búsqueda binaria es el camino a seguir. – danharaj
No es tan completo como 'Data.List', pero la interfaz de Secuencia depende en gran medida de las clases de tipos. 'map' from' Functor', 'fold' from' Foldable', etc. También puede usar ListLike, http://hackage.haskell.org/package/ListLike, que tiene una instancia para el tipo de secuencia y le daría una interfaz mucho más completa, que incluye 'insert' y' insertBy'; Creo que la interfaz es la misma que el segundo ejemplo de Mikhail. –