[Haskell-cafe] lazy skip list?
felipe.lessa at gmail.com
Fri Aug 20 08:24:14 EDT 2010
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?
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.
More information about the Haskell-Cafe