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
Тех, кто говорят, что нет языков без состояния, не слушай. Они все еще не научились абстрактному мышлению.

J>Т.е. реализовать ручное кэширование в случае необходимости будет невозможно?

это можно сделать двумя способами:
— использовать lazy семантику вычисления. фактически, laziness — это само по себе система кеширования однажды вычисленных значений, надо просто уметь ею управлять
— использовать unsafePerformIO

что касается первого — вот типичный пример из базовой библиотеки GHC:

power x n | x==2 && (n>=0 && n<=317) = powers2!n
          | otherwise                = x^n

powers2 :: Array Int Double
powers2 = array (0,318) [2^n | n <- [0..317]]

благодаяр laziness, значения в массиве powers2 вычисляются только по необходимости и запоминаются. степени же, не включённые в этот массив, вычисляются каждый раз заново. для более сложных ключей аналогиынйм образом можно прменить Map или Trie

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

J>В чисто функциональном языке (возьмём для примера Хаскель) все переменные есть константы, функции детерминированы — результат вызова зависит только от её аргументов.

Хорошо бы ещё взять для примера ML — потому что один ленивый, второй энергичный. (Надо сказать, каждый из них умеет делать и то, и другое).

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

Есть три разных способа редукции выражений.
Какая-то там теорема Чёрча показывает, что все эти способы — возможно, за разное время (вплоть до бесконечного ), — приводят к одному результату.

f(x) = expr(....., x, ....., x, .....)  -- аргумент используется несколько раз
f(g()) -- подставим туда нечто вычисляемое

-- подставить копии (лямбда-исчисление на строках)
f(g())
= expr(....., g(), ....., g(), .....)

-- вычислить и подставить <ссылку на> результат (путь ML)
f(g())
= let v=g() in f(v)
= let v=g() in expr(....., v, ....., v, .....)

-- подставить ссылку на одно и то же ленивое значение (путь Haskell)
-- которое вычислится единожды, когда потребуется первый раз
f(g())
= expr(....., v, ....., v, .....) where v=g()

Поэтому ни в ML, ни в Haskell не нужно делать фанатичную мемоизацию.

Другое дело, что если написать

let
    x = g()
    y = g()
in f(x,y)

то компилятор+рантайм может догадаться, а может не догадаться, что x==y и, соответственно, выполнит редукцию g() единожды или дважды.
Вот тут уже нужно смотреть, стоит ли доверять интеллекту компилятора и объёму кэша рантайма, или переписать руками.

Говорят, что некоторые диалекты Пролога работают, как суперкомпьютер Крей-1: вычисляют бесконечный цикл за 6 секунд.

% Question of Life, Universe and Everything
qlue(X) :- qlue(X).
qlue(42).

?- qlue(N)
% благодаря мемоизации распознано зацикливание, и второй раз уже машина поехала по второй ветке
N=42
Yes

Хотя для большинства реализаций это не так.

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

Во-первых, можно предположить, что функция всё-таки детерминирована

rand :: RandSeed -> (Int, RandSeed)
srand :: Int -> RandSeed

r0 = srand 0
(x1,r1) = rand r0
(x2,r2) = rand r1

-- осталось только протащить нитку из последовательно вычисляемых r_k через все функции
-- например, 
randoms :: Int -> RandSeed -> ([Int], RandSeed)
randoms 0 r0 = ([],r0)
randoms n r0 =
    let
        (x,r1) = rand r0
        (xs,rn) = randoms r1
    in ((x:xs),rn)

(xs1,_) = randoms r2
(xs2,_) = randoms r2 -- новая серия (повторяет предыдущую)

Это подход монады State.

Во-вторых, недетерминированная функция — это функция со скрытым параметром World, природа которого не поддаётся расшифровке.
Монада IO в Хаскеле — это, по сути, монада State, только намертво засахаренная (чтобы нельзя было хакнуть вселенную и запустить два параллельных потока вычислений над копиями мира).

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

К>>то компилятор+рантайм может догадаться, а может не догадаться, что x==y и, соответственно, выполнит редукцию g() единожды или дважды.
К>>Вот тут уже нужно смотреть, стоит ли доверять интеллекту компилятора и объёму кэша рантайма, или переписать руками.

