[<<][meta][>>][..]

Merging lists: recovering tail sharing

Take two lists, establish their common tail, add head of first to
second list.  Is there a Haskell function for this?

A different datastrucure might help: length-annotated lists, as this
can prune the search tree; i.e. two lists cannot be equal if their
lengths are not equal.


import Data.List 
import System.IO.Unsafe
import System.Mem.StableName


refEq a b = unsafePerformIO $ do
              a' <- makeStableName a
              b' <- makeStableName b
              return (a' == b')

type TaggedList a = [(Int, a)]

taggedCons = f where
    f x [] = [(0 :: Int, x)]
    f x txs@((n,_):_) = (n+1,x) : txs

taggedList = foldr taggedCons [] 

taggedTail = f where
    f as [] = []
    f [] bs = []
    f as bs | as `refEq` bs = as             -- found tail
    f a@((na,_):as) b@((nb,_):bs)
      | na == nb = f as bs                   -- same length => recurse
      | na > nb  = f (drop (na - nb) as) bs  -- diff length: drop heads
      | na < nb  = f as (drop (nb - na) bs)



Problem: this might rebase a lot though.  Maybe sharing should be done
in a functional representation anyway?



[Reply][About]
[<<][meta][>>][..]