filter f [] = []
filter f [x] = if f x then [x] else []
filter f (x:xs) = let (x',xs') = filter f [x] ||| (filter f xs) in x'++xs'

map f [] = []
map f [x] = f x
map f (x:xs) = let (x',xs') = f x ||| (map f xs) in x':xs'

{-
	-- Not actually better

tabulateAux f l r | (r - l) < 1 = []
				  | otherwise = let mid = div (r + l) 2
									(l',r') = tabulateAux f l mid ||| tabulateAux f (mid+1) r
								in l' ++ [f mid] ++ r'

tabulate f n | n <= 0 = []
			 | otherwise = tabulateAux f 0 n

			 -}

tabulateAux f i n | i == n 	  = []
				  | otherwise = let (l,r) = (f i) ||| (tabulateAux f (i+1) n) in l:r

tabulate f n | n <= 0 = []
			 | otherwise = tabulateAux f 0 n


showt [] = EMPTY
showt [x] = ELT x
showt s  = 	let mid = div (length s) 2
				(l,r) = take mid s ||| drop mid s
			in NODE l r

showl [] = NIL
showl (x:xs) = CONS x xs

join = concat

contraer f [] = []
contraer f [x] = [x]
contraer f (x:y:xs) = let (x':xs') = f x y ||| contraer f xs in x':xs'

reduce f e [] = e
reduce f e [x] = x
reduce f e s@(x:y:xs) = reduce f e (contraer f s)

expansion f [] _ = []
expansion f _ [] = []
expansion f (x:xs) [y] = x : [f x y]
expansion f (x:xs) (y:y':ys) = x : (f x y) : expansion f xs ys

scan f e [] = ([],e)
scan f e [x] = ([x],e)
scan f e s = let (l,h) = scan f e (contraer f s) in (expansion f l s,h)