BZ>дело не в интеллекте. представь себе, что результат g() — список из миллиарда элементов, а f=(++) т.е. безопасно соптимизировать это можно только если x имеет примитивный тип (и следовательно его значение не превосходит по занимаемой памяти thunk для вычисления g() )

Вот именно, что в интеллекте.
Глупый рантайм — не мемоизирует вообще ничего, расходуя время.
Деятельно-глупый — мемоизирует всё подряд, расходуя память (и время тоже).
Умный — пребывает в дао, находя равновесие между крайностей.

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

no4>По-моему, чистый функциональный язык не тот, где нет состояние, а тот, где нет побочных эффектов.

Если есть состояние, то его надо менять. Изменение дает побочные эффекты.

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

no4>А IO монада в haskell, насколько я понял, состоит в том, что функция возвращает не состояние, а функуцию, которая для текущего состояние мира вычисляет действие с ним. А использование этой функции происходит за пределами языка haskell.

no4>Таким образом, они оба чистые.

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

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

A>>С такой сигнатурой:

A>>rand :: StateType -> (Int, StateType)
A>>

функция становится детерминированной. Если само значение состояния (типа StateType) нам не нужно, остается только его тип. Так получаются монады.

J>Интересно, а, например, в Clean нет никаких монад, и как там?

в clean каждая императивная операция получает и возвращает доп. аргумент, который рассматривается как "состояние мира"

монады сами по себе — это только способ декларации императивности. реализация же их либо использует тот же фокус с "состоянием мира" (в большинстве компиляторов), либо continuations (в hbc). почитай http://haskell.org/haskellwiki/IO_inside

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

[]

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

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

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

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

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

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

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

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

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


J>На своём пути к функциональному миру, читаю различные книжки, пока остаётся загадкой пара вопросов. Если можно, поясните.

J>В чисто функциональном языке (возьмём для примера Хаскель) все переменные есть константы, функции детерминированы — результат вызова зависит только от её аргументов.

J>1. Допустим мы имеем функцию f(arg), которая детерминирована, делает свою работу и делает её медленно.
в чистом ФП функция не может делать никакой работы. Это всего лишь декларация соответствия результата параметрам. Поэтому о скорости ее работы говорить не имеет смысла.
Это реализация делает некоторую работу по собственно вычислению всего, чего надо.
J>Мы хотим приделать кэш вызовов. Собственно вопрос, где хранить состояние — тот самый кэш?
Среда исполнения и должна решать, что такое кэш и что такое вызов.
Умные компиляторы ухитряются, к примеру, экономить вызовы при переборе чисел Фибоначчи, так, чтобы вместо O(2^n) каждое число отдавалось за О(1). Именно благодаря использованию чего-то вроде кэша вызовов.

J>2. Как возможно определить и вообще работать с явно недетерминированными функциями типа rand()?
Приходится вводить состояние. Функции типа rand на самом деле жестко детерминированы. В процедурном программировании состояние rand хранится в скрытой глобальной переменной; в ООП — в экземпляре ГСЧ. В ФП придется передавать состояние явно (либо воспользоваться монадами или еще каким-нибудь мега-способом): rand(current_state)->(random, next_state).

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

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

КЛ>[]

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

а мода на применение компьютеров уже не раздражает?

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

J>В чисто функциональном языке ...

Нет таких языков. Разве что лямбда исчисления Чёрча, но это не язык программирования.

Во всех остальных состояние в том или ином виде (зачастую очень завуалированном) есть. Кое что умеют делать компиляторы (оптимизировать). Где-то используется магия вроде монад.

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

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

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

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

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

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

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

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

КЛ>[]

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

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

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

На своём пути к функциональному миру, читаю различные книжки, пока остаётся загадкой пара вопросов. Если можно, поясните.

В чисто функциональном языке (возьмём для примера Хаскель) все переменные есть константы, функции детерминированы — результат вызова зависит только от её аргументов.

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

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

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

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

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

rand :: StateType -> (Int, StateType)

функция становится детерминированной. Если само значение состояния (типа StateType) нам не нужно, остается только его тип. Так получаются монады.

A>С такой сигнатурой:

A>rand :: StateType -> (Int, StateType)
A>

функция становится детерминированной. Если само значение состояния (типа StateType) нам не нужно, остается только его тип. Так получаются монады.

