blob: 727dfc5859a52b484abb0c14349e0af83e991af1 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE MagicHash #-}
module T13027 (insert) where
import GHC.Exts (isTrue#, reallyUnsafePtrEquality#)
data Set a = Bin {-# UNPACK #-} !Size !a !(Set a) !(Set a)
| Tip
type Size = Int
insert :: Ord a => a -> Set a -> Set a
insert = go
where
go :: Ord a => a -> Set a -> Set a
go !x Tip = Bin 1 x Tip Tip
go !x t@(Bin sz y l r) = case compare x y of
LT | l' `ptrEq` l -> t
| otherwise -> undefined -- balanceL y l' r
where !l' = go x l
GT | r' `ptrEq` r -> t
| otherwise -> undefined -- balanceR y l r'
where !r' = go x r
EQ | x `ptrEq` y -> t
| otherwise -> Bin sz x l r
{-# INLINABLE insert #-}
ptrEq :: a -> a -> Bool
ptrEq x y = isTrue# (reallyUnsafePtrEquality# x y)
{-# INLINE ptrEq #-}
|
