Oh, an example: *Main> fromList [1..8] :: SkipList Z Int Cons (Branch 1 1 None None) (Cons (Branch 3 2 (Branch 1 3 None None) (Branch 1 4 None None)) (Cons (Branch 4 5 (Branch 3 6 (Branch 1 7 None None) (Branch 1 8 None None)) None) Empty)) *Main> fromList [1..8] :: SkipList (S Z) Int Cons (Branch 3 1 (Branch 1 2 None None) (Branch 1 3 None None)) (Cons (Branch 5 4 (Branch 3 5 (Branch 1 6 None None) (Branch 1 7 None None)) (Branch 1 8 None None)) Empty) *Main> fromList [1..8] :: SkipList (S (S Z)) Int Cons (Branch 7 1 (Branch 3 2 (Branch 1 3 None None) (Branch 1 4 None None)) (Branch 3 5 (Branch 1 6 None None) (Branch 1 7 None None))) (Cons (Branch 1 8 None None) Empty) *Main> let x = fromList [1..8] :: SkipList Z Int *Main> toList x [1,2,3,4,5,6,7,8] *Main> x `index` 3 Just 4 *Main> x `index` 8 Nothing Cheers! =) -- Felipe.

On Fri, Aug 20, 2010 at 12:49 AM, Ivan Lazar Miljenovic wrote:

How about fromList [1..] like Evan's original email had (which I think is going to be a problem here as well)?

The only "problem" is that the Element's sizes will be forced up to the point you need, but not anymore. *Main> (fromList [1..] :: SkipList Z Int) `index` 100 Just 101 Probably this small problem could be removed if the code was polished. Alas, the idea is simple. Each 'Element' contains up to 2^(s-1) data. For example, with an 'Element Z a' you can't store anything. With an 'Element (S Z) a' you may store zero or one datum. With an 'Element (S (S Z)) a', you may store between 0 and 4 data, and so forth. Then we just create an SkipList so that the Elements have an increasing capacity. When you 'Cons', the 'Element' of tail of the SkipList will have twice more capacity than the 'Element' of the head. However, I haven't thought about how operations such as 'cons' and 'tail' would be implemented =). OP just asked about indexing ;-). Cheers! =D -- Felipe.

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

Hah, serves me right I suppose. I figured the promise of some type fanciness would be catnip to some well-typed cats out there, but your implementation is even more advanced than I expected. I'll have to squint at it a while to figure out how it works and how the usual list ops could be implemented. Thanks for giving me something to chew on! And thanks too for the example of how to write a showsPrec, I hadn't figured that out yet!

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.

On Sat, Aug 21, 2010 at 6:52 PM, Michael D. Adams wrote:

Could you be more specific about what operations you want and their properties (e.g. performance laziness, etc.)?  For example, do you need to be able to cons onto the front or is the list generated once and never consed onto?  Do you need to be able to insert/remove elements from the middle?  Do you need the tail sharing property that regular cons lists have?

Good questions. It's just generated in one long iterative process (as a complex but lazy transformation of another long list), and then I want to seek to various points and read sequentially (think about music, seeking to a particular spot and then playing). Sections are then recomputed and spliced in (i.e., if you modify a bit of music in the middle, it recomputes that range of time and splices it in). The laziness is that I don't want to compute too far into the future, and it will be common to recompute the entire tail, but never actually need that tail before it needs to be tossed and recomputed again. Currently, I think I've solved my problem by just using a list of chunks. I already use the chunks as the units of recomputation, and since each one accounts for n seconds, seeking to a particular spot or replacing a chunk out of the middle should be plenty fast with a plain list. If each chunk is 5 sec, 3 hours of music is still only a list of 2160 elements, and '[0..] !! 2160' is basically instant. It looks like I need to get up to around 5120000 or so before I can even notice the delay, in plain old interpreted ghci. Lists are fast!