Интересно, а, например, в Clean нет никаких монад, и как там?

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

J>В чисто функциональном языке (возьмём для примера Хаскель) все переменные есть константы, функции детерминированы — результат вызова зависит только от её аргументов.

В чисто функциональном языке вообще нет переменных. Есть только именованные значения. Это сахар, вообще можно писать в чисто функциональном стиле на одних комбинаторах, но это не удобно

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

Как уже писал Sinclair, об этом должен заботиться компилятор. Причём, ИМХО, это должен делать не только компилятор, но и рантайм, который считает статистику вызовов и т.д., т.к. на этапе компиляци не всегда можно предсказать такие вещи.

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

Т.е. реализовать ручное кэширование в случае необходимости будет невозможно?

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


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

J>Т.е. реализовать ручное кэширование в случае необходимости будет невозможно?

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

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

порядок вычисления в хаскеле определён. недавно об этом рассказывали в cafe. способ вычисления — graph reduction, т.е. подставновка вместо левой части определения функции правой части. при этом вычисляется всегда самый наружный вызов, для которого уже достаточно данных

вот кусочек из моего письма:

simple example: consider evaluation of "head [1..]". [1..] may be
represented with the following recursive function:

list n = n:list n+1

so we have "head (list 1)" where head defined as

head (x:_) = x

let's evaluate expression:

head (list 1) =>
head (1:list 2) =>
1

as you see, "list 2" was just dropped during evaluation.


но лучше поглядеть в оригинале — там высказывались настоящие теоретики, не мне чета

К>Хорошо бы ещё взять для примера ML — потому что один ленивый, второй энергичный. (Надо сказать, каждый из них умеет делать и то, и другое).

по-моему, не столько делать, сколько эмулировать через всякие "состояния мира"

К>Другое дело, что если написать
К>

К>let
К>    x = g()
К>    y = g()
К>in f(x,y)
К>

К>то компилятор+рантайм может догадаться, а может не догадаться, что x==y и, соответственно, выполнит редукцию g() единожды или дважды.
К>Вот тут уже нужно смотреть, стоит ли доверять интеллекту компилятора и объёму кэша рантайма, или переписать руками.

дело не в интеллекте. представь себе, что результат g() — список из миллиарда элементов, а f=(++) т.е. безопасно соптимизировать это можно только если x имеет примитивный тип (и следовательно его значение не превосходит по занимаемой памяти thunk для вычисления g() )

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

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

J>>В чисто функциональном языке ...

VD>Нет таких языков. Разве что лямбда исчисления Чёрча, но это не язык программирования.

VD>Во всех остальных состояние в том или ином виде (зачастую очень завуалированном) есть.
VD>Кое что умеют делать компиляторы (оптимизировать). Где-то используется магия вроде монад.

По-моему, чистый функциональный язык не тот, где нет состояние, а тот, где нет побочных эффектов.
Побочный эффект, это что-либо, что не является преобразованием аргумента в результат.

Соответственно, чтобы язык был чисто функциональный надо, чтобы состояние было в качестве аргумента и в качестве результата.

По-моему, так и делается в clean, нанапример.

А IO монада в haskell, насколько я понял, состоит в том, что функция возвращает не состояние, а функуцию, которая для текущего состояние мира вычисляет действие с ним. А использование этой функции происходит за пределами языка haskell.

Таким образом, они оба чистые.

no4>Соответственно, чтобы язык был чисто функциональный надо, чтобы состояние было в качестве аргумента и в качестве результата.

no4>По-моему, так и делается в clean, нанапример.

это не состояние, а фиктивный аргумент, пощволяющий управлять последоватенльностью исполнения. подробности в http://haskell.org/haskellwiki/IO_inside

no4>А IO монада в haskell, насколько я понял, состоит в том, что функция возвращает не состояние, а функуцию, которая для текущего состояние мира вычисляет действие с ним. А использование этой функции происходит за пределами языка haskell.

я чуть выше написал — реализация монады IO в большинстве хаскеловских компиляторов точно такая же, как в clean. разница только в том, что в clean это *спецификация*, а в хаскеле — одна из возможных *реализаций*

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

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?

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

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

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

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

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

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

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

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

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