-- a type for lists: functions from lists to lists

type FList a = [a] -> [a]


-- conversions between lists and flists and back again

flist :: [a] -> FList a
flist xs = (xs++)

list :: FList a -> [a]
list = ($[])


-- slightly less efficient, but equivalent flist converters

flist2, flist3, flist4 :: [a] -> FList a
flist2 = foldr       cons  nil
flist3 = foldl (flip cons) nil
flist4 = foldr       cons' nil'



-- several variations on cons and nil

cons, cons' :: a -> FList a -> FList a
cons  x = ((x:).)
cons' x xs ys = x : (xs ys)

nil, nil' :: FList a
nil  = id
nil' xs = xs


-- append and concatenate, FList style

app :: FList a -> FList a -> FList a
app = (.)

conc :: [[a]] -> [a]
conc = list . foldl app nil . map flist



-- some testing stuff, including the "bad" version of concat

conc' = foldl (++) []

test c = length (c ws)
         where ws = replicate 100 "foo"

tl f = length (list (f [1..100]))



data Tree a = Node a (Tree a) (Tree a) | Tip

tree 0 = Tip
tree n = Node '.' t t where t = tree (n-1)

try t p = length (p t)

t4  = tree 4
t5  = tree 5
t8  = tree 8
t12 = tree 12
t16 = tree 16
t18 = tree 18
t6  = tree 6
t7  = tree 7
t2  = tree 2
t3  = tree 3


prt Tip = ""
prt (Node x y z) = prt y ++ [x] ++ prt z

prt' = list . p 
        where p  Tip         = id
              p (Node x y z) = p y . (x:) . p z

pr = flip px ""
     where px  Tip         a = a
           px (Node x y z) a = px y (x : px z a)

pr' = flip px ""
      where px  Tip         = id
            px (Node x y z) = px y . (x:) . px z

pq = px ""
     where px a  Tip         = a
           px a (Node x y z) = px (x : px a z) y



{-

	n		len		prt		pr		prt'
	
	4		15		263		202		252
	8		255		3939	2406	3174
	16		65K		1.24M	590K	787K
	18		262K	5.24M	2.36M	3.15M


	n		len		prt			pq			savings
	
	2		3		50			40			20 %
	3		7		102			76			25 %
	4		15		210			148			30 %
	5		31		434			292			33 %
	6		63		898			580			35 %
	7		127		1858			1156			38 %
	8		255		3842			2308			40 %
	16		65K		1245186		589828		53 %
	18		262K		5242882		2359300		55 %
	
			2^n-1	??				9*len+13

-}