Container: Folgen (II)

benutzt Prelude.[]:

binsert :: Ord a => a -> [a] -> [a]
binsert x xs =
    if null xs then [x] else
    let ( pre, mid : post ) = 
            splitAt ( div (length xs) 2 ) xs
    in  if x < mid
        then binsert x pre ++ mid : post
        else pre ++ mid : binsert x post
        
bisort :: Ord a => [a] -> [a]             
bisort = foldr binsert []

benutzt Data.Sequence.Seq:

import Data.Sequence ( Seq )
import qualified Data.Sequence as S
binsert :: Ord a => a -> Seq a -> Seq a
binsert x xs =
    if S.null xs then S.singleton x else
    let ( pre, midpost ) = 
            S.splitAt ( div (S.length xs) 2 ) xs
        mid S.:< post = S.viewl midpost
    in  if x < mid
        then binsert x pre S.>< midpost        
        else pre S.>< mid S.<| binsert x post
bisort :: Ord a => [a] -> Seq a
bisort = foldr binsert S.empty

Bemerkungen:

• Testfall: bisort $ reverse [1 .. 10000]
• diese Funktion bisort ist wirklich nur ein Test. Wenn es nur um das Einfügen in geordnete Listen geht, dann sollte man von Anfang an einen Suchbaum verwenden.