[Haskell-cafe] Re: OCaml list sees abysmal Language Shootoutresults

[Keith Wansbrough]

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