Re: [Haskell-cafe] lazy skip list?

On Fri, Aug 20, 2010 at 3:57 AM, Luke Palmer wrote:

On Thu, Aug 19, 2010 at 9:57 PM, Felipe Lessa wrote:

...

However, I haven't thought about how operations such as 'cons' and 'tail' would be implemented =).  OP just asked about indexing ;-).

Well if all you need is indexing, then an integer trie does it, right?  http://hackage.haskell.org/package/data-inttrie

Probably! More specifically, newtype SkipList a = (Int, IntTrie a) index :: SkipList a -> Int -> Maybe a index i (n, t) = if i < n && i >= 0 then Just (apply t i) else Nothing However, with the API exposed in data-inttrie it isn't posssible to implement fromList/toList in time O(n), only O(n log n), assuming that modify/apply are O(log n). Worse yet, if we wanted our fromList to work with infinite lists we would need to do something like import Data.List (genericLength) import Number.Peano.Inf (Nat) -- from peano-inf on Hackage newtype SkipList a = (Nat, IntTrie a) fromList :: [a] -> SkipList a fromList xs = (genericLength xs, fmap (xs !!) identity) The problem here is that 'fromList' is now O(n²). If IntTrie exposed an Traversable interface, I think it would be possible to write a 'fromList' in O(n) using a state monad. However, I don't know if it is possible to write a Traversable interface in the first place. Cheers! =) -- Felipe.