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

Keith Wansbrough Keith.Wansbrough at cl.cam.ac.uk
Fri Oct 8 09:42:28 EDT 2004

```> 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"