Сначала я его распарсил в DotGraph a из http://hackage.haskell.org/package/graphviz-2999.20.0.3/docs/Data-GraphViz-Types-Graph.html
Распарсить таким образом, чтобы в a был лейбл я не смог, поэтому пришлось написать функцию, которая проходит по всему графу и матчит ноду с нужными атрибутами. У найденной ноды дернул successors, а это оказались только непосредственные последователи. Т.е. тут тоже чет рекурсивное надо было изобретать, поэтому я забил.
Потом через fgl пробовал, но там оказалось что при восстановлении назад из fgl в дот он какую-то информацию теряет. Не помню уже что именно. Я расстроился и пошел пить.
почему вы считаете, что функция не должна течь? как вы это доказали?
как минимум для переменной
s только строятся задумки (s + 1), но никогда не вычисляются
g ks (x0,xs,s)
|x0 == x0' = (x0,s)
|True = g ks (x0',x0:take 30 xs,(s+1))
where
x0' = f xs ks /sum ks
f (x:xs) (k:ks') = x*k + f xs ks'
f _ _ = 0
main = g [2,3,9] (1,[],0)
Чет у меня с форматированием не очень переносы строк исчезли...
как минимум, течёт
s
sum тоже линейно память потребляет на некоторых уровнях оптимизации
Да еще момент - я это в ghci проверяю. Обычно мне удается и там сделать без утечки, но в данный случай заколдованный
g ks (x0,xs,s)
|x0 == x0' = (x0,s)
|True = seq s $ g ks (x0',x0:take 30 xs,1)
where
x0' = f xs ks /14
f (x:xs) (k:ks') = x*k + f xs ks'
f _ _ = 0g ks (x0,xs,s)
|x0 == x0' = (x0,s)
|True = g ks (x0',x0:take 2 xs,s)
where
x0' = f xs ks /sum ks
f (x:xs) (k:ks') = x*k + f xs ks'
f _ _ = 0
@nickbeljaev если Вы запускаете код в GHCi, то он компилируется без оптимизаций, и анализ строгости, уверен, вообще не проводится. В этом случае да, даже Инты "утекают". Не говоря уже про вызовы
take. Либо расставьте аннотации строгости руками, либо хотя бы соберите с оптимизацией, для начала.
@nickbeljaev, да
x0 == x0' должно вычислять x0 и x0', x0' приводит к полному вычислению xs и ks, в результате они начинают занимать всю свою память, но не освобождаются, потому что передаются дальше
g ks x0 xs s
|x0 == x0' = (x0,s)
|True = seq (s+1) $ g ks x0' (x0:take (length ks -1) xs) ((s+1)::Int)
where
x0' = f xs ks /sum ks
f (x:xs) (k:ks') = x*k + f xs ks'
f _ _ = 0
ссылка на
xs утекала через задумку x0 : take _ xs
какая правая часть возможна? я использовал подчёркивание как сокращение, если вы про него
Последний вариант без этого Int тоже работает на мизере памяти, как и задумывалось в этом алгоритме. Но мне все равно не ясно как "лишний" (то есть нигде и никогда не используемый) хвост xs вызывал переполнение, take 30 xs должен оставлять список в 30 элементов, а все остальное, что там было должно становится клиентом мусорщика и освобождаться, но почему то не становилось и не освобождалось. Возможно, при компиляции с оптимизацией эта проблема самоустранилась бы, но хотелось ручками :)
Кроме того для меня удивительна разница между одним "лишним" и двумя. В последнем варианте если поставить take 3 ... то утечки нет, и это один лишний в xs, но если поставить take 4 ... то начинается зверская утечка (примерно 100М/сек) и это 2 лишних, вот это все, как говорится меня беспокоит - данный пример простой, но столкнись с таким в реальной программе - мало не покажется.
Функция
f - это dot product, как я понимаю?
seq (s + 1) смысла не имеет, сложение там ни к селу, ни к городу.
Прошу прощения за мое не владение терминологией, но что значит dot? Функция f фактически является скалярным произведением своих аргументов если это отвечает на Ваш вопрос.
Что там с
takeами происходит - нужно разбираться. Но Вам в любом случае нужно понять как работают "задумки" aka thunks и как возникают space leaks. Об этом написано на Haskell wiki и в книге "Parallel and Concurrent Programming in Haskell" (имеется русский перевод).
Благодарю за ссылки на книги, на "бытовом уровне" мне понятно что значит отложенное вычисление и почему оно может потреблять памяти больше чем выполненное, а может и не потреблять как например
[1..], на уровне компилятора я в этом разбираться не хочу, так как написание компиляторов не моя профессия. Меня пугает отсутствие единообразия результатов в зависимости от количества лишних в списке, то есть тут явно есть бифуркация между 0,1 и остальными числами - хотелось бы понять почему.
Я вот хочу смерджить две мапы таким образом, чтобы при слиянии элементов с одинаковыми ключами одному из них придумывался новый ключ (даже не важно какой) и оба элемента добавлялись бы в конечный мап.
Насколько я понимаю, https://hackage.haskell.org/package/containers-0.6.2.1/docs/Data-IntMap-Merge-Lazy.html этого не позволяет. Надо велосипедить самому?
