scala - How to maintain an immutable list when you impact object linked to each other into this list -

scala - How to maintain an immutable list when you impact object linked to each other into this list -

i'm trying code fast non dominated sorting algorithm (nds) of deb used in nsga2 in immutable way using scala.

but problem seems more hard think, simplify here problem create mwe.

imagine population of seq[a], , each a element decorateda list contains pointers other elements of population seq[a].

a function evala(a:decorateda) take list of linkeda contains, , decrement value of each.

next take subset list decoratedapopulation of population a, , phone call evala on each. have problem, because between each iteration on element on subset list decoratedapopulation, need update population of a new decorateda , new updated linkeda contain ...

more problematic, each element of population need update of 'linkeda' replace linked element if alter ...

hum can see, seem complicated maintain linked list synchronized in way. propose solution bottom, need recursion homecoming after each evala new population element replaced.

how can correctly in immutable way ?

it's easy code in mutable way, don't find way in immutable way, have path or thought ?

object test extends app{ case class a(value:int) {def decrement()= new a(value - 1)} case class decorateda(oneadecorated:a, listoflinkeda:seq[a]) // start algorithm loop element value = 0 val population = seq(new a(0), new a(0), new a(8), new a(1)) val decoratedapopulation = seq(new decorateda(population(1),seq(population(2),population(3))), new decorateda(population(2),seq(population(1),population(3)))) def evala(a:decorateda) = { val newlistoflinked = a.listoflinkeda.map{e => e.decrement() new decorateda(a.oneadecorated,newlistoflinked)} } def run()= { //decoratedapopulation.map{ // ? //} } }

update 1:

about input / output of initial algorithm.

the first part of deb algorithm (step 1 step 3) analyse list of individual, , compute each : (a) domination count, number of dominate me (the value attribute of a) (b) list of dominate (listoflinkeda).

so homecoming population of decorateda totally initialized, , entry of step 4 (my problem) take first non dominated front, cf. subset of elements of decorateda a value = 0.

my problem start here, list of decorateda a value = 0; , search next front end list computing each listoflinkeda of each of a

at each iteration between step 4 step 6, need compute new b subset list of decorateda a value = 0. each , decrementing first domination count attribute of each element listoflinkeda, filter element equal 0. end of step 6, b saved list list[seq[decorateda]], restart step 4 b, , compute new c, etc.

something in code, phone call explore() each element of b, q equal @ end new subset of decorateda value (fitness here) = 0 :

case class populationelement(popelement:seq[double]){ implicit def poptodouble():seq[double] = { popelement } } class solutionelement(values: populationelement, fitness:double, dominates: seq[solutionelement]) { def decrement()= if (fitness == 0) else new solutionelement(values,fitness - 1, dominates) def explore(q:seq[solutionelement]):(solutionelement, seq[solutionelement])={ // homecoming dominates elements fitness - 1 val newsolutionset = dominates.map{_.decrement()} val filteredsolution:seq[solutionelement] = newsolutionset.filter{s => s.fitness == 0.0}.diff{q} filteredsolution } }

a end of algorithm, have final list of seq of decorateda list[seq[decorateda]] contain fronts computed.

update 2

a sample of value extracted example. take pareto front end (red) , {f,h,l} next front end dominated count = 1.

case class p(x: int, y: int) val = a(p(3.5, 1.0),0) val b = a(p(3.0, 1.5),0) val c = a(p(2.0, 2.0),0) val d = a(p(1.0, 3.0),0) val e = a(p(0.5, 4.0),0) val f = a(p(0.5, 4.5),1) val h = a(p(1.5, 3.5),1) val l = a(p(4.5, 1.0),1) case class a(xy:p, value:int) {def decrement()= new a(xy, value - 1)} case class aroot(node:a, children:seq[a]) val population = seq( aroot(a,seq(f,h,l), aroot(b,seq(f,h,l)), aroot(c,seq(f,h,l)), aroot(d,seq(f,h,l)), aroot(e,seq(f,h,l)), aroot(f,nil), aroot(h,nil), aroot(l,nil))

algorithm homecoming list(list(a,b,c,d,e), list(f,h,l))

update 3

after 2 hour, , pattern matching problems (ahum...) i'm comming finish illustration compute automaticaly dominated counter, , children of each aroot.

but have same problem, children list computation not totally correct, because each element perchance shared fellow member of aroot children list, need think reply modify :/ @ time compute children list of seq[p], , need list of seq[a]

case class p(x: double, y: double){ def toseq():seq[double] = seq(x,y) } case class a(xy:p, dominatedcounter:int) {def decrement()= new a(xy, dominatedcounter - 1)} case class aroot(node:a, children:seq[a]) case class arootraw(node:a, children:seq[p]) object test_stackoverflow extends app { val = new p(3.5, 1.0) val b = new p(3.0, 1.5) val c = new p(2.0, 2.0) val d = new p(1.0, 3.0) val e = new p(0.5, 4.0) val f = new p(0.5, 4.5) val g = new p(1.5, 4.5) val h = new p(1.5, 3.5) val = new p(2.0, 3.5) val j = new p(2.5, 3.0) val k = new p(3.5, 2.0) val l = new p(4.5, 1.0) val m = new p(4.5, 2.5) val n = new p(4.0, 4.0) val o = new p(3.0, 4.0) val p = new p(5.0, 4.5) def isstriclydominated(p1: p, p2: p): boolean = { (p1.toseq zip p2.toseq).exists { case (g1, g2) => g1 < g2 } } def sortedbyrank(population: seq[p]) = { def paretoranking(values: set[p]) = { //comment @dk14: suppose order of values isn't matter here, otherwise utilize sortedset values.map { v1 => val t = (values - v1).filter(isstriclydominated(v1, _)).toseq val = new a(v1, values.size - t.size - 1) val root = new arootraw(a, t) println("root value ", root) root } } val listofarootraw = paretoranking(population.toset) //from @dk14: here convertion seq[p] seq[a] val dominations: map[p, int] = listofarootraw.map(a => a.node.xy -> a.node.dominatedcounter) //from @dk14: it's map dominatedcounter each point val listofaroot = listofarootraw.map(raw => aroot(raw.node, raw.children.map(p => a(p, dominations.getorelse(p, 0))))) listofaroot.groupby(_.node.dominatedcounter) } //get first front, subset of aroot, , start step 4 println(sortedbyrank(seq(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p)).head) }

talking problem distinguishing fronts (after update 2):

val (left,right) = population.partition(_.node.value == 0) list(left, right.map(_.copy(node = node.copy(value = node.value - 1))))

no need mutating here. copy re-create everything, fields specified new values. talking code, new re-create linked same list of children, new value = value - 1.

p.s. have feeling may want this:

case class a(id: string, level: int) val = a("a", 1) val b = a("b", 2) val c = a("c", 2) val d = a("d", 3) clusterize(list(a,b,c,d)) === list(list(a), list(b,c), list(d))

it's simple implement:

def clusterize(list: list[a]) = list.groupby(_.level).tolist.sortby(_._1).map(_._2)

test:

scala> clusterize(list(a("a", 1), a("b", 2), a("c", 2), a("d", 3))) res2: list[list[a]] = list(list(a(a,1)), list(a(b,2), a(c,2)), list(a(d,3)))

p.s.2. please consider improve naming conventions, here.

talking "mutating" elements in complex structure:

the thought of "immutable mutating" shared (between parts of structure) value separate "mutation" structure. or saying, split , conquerror:

calculate changes in advance apply them

the code:

case class a(v: int) case class aa(a: a, seq: seq[a]) //decorateda def update(input: seq[aa]) = { //shows how decrement each value wherever is: val stats = input.map(_.a).groupby(identity).mapvalues(_.size) //domination count each def upd(a: a) = a(a.v - stats.getorelse(a, 0)) //apply decrement input.map(aa => aa.copy(aa = aa.seq.map(upd))) //traverse , "update" original construction }

so, i've introduced new map[a, int] structure, shows how modify original one. approach based on highly simplified version of applicative functor concept. in general case, should map[a, => a] or map[k, => b] or map[k, zipper[a] => b] applicative functor (input <*> map). *zipper (see 1, 2) give info current element's context.

notes:

i assumed as same value same; that's default behaviour case classess, otherwise need provide additional id's (or redefine hashcode/equals).

if need more levels - aa(aa(aa(...)))) - create stats , upd recursive, if dеcrement's weight depends on nesting level - add together nesting level parameter recursive function.

if decrement depends on parent node (like decrement a(3)'s, belongs a(3)) - add together parent node(s) part of stats's key , analise during upd.

if there dependency between stats calculation (how much decrement) of let's input(1) input(0) - should utilize foldleft partial stats accumulator: val stats = input.foldleft(map[a, int]())((partialstats, elem) => partialstats ++ analize(partialstats, elem))

btw, takes o(n) here (linear memory , cpu usage)

example:

scala> val population = seq(a(3), a(6), a(8), a(3)) population: seq[a] = list(a(3), a(6), a(8), a(3)) scala> val input = seq(aa(population(1),seq(population(2),population(3))), aa(population(2),seq(population(1),population(3)))) input: seq[aa] = list(aa(a(6),list(a(8), a(3))), aa(a(8),list(a(6), a(3)))) scala> update(input) res34: seq[aa] = list(aa(a(5),list(a(7), a(3))), aa(a(7),list(a(5), a(3))))

list scala recursion immutability genetic-algorithm