OffsetOp.hs

module OffsetOp where
import Data.List

-- The function condense takes a list of pairs. The second value of
-- each pair denotes either a delete or skip action. The delete action
-- says that the next item in the list is to be discarded, and will
-- not appear in the result list. Skip actions do nothing.

--     1-skip 2-del 3-skip ->  1-skip 2-del

-- We cannot delete an item before its action is applied.

--     1-skip 2-del 3-del 4-skip -> 1-skip 2-del 

data Action = Del | Skip deriving (Show,Eq)
type UID = Int
type Item = (UID, Action)
type AList = [Item]

condense :: AList -> AList
condense [] = []
condense [a] = [a]
condense (a@(_,Skip):cs) = a : condense cs
condense (a@(_,Del):cs) = a : tail (condense cs)


-- testing 
data Test = Test {before :: AList, after :: AList}

instance Show Test where
  show (Test be af) = show be ++ " " ++ show af

type Suite = [Test]

t1 = Test []  []
t2 = Test [(1,Skip)]  [(1,Skip)]
t3 = Test [(1,Del)]  [(1,Del)]
t4 = Test [(1,Skip),(2,Skip)]  [(1,Skip),(2,Skip)]
t5 = Test [(1,Del),(2,Skip)]  [(1,Del)]
t6 = Test [(1,Del),(2,Skip),(3,Skip)]  [(1,Del),(3,Skip)]
t7 = Test [(1,Del),(2,Del),(3,Skip),(4,Skip)]  [(1,Del),(4,Skip)]
suite = [t1,t2,t3,t4,t5,t6,t7]

check :: Test -> IO ()
check (Test be af) = print $ condense be == af

-- The next step will be to generalize this scheme for trees. A node
-- may delete its children, but only after arranging to take on all the
-- abandoned grandchildren.

main = do
  check t1
  check t2
  check t3
  check t4
  check t5
  check t6
  check t7
  print "ok"