-- Reflection without Remorse
-- http://homepages.cwi.nl/~ploeg/papers/zseq.pdf
-- https://github.com/atzeus/reflectionwithoutremorse

-- try implement diff list

type DiffList a = [a] -> [a]

absFromDiffList :: DiffList a -> [a] -- original name = abs
absFromDiffList a = a []

rep :: [a] -> DiffList a
rep = (++)

(+++) :: DiffList a -> DiffList a -> DiffList a
(+++) = (.)

list = replicate 10000 'a'

normalList = replicate 1000 list -- [l1, list2, list3, ..., listn]
diffList   = map rep normalList  -- [(++ list1), (++ list2), (++ list3), ..., (++ listn)]

normalListLeftLength = length $ foldl1 (++) normalList
-- length $ list1 ++ list2 ++ list3 ++ ... ++ listn
-- length $ ((list1 ++ list2) ++ list3) ++ ... ++ listn -- left associated
--
normalListRightLength = length $ foldr1 (++) normalList
-- length $ list1 ++ list2 ++ list3 ++ ... ++ listn
-- length $ (list1 ++ (list2 ++ (list3 ++ ... ++ listn))) -- right associated

diffListLeftLength   = length $ absFromDiffList $ foldl1 (+++) diffList
-- length $ absFromDiffList $ (++ list1) +++ (++ list2) +++ (++ list3) +++ ... +++ (++ listn)
-- length $ absFromDiffList $ (((++ list1) +++ (++ list2)) +++ (++ list3)) +++ ... +++ (++ listn)
-- length $ absFromDiffList $ ((((++ list1) . (++ list2)) . (++ list3)) . ... . (++ listn) -- (++ list1)) = \x -> list1 ++ x
-- length $ absFromDiffList $ (++ (list1 ++ (list2 ++ (list3 ++ (...)))))
-- length $ (++ (list1 ++ (list2 ++ (list3 ++ (...))))) []
-- length $ (list1 ++ (list2 ++ (list3 ++ (...)))) ++  []
-- length $ ((list1 ++ (list2 ++ (list3 ++ (...)))) ++  []) -- right associated

diffListRightLength   = length $ absFromDiffList $ foldr1 (+++) diffList
-- length $ absFromDiffList $ (++ list1) +++ (++ list2) +++ (++ list3) +++ ... +++ (++ listn)
-- length $ absFromDiffList $ ((++ list1) +++ ((++ list2) +++ ((++ list3) +++ ... +++ (++ listn))))
-- length $ absFromDiffList $ ((++ list1) . ((++ list2) . ((++ list3) . ... . (++ listn))))
-- length $ absFromDiffList $ (++ (list1 ++ (list2 ++ (list3 ++ (...)))))
-- length $ (++ (list1 ++ (list2 ++ (list3 ++ (...))))) []
-- length $ ((list1 ++ (list2 ++ (list3 ++ (...)))) ++  []) -- right associated


-- normalListRightLength -- ok
-- normalListLeftLength  -- slowly
-- diffListLeftLength    -- ok
-- diffListRightLength   -- ok