Здравствуйте, thesz, Вы писали:

T>data T = T String deriving Show

T>toInt (T s) = (read s)::Int
T>fromInt i = T $ show i

T>cache =
T>    map (map fromInt)
T>    $ map (\(f,t) -> [f..t-1])
T>    $ iterate (\(a,b) -> (b,b*2)) (1,2)

T>fetchCache i = take 1 i cache
T>    where
T>        take ofs 1 (xs:_) = xs !! (i-ofs)
T>        take ofs n (_:xss) = take (ofs*2) (div n 2) xss

T>Память зря не расходуется, время не растет.
T>Чудеса!

Интересно, что эффективнее — настоящая двоичная куча, или твоя двухэтажная структура?
Конечно, двухэтажная красивее и проще: не вводим никаких новых типов. И расплачиваемся линейным поиском на втором этаже...