[Haskell-cafe] lazy skip list?

[Felipe Lessa]

On Fri, Aug 20, 2010 at 3:57 AM, Luke Palmer <lrpalmer at gmail.com> wrote:
> On Thu, Aug 19, 2010 at 9:57 PM, Felipe Lessa <felipe.lessa at gmail.com> 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.