Мне захотелось попробовать написать на хаскеле это https://e-maxx.ru/algo/lca_linear_offline Я знаю,

что есть публикации по LCA в хаскеле другими способами, но мне интересно пощупать именно этот, и посмотреть, что получится.

Вот кусочек, который хочется сделать

void dfs(int v)
{
m_visited[v] = true;
m_parent[v] = v;
for (int u : m_adj[v]) {
if (!m_visited[u]) {
dfs(u);
union_sets(v, u);
m_parent[find_set(v)] = v;
}
}
for (int other_node : m_queries[v]) {
if (m_visited[other_node]) {
auto find_set_var = find_set(other_node);
std::cout << "LCA of " << v << " and " << other_node
<< " is " << m_parent[find_set_var] << ".\n";
}
}
}


Взял union-find отсюда https://kseo.github.io/posts/2014-01-30-implementing-union-find-in-haskell.html и начал:

data LcaOffline s = LcaOffline {
uf_:: UnionFind s,
adj_:: Map Int [Int],
queries_:: STUArray s Int (STUArray s Int Int),
result_:: Map (Int, Int) Int,
visited_:: STUArray s Int Bool
}

lcaDfs :: LcaOffline s -> Int -> ST s ()
lcaDfs lcaoffline v =
do
let uf = uf_ lcaoffline
let adj = adj_ lcaoffline
let queries = queries_ lcaoffline
let result = result_ lcaoffline
let visited = visited_ lcaoffline

let descs = M.findWithDefault [] v adj

writeArray visited v True
writeArray (ids uf) v v


forM_ descs $ \x -> do
lcaDfs lcaoffline x
unite uf v x
y <- root uf v --findset
writeArray (ids uf) y v

оно компилируется.


Как дальше взять массив из queries и пройти по нему, записывая куда-то результаты, мне непонятно. Даже как пройти по результатам и сделать ничего, непонятно. Например, хочу просто взять подмассив, и пройтись по нему, по аналогии с кодом выше:

testFun:: (STUArray s Int (STUArray s Int Int)) -> STUArray s Int Bool -> Int -> ST s ()
testFun queries visited v = do
vQueries <- (readArray queries v)
forM vQueries $ \x -> do
writeArray visited x True
и оно не компилируется. Я понимаю, что у vQueries другой тип, попробуем ещё проще
testFun1:: (STUArray s Int (STUArray s Int Int)) -> STUArray s Int Bool -> Int -> STUArray s Int Int
testFun1 queries visited v = do
readArray queries v

тоже не компилируется.

Где почитать про многомерные STUArray?
Что я ещё упускаю? Могут ли тут быть замешаны трансформеры монад, до которых я ещё не дошел?

Эх, вот бы можно было действительно успешно Haskell использовать на олимпиадах (в том же Яндекс.Контест ghc 7.10.2, пакетов никаких нет, так что об эффективной реализации можно только мечтать, наверное)

Собственно, я захотел решить вступительные задачи отсюда https://stepik.org/course/91751/syllabus на хаскеле. Две первые решил вовремя, а третья была совсем непонятной. Тогда ещё не знал, с какой стороны к монадам подходить, и что есть что в do-нотации. Плюс LCA оказалось достаточно редкой темой, готовых исходников нет После неё хочу ещё решить несколько задач с какого-нибудь литкода и из книжки по алгоритмам, которую читаю, и потом переходить к haskell in depth и всяким серверам/клиентам/работой с БД