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

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

T>>Бесконечный список можно заменить на любую другую бесконечную структуру, это несложно.

К>А разреженный список как сделать без State?

data T = T String deriving Show

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

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

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

Результаты:

*Main> fetchCache 2048
T "2048"
(0.02 secs, 0 bytes)
*Main> fetchCache 8192
T "8192"
(0.00 secs, 0 bytes)
*Main> fetchCache 32768
T "32768"
(0.00 secs, 0 bytes)
*Main> fetchCache 131072
T "131072"
(0.00 secs, 0 bytes)
*Main> fetchCache 131071
T "131071"
(0.03 secs, 6414520 bytes)
*Main> fetchCache 262144
T "262144"
(0.00 secs, 264588 bytes)
*Main> fetchCache 524288
T "524288"
(0.00 secs, 266712 bytes)
*Main> fetchCache 524287
T "524287"
(0.33 secs, 19143472 bytes)
*Main>

Вот кэш:

*Main> take 5 cache
[[T "1"],[T "2",T "3"],[T "4",T "5",T "6",T "7"],[T "8",T "9",T "10",T "11",T "1
2",T "13",T "14",T "15"],[T "16",T "17",T "18",T "19",T "20",T "21",T "22",T "23
",T "24",T "25",T "26",T "27",T "28",T "29",T "30",T "31"]]

Видно, что вычисление первых элементов в подсписке дешево, последних дорогое.

По идее, лучше сделать по твоей мысли с бесконечным деревом, где левая половина содержит данные для base..base*2-1, правая — все остальные.

Вот, я и код написал:

data T = T String deriving Show

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

data C a = N a | C (C a) (C a)    -- left subtree is finite, right subtree - infinite

mapC f (N a) = N $ f a
mapC f (C a b) = C (mapC f a) (mapC f b)

cache = mapC fromInt $ heap 1 1
    where
        heap ofs base = C (c ofs (ofs+base-1)) (heap base2 base2)
            where
                base2 = base*2
        c from to
            | from == to = N from
            | otherwise = C (c from mid) (c (mid+1) to)
            where
                mid = div (to+from) 2

showC 0 _ = "..."
showC n (N x) = "(N "++show x++")"
showC n (C l r) = "(C "++showC (n-1) l++" "++showC (n-1) r++")"

fetchCache i = findLeaf offset (offset*2-1) left
    where
        findLeft ofs (C l r)
            | i >= ofs*2 = findLeft (ofs*2) r
            | otherwise = (ofs,l)
        (offset,left) = findLeft 1 cache
        findLeaf from to (N x) = x
        findLeaf from to (C l r)
            | i > mid = findLeaf (mid+1) to r
            | otherwise = findLeaf from mid l
            where
                mid = div (from+to) 2

А вот результаты работы:

*Main> fetchCache 4
T "4"
(0.02 secs, 266976 bytes)
*Main> fetchCache 7
T "7"
(0.02 secs, 530516 bytes)
*Main> fetchCache 15
T "15"
(0.00 secs, 266952 bytes)
*Main> fetchCache 31
T "31"
(0.00 secs, 530028 bytes)
*Main> fetchCache 142
T "142"
(0.00 secs, 267172 bytes)
*Main> fetchCache 284
T "284"
(0.00 secs, 531596 bytes)
*Main> fetchCache 10000
T "10000"
(0.00 secs, 268288 bytes)
*Main> fetchCache 100000
T "100000"
(0.00 secs, 533580 bytes)
*Main>

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

Чудеса!

T>>Добавлю, что rand с типом rand :: RndState -> (Int,RndState) может быть сконвертирован в бесконечный список псевдослучайных чисел типа Int, с которым работать достаточно удобно, например, обычной сверткой.

К>Задумался над тем, как унифицировать монады State и List применительно к рандому.

Боюсь, не удастся.