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

In this list, all the common tails are *shared*, recursively; this is
not 24x4 list (cons) cells in memory, but rather less.

--KW 8-)

More information about the Haskell-Cafe mailing list