Actually, I've been wondering about this. If my understanding is correct, Haskell lists are basicly singly-linked lists of cons cells (is that correct?) A simple (I think) thing to do would be to make the lists doubly-linked and circular. That would let us do nice things like have O(1) primops for reverse, tail, (++) and other things that access lists at the end. However, I'm still pretty new to FP in general, so I don't know if there are any theoretical reasons why something like this couldn't work.
x = [3,5,7] primes = 2:x odds = 1:x You can't do sharing like this if your lists are doubly-linked; lots of cool algorithms depend on this sharing. -- first-arg-reversed-then-args-flipped append revApp :: [a] -> [a] -> [a] revApp = foldr (flip (.) . (:)) id -- all insertions of a into ys, with prefix (rev xs) allinserts :: [a] -> a -> [a] -> [[a]] -> [[a]] allinserts xs a [] = (:) (revApp xs [a] ) allinserts xs a ys0@(y:ys) = (:) (revApp xs (a:ys0)) . allinserts (y:xs) a ys -- all permutations of a list allperms :: [a] -> [[a]] allperms = foldr (\ x -> foldr (allinserts [] x) []) [[]]
allperms "abcd" ["abcd","bacd","bcad","bcda","acbd","cabd","cbad","cbda","acdb","cadb","cdab","cdba","abdc","badc","bdac","bdca","adbc","dabc","dbac","dbca","adcb","dacb","dcab","dcba"]
In this list, all the common tails are *shared*, recursively; this is not 24x4 list (cons) cells in memory, but rather less. --KW 8-)