haskell: a data structure for storing ascending integers with a very fast lookup

Question

Hello!

(This question is related to my previous question, or rather to my answer to it.)

I want to store all qubes of natural numbers in a structure and look up specific integers to see if they are perfect cubes.

For example,

cubes = map (\x -> x*x*x) [1..]
is_cube n = n == (head $ dropWhile (<n) cubes)

It is much faster than calculating the cube root, but It has complexity of O(n^(1/3)) (am I right?).

I think, using a more complex data structure would be better.

For example, in C I could store a length of an already generated array (not list - for faster indexing) and do a binary search. It would be O(log n) with lower сoefficient than in another answer to that question. The problem is, I can't express it in Haskell (and I don't think I should).

Or I can use a hash function (like mod). But I think it would be much more memory consuming to have several lists (or a list of lists), and it won't lower the complexity of lookup (still O(n^(1/3))), only a coefficient.

I thought about a kind of a tree, but without any clever ideas (sadly I've never studied CS). I think, the fact that all integers are ascending will make my tree ill-balanced for lookups.

And I'm pretty sure this fact about ascending integers can be a great advantage for lookups, but I don't know how to use it properly (see my first solution which I can't express in Haskell).

Answer 1

Several comments:

• If you have finitely many cubes, put them in Data.IntSet. Lookup is logarithmic time. Algorithm is based on Patricia trees and a paper by Gill and Okasaki.

• If you have infinitely many cubes in a sorted list, you can do binary search. start at index 1 and you'll double it logarithmically many times until you get something large enough, then logarithmically many more steps to find your integer or rule it out. But unfortunately with lists, every lookup is proportional to the size of the index. And you can't create an infinite array with constant-time lookup.

With that background, I propose the following data structure:

A sorted list of sorted arrays of cubes. The array at position i contains exp(2,i) elements.

You then have a slightly more complicated form of binary search. I'm not awake enough to do the analysis off the top of my head, but I believe this gets you to O((log n)^2) worst case.

Answer 2

You can do fibonacci-search (or any other you wuld like) over lazy infinite tree:

data Tree a = Empty
            | Leaf a
            | Node a (Tree a) (Tree a)

rollout Empty = []
rollout (Leaf a) = [a]
rollout (Node x a b) = rollout a ++ x : rollout b

cubes = backbone 1 2 where
    backbone a b = Node (b*b*b) (sub a b) (backbone (b+1) (a+b))

    sub a b | (a+1) == b = Leaf (a*a*a)
    sub a b | a == b = Empty
    sub a b = subBackbone a (a+1) b

    subBackbone a b c | b >= c = sub a c
    subBackbone a b c = Node (b*b*b) (sub a b) (subBackbone (b+1) (a+b) c)

is_cube n = go cubes where
    go Empty = False
    go (Leaf x) = (x == n)
    go (Node x a b) = case (compare n x) of
                          EQ -> True
                          LT -> go a
                          GT -> go b