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