module Template_11(testA, testB, testC) where

-- instead of the import, we here copied the relevant functions
-- of module OList_09

data OList a = OList [a] deriving Eq

insert :: Ord a => a -> OList a -> OList a
insert x o@(OList xs) = case span (< x) xs of
  (first, []) -> OList $ first ++ [x]
  (first, y : last) -> OList $ first ++ [x | x /= y] ++ y : last

empty :: OList a
empty = OList []

instance Show a => Show (OList a) where
  show (OList []) = "{}"
  show (OList xs) = ("{" ++) . drop 2 $ foldr
    (\ y s -> ", " ++ show y ++ s)
    "}" xs


-- Exercise 1 

{-
You can (but do not have to) upload your step by step evaluations 
by adding them in this comment.



-}

-- Exercise 2

applyIndefinitely :: undefined
applyIndefinitely = undefined

infDigits :: [Int]
infDigits = applyIndefinitely undefined undefined

fromListA :: Ord a => [a] -> OList a
fromListA [] = empty
fromListA (x : xs) = insert x (fromListA xs)

fromListB :: Ord a => [a] -> OList a
fromListB = flb empty
flb s [] = s
flb s (x : xs) = flb (insert x s) xs

fromListC :: Ord a => [a] -> OList a
fromListC = undefined
   
   


numberInsertions = 2 * 10^6
testList = take numberInsertions infDigits

testA, testB, testC :: String
testA = show $ fromListA testList
testB = show $ fromListB testList
testC = show $ fromListC testList