-- 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
-}