Łamanie danych. Integralność zestawu bez uogólnionej obsługi nowego typu
Poniższy kod używa niebezpiecznegoGeneralizedNewtypeDeriving
przedłużenie do zerwaniaData.Set
wstawiając różne elementy z różnymiOrd
instancje:
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
import Data.Set
import System.Random
class AlaInt i where
fromIntSet :: Set Integer -> Set i
toIntSet :: Set i -> Set Integer
instance AlaInt Integer where
fromIntSet = id
toIntSet = id
newtype I = I Integer deriving (Eq, Show, AlaInt)
instance Ord I where compare (I n1) (I n2) = compare n2 n1 -- sic!
insert' :: Integer -> Set Integer -> Set Integer
insert' n s = toIntSet $ insert (I n) $ fromIntSet s
randomInput = take 5000 $ zip (randomRs (0,9) gen) (randoms gen) where
gen = mkStdGen 911
createSet = Prelude.foldr f empty where
f (e,True) = insert e
f (e,False) = insert' e
main = print $ toAscList $ createSet randomInput
Kod jest drukowany[1,3,5,7,8,6,9,6,4,2,0,9]
. Zauważ, że lista jest nieuporządkowana i ma9
dwa razy.
Czy możliwe jest wykonanie tego słownikowego ataku wymiany przy użyciu innych rozszerzeń, np.ConstraintKinds
? Jeśli tak, możeData.Set
zostać przeprojektowany, aby był odporny na takie ataki?