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

VD>Ага щас блин. А разные ансэйфперформио и т.п.?

Ага ансейфперформио я и забыл. Интересно, есть ли поименованное подмножетство Хаскелль без него (оно в стандарт входит)?

КЛ>че то меня начинает раздражать эта мода на "чистую" функциональщину. Эдакий гламур в программинге, от которого в чистом виде нету ничего хорошего.

Кто сказал, что ничего хорошего?

J>1. Допустим мы имеем функцию f(arg), которая детерминирована, делает свою работу и делает её медленно. Мы хотим приделать кэш вызовов. Собственно вопрос, где хранить состояние — тот самый кэш?

Одно вычисление

x=f arg

будет вычислено не более, чем один раз. Это тебе гарантирует семантика языка с ленивым порядком вычислений.

Если нам нужен именно кэш, то два варианта: запихнуть все это дело в монаду состояния с отображением

Map ArgType ArgResult

или сделать отображения

fromInt :: Int -> ArgType

и

toInt :: ArgType -> Int

, сделать (бесконечный) список результатов

results = map (f . fromInt) [1..]

и выбирать из него путем

cachedResult arg = results !! toInt arg

.

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

J>2. Как возможно определить и вообще работать с явно недетерминированными функциями типа rand()?

Про rand тебе уже объяснили.

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

PS
Тех, кто говорят, что нет языков без состояния, не слушай. Они все еще не научились абстрактному мышлению.

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

VD>>В любмо случае языков без побочных эффектов тоже небывает. Тот же Хаскель содержит опасные манады.

К>Влад, можно пояснить, что ты подразумеваешь под выделенным? Откуда взят этот термин?

Штука, которая называется таким страшным словом не может быть безопасной

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

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

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

Я так понимаю,

results = map f [1..]
x = (results !!) $! 10000

Немедленно родит заготовку списка из 10000 конструкторов (, содержащих 9999 ленивых f$k, 1 вычисленное f$!10000 и 1 ленивое map f [10001..]

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

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

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

[]

T>PS
T>Тех, кто говорят, что нет языков без состояния, не слушай. Они все еще не научились абстрактному мышлению.

Только они нафиг никому не упали. Или вы вводите дополнительный аргумент к каждой функции — время t?

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

Data.Map

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

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

BZ>Data.Map

Каким способом? Если задействовать fromList***, то всё равно получится туча заготовок.

Может быть, логарифмически, на бесконечной двоичной куче?

data Heap v = HeapNode v (Heap v) (Heap v)

buildHeap :: (Num n) => (n -> v) -> Heap v
buildHeap f = build' 0 where
    build' n = HeapNode (f n) (build' (n*2)) (build' (n*2+1))

lookupHeap :: (Num n) => Heap v -> n -> v
lookupHeap (HeapNode v _ _) 0 = v
lookupHeap (HeapNode _ l r) n = lookup (if even n then l else r) (n `div` 2)


results = buildHeap f
fn = lookupHeap results n

Я что-то не понял, как конструировать подобную структуру с помощью Map...

К>Может быть, логарифмически, на бесконечной двоичной куче?

здесь ты абсолютно прав

BZ>>Data.Map
К>Каким способом? Если задействовать fromList***, то всё равно получится туча заготовок.

а здесь я просто не в курсе — нало разбираться как оно строится, но вероятно хорошо не получится. было бы интересно иметь функцию, которая строит Map непосредственно из функции, занимаясь просто memoization её значений

ты читал дисер "Purely functional data structures" by Chris Okasaki? там излагается концепция амортизированного времени выполнения операций над lazy data structures. не то чтобы это один-в-один то, что тебя сейчас интересует, но книжка весьма основополагающая

T>>PS
T>>Тех, кто говорят, что нет языков без состояния, не слушай. Они все еще не научились абстрактному мышлению.
КЛ>Только они нафиг никому не упали. Или вы вводите дополнительный аргумент к каждой функции — время t?

Мне нравятся. Я их использую с большим успехом.

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

К>Здравствуйте, 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 применительно к рандому.

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

VD>>Ага щас блин. А разные ансэйфперформио и т.п.?
no4>Ага ансейфперформио я и забыл. Интересно, есть ли поименованное подмножетство Хаскелль без него (оно в стандарт входит)?

unsafePerformIO часть библиотеки. В стандарты 1.4 и H98 не входит. В стандарт де-факто под названием "реализация Хаскеля ghc" — входит.

В реальной жизни не используется.

J>>Т.е. реализовать ручное кэширование в случае необходимости будет невозможно?
DD>Просто насколько я понимаю, для ленивого языка, коим является Haskell, само понятие "кэширование результатов вызова функции" является неприменимым, т.к. мы не знаем, в какой точно момент понадобится результат вычисления, и соответственно, когда этот результат будет вычислен. В принципе, можно получить желаемый результат, путем strict вычисления нужной функции, но вот нужно ли это...

Кто-то что-то путает.

И это точно не я.

Хаскель — чистофункциональный язык с ленивой семантикой. Оных бывает две штуки — call-by-name, вычислять столько раз, сколько попросят, возможно, более одного раза, и call-by-need — вычислять не более одного раза.

Соответственно, в вызове f x x вычисление x будет выполнено не более одного раза в call-by-need семантике.

Кэширование на ровном месте.

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

[]

T>Мне нравятся. Я их использую с большим успехом.

Насколько мне позволяет мой императивный мозг, состояние — это совйства объекта в конкретный момент времени t. Если эти свойства не зависят от этого t, то состояние то и не нужно. Но разве так бывает? А когда не бывает, как вы выкручиваетесь?

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

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

КЛ>[]

T>>Мне нравятся. Я их использую с большим успехом.

КЛ>Насколько мне позволяет мой императивный мозг, состояние — это совйства объекта в конкретный момент времени t. Если эти свойства не зависят от этого t, то состояние то и не нужно. Но разве так бывает? А когда не бывает, как вы выкручиваетесь?

А мы как-то без объектов обходимся
Мороки с ними, писанины...

Здравствуйте, 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>Чудеса!

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