- About Scala
- Documentation
- Code Examples
- Software
- Scala Developers

# A question of structuring an optimisation algorithm

Thu, 2010-02-04, 17:22

Hello all.

After working throug scala by example, out of purely academic interest, I thought I'd try to cut my teeth on a real world problem. Unfortunately, I've come unstuck.

I have an optimisation routine written in an iterative style (C# in this case), and I figured it would be interesting to implement it in a functional style as at somepoint it might be interesting to suggest runnin it on a cluster.

The algorithm essentially works by simulation: branching realities (where each branch alters the reality slightly) until the final step represents machines on a shop floor cutting rods!

As the algorithm falls back recursively, the most successful of the branches should be chosen in succession, until finally we end up with the reality in which rods ended up being cut in such a way that they best satisfy a compex weighting scheme which considers various aspects of resource use, efficiency of manpower/machines, storage space etc.

It sounds so trivial, I was expecting to make a nice DSL, but after a few days playing around with Scala's AWESOME language features I've yet to find the right way to approach it.

It has proven simple to implement the basic structure in a recursive manner, if I "hardcode" the successive function calls e.g.

def f(arg)=>..do something....f'(arg')..so something..

def f'(arg')=> ..do something....f''(arg'')...

What's been driving me crazy is that I'd like to extract the dependency from within each function regarding which function to call next.

It seems I only have four basic functional "archtypes" to worry about :

1) BRANCH

A type of function which takes a (quite complicated "reality" defined as an object), transforms this reality r to reality r',r'',r''....rn according to some function which may execute arbitrarily many times (e.g. trying different sortings of source and target rods) , calls the next required function with each of these generated "realities"

N.B. A reality object contains lists of everything which can be manipulated to create a different outcome, e.g. the list of rods which are to be produced, the list of rods which exist in stores, and the set of all options which can be used to vary how stages of the process are handled.

2) MERGE

A function which passes arguments onto the next function first, then processes a LIST of results (i.e. a list of "realities) which are returned from that next function to select the best one according to various riteria.

3) ITERATE

A type of function which *partitions* the reality in an arbitrary way with a supplied function (e.g. to cluster the desired rods by OrderID, or by Length, or by Colour) where it must then call the next function for each partition, but feed forward the returned "reality" as an input into each successive call and finally return the single processed reality.

4) TRANSFORM

A type of Transformation function which simply transforms a reality, and passes it onto the next function, returning the result from the next function to the previous function.

I'm afraid I'm not really sure how to tighten up the vocabulary here.

In some sort of pseudo way, I'd ultimately like a DSL which looks something (showing a small subset of the complexity) like :

ITERATE(f_byProfileAndColour) > MERGE(f_byWeightings1) > BRANCH(f_bySeriesRods) > BRANCH(f_byPhysicalRods) > ITERATE(f_byOrderID) > MERGE(f_byWeightings2) > BRANCH(f_byMaxStacking) > BRANCH(f_byAltOrReg) > TRANSFORM(f_SimulateCutting)

where f_.... are externally defined functions. I envisage the ITERATE/MERGE/BRANCH/TRANSFORM in this case as control flow statements which make it abundently clear what the algorithm is doing, when and where (which isn't so obvious in the iterative code, or the function (hardcoded) code as I have it now).

It would be important that order of processing is Left to Right (with the > operator).

It is also important that the "Reality" object gets passed from each stage to the next.

I have tried using currying, case class matching, and even passing along lists of functions... but although I've learnt a LOT about Scala these last few days, for a "spare time" project it's slowly becoming frustrating.

I guess this is a generic sort of problem so I wondered if anybody on the list can advise how they would approach it?

Many thanks for any advice. It's appreciated :-)

Ben

After working throug scala by example, out of purely academic interest, I thought I'd try to cut my teeth on a real world problem. Unfortunately, I've come unstuck.

I have an optimisation routine written in an iterative style (C# in this case), and I figured it would be interesting to implement it in a functional style as at somepoint it might be interesting to suggest runnin it on a cluster.

The algorithm essentially works by simulation: branching realities (where each branch alters the reality slightly) until the final step represents machines on a shop floor cutting rods!

As the algorithm falls back recursively, the most successful of the branches should be chosen in succession, until finally we end up with the reality in which rods ended up being cut in such a way that they best satisfy a compex weighting scheme which considers various aspects of resource use, efficiency of manpower/machines, storage space etc.

It sounds so trivial, I was expecting to make a nice DSL, but after a few days playing around with Scala's AWESOME language features I've yet to find the right way to approach it.

It has proven simple to implement the basic structure in a recursive manner, if I "hardcode" the successive function calls e.g.

def f(arg)=>..do something....f'(arg')..so something..

def f'(arg')=> ..do something....f''(arg'')...

What's been driving me crazy is that I'd like to extract the dependency from within each function regarding which function to call next.

It seems I only have four basic functional "archtypes" to worry about :

1) BRANCH

A type of function which takes a (quite complicated "reality" defined as an object), transforms this reality r to reality r',r'',r''....rn according to some function which may execute arbitrarily many times (e.g. trying different sortings of source and target rods) , calls the next required function with each of these generated "realities"

N.B. A reality object contains lists of everything which can be manipulated to create a different outcome, e.g. the list of rods which are to be produced, the list of rods which exist in stores, and the set of all options which can be used to vary how stages of the process are handled.

2) MERGE

A function which passes arguments onto the next function first, then processes a LIST of results (i.e. a list of "realities) which are returned from that next function to select the best one according to various riteria.

3) ITERATE

A type of function which *partitions* the reality in an arbitrary way with a supplied function (e.g. to cluster the desired rods by OrderID, or by Length, or by Colour) where it must then call the next function for each partition, but feed forward the returned "reality" as an input into each successive call and finally return the single processed reality.

4) TRANSFORM

A type of Transformation function which simply transforms a reality, and passes it onto the next function, returning the result from the next function to the previous function.

I'm afraid I'm not really sure how to tighten up the vocabulary here.

In some sort of pseudo way, I'd ultimately like a DSL which looks something (showing a small subset of the complexity) like :

ITERATE(f_byProfileAndColour) > MERGE(f_byWeightings1) > BRANCH(f_bySeriesRods) > BRANCH(f_byPhysicalRods) > ITERATE(f_byOrderID) > MERGE(f_byWeightings2) > BRANCH(f_byMaxStacking) > BRANCH(f_byAltOrReg) > TRANSFORM(f_SimulateCutting)

where f_.... are externally defined functions. I envisage the ITERATE/MERGE/BRANCH/TRANSFORM in this case as control flow statements which make it abundently clear what the algorithm is doing, when and where (which isn't so obvious in the iterative code, or the function (hardcoded) code as I have it now).

It would be important that order of processing is Left to Right (with the > operator).

It is also important that the "Reality" object gets passed from each stage to the next.

I have tried using currying, case class matching, and even passing along lists of functions... but although I've learnt a LOT about Scala these last few days, for a "spare time" project it's slowly becoming frustrating.

I guess this is a generic sort of problem so I wondered if anybody on the list can advise how they would approach it?

Many thanks for any advice. It's appreciated :-)

Ben

Thu, 2010-02-04, 19:17

#2
Re: A question of structuring an optimisation algorithm

Sorry, mistyped something in the example. Here:
(
realities
.groupBy(f_byProfileAndColour).valuesIterable
.map(f_byWeightings1) // type of f_byWeightings1 is List[R] => R
.flatMap(f_bySeriesRods) // R => List[R]
.flatMap(f_byPhysicalRods) // R => List[R]
.groupBy(f_byOrderID).valuesIterable
.map(f_byWeightings2) // List[R] => R
.flatMap(f_byMaxStacking) // R => List[R]
.flatMap(f_byAltOrReg) // R => List[R]
.map(f_SimulateCutting) // R => R
.merge(finalMerge)
)
Which, in fact, gives me an idea. Let's write a few other implicits (and modify that last one):

class MergeAllRealities(realities: List[R]) { def mergeAll(f: List[R] => R) = f(realities) } implicit def toMergeAllRealities(realities: List[R]) = new MergeAllRealities(realities) class MergeRealities(realities: List[R]) { def merge(f: List[List[R]] => List[R]) = realities.map(f) } implicit def toMergeRealities(realities: List[R]) = new MergeRealities(realities)

class DistributeRealities(realities: List[R]) { def iterate[A](f: R => A) = realities.groupBy(f).valuesIterable.toList def branch(f: R => List[R]) = realities.flatMap(f) def transform(f: R => R) = realities.map(f) } implicit def toDistributeRealities(realities: List[R]) = new DistributeRealities(realities) It should then be possible to write this: ( realities iterate f_byProfileAndColour merge f_byWeightings1 branch f_bySeriesRods branch f_byPhysicalRods iterate f_byOrderID merge f_byWeightings2 branch f_byMaxStacking branch f_byAltOrReg transform f_SimulateCutting mergeAll finalMerge ) This would have been a great question on stack overflow. :-) On Thu, Feb 4, 2010 at 4:03 PM, Daniel Sobral <dcsobral [at] gmail [dot] com> wrote:

--

Daniel C. Sobral

I travel to the future all the time.

class MergeAllRealities(realities: List[R]) { def mergeAll(f: List[R] => R) = f(realities) } implicit def toMergeAllRealities(realities: List[R]) = new MergeAllRealities(realities) class MergeRealities(realities: List[R]) { def merge(f: List[List[R]] => List[R]) = realities.map(f) } implicit def toMergeRealities(realities: List[R]) = new MergeRealities(realities)

class DistributeRealities(realities: List[R]) { def iterate[A](f: R => A) = realities.groupBy(f).valuesIterable.toList def branch(f: R => List[R]) = realities.flatMap(f) def transform(f: R => R) = realities.map(f) } implicit def toDistributeRealities(realities: List[R]) = new DistributeRealities(realities) It should then be possible to write this: ( realities iterate f_byProfileAndColour merge f_byWeightings1 branch f_bySeriesRods branch f_byPhysicalRods iterate f_byOrderID merge f_byWeightings2 branch f_byMaxStacking branch f_byAltOrReg transform f_SimulateCutting mergeAll finalMerge ) This would have been a great question on stack overflow. :-) On Thu, Feb 4, 2010 at 4:03 PM, Daniel Sobral <dcsobral [at] gmail [dot] com> wrote:

In this kind of situation, I recommend thinking about the types. Let's call the type of reality R.

On Thu, Feb 4, 2010 at 2:22 PM, Dr T B Senior <ben [at] sefol [dot] com> wrote:

Hello all.R => List[R] Applied to a list, it could be the method map. Or, if you want to join all maps, a flatMap.

It seems I only have four basic functional "archtypes" to worry about :

1) BRANCH

A type of function which takes a (quite complicated "reality" defined as an object), transforms this reality r to reality r',r'',r''....rn according to some function which may execute arbitrarily many times (e.g. trying different sortings of source and target rods) , calls the next required function with each of these generated "realities"

This one I'm not sure about. I don't quite understand what you are saying.

N.B. A reality object contains lists of everything which can be manipulated to create a different outcome, e.g. the list of rods which are to be produced, the list of rods which exist in stores, and the set of all options which can be used to vary how stages of the process are handled.

2) MERGE

A function which passes arguments onto the next function first, then processes a LIST of results (i.e. a list of "realities) which are returned from that next function to select the best one according to various riteria.Again, not quite sure. The partition part is easy. As a function, it would receive: (R => A, List[R] => List[List[R]]) That's somewhat similar to Scala 2.8's "groupBy", in fact. It's signature is [R](R => K): Map[K, List[A]]. So you could actually write this: listOfRealities.groupBy(f_byProfileAndColor).valuesIterator.toList Assuming, for instance, that "profile" and "color" are two values of a reality, it would go like this: listOfRealities.groupBy(r => (r.profile, r.color)).valuesIterable You also want to call the next function into each partition, which a simple "map" does, but I'm not sure where exactly do you want to go from there.

3) ITERATE

A type of function which *partitions* the reality in an arbitrary way with a supplied function (e.g. to cluster the desired rods by OrderID, or by Length, or by Colour) where it must then call the next function for each partition, but feed forward the returned "reality" as an input into each successive call and finally return the single processed reality.

That's a function R => R. Applied to a List, that's the method R.

4) TRANSFORM

A type of Transformation function which simply transforms a reality, and passes it onto the next function, returning the result from the next function to the previous function.

( realities .groupBy(f_byProfileAndColour).valuesIterable .map(f_byWeightings1) // type of f_byWeightings1 is List[R] => R .flatMap(f_bySeriesRods) // R => List[R] .flatMap(f_byPhysicalRods) // R => List[R] .groupBy(f_byOrderID).valuesIterable .map(f_byWeightings2) // List[R] => R .flatMap(f_byMaxStacking) // R => List[R] .flatMap(f_byAltOrReg) // R => List[R] .map(f_SimulateCutting) // R => R ) It is missing a final merge, it would seem. You'd have to pass the result of the above, which is a List[R], assuming "realities" is a List[R] as well, to the final merge function. You could define an implicit from List[R] => R: class mergeRealities(realities: List[R]) { def merge(f: List[R] => R) = f(realities) } implicit def toMergeRealities(realities: List[R]) = new mergeRealities(realities) Then you could write it like this: ( realities .groupBy(f_byProfileAndColour).valuesIterable .map(f_byWeightings1) // type of f_byWeightings1 is List[R] => R .flatMap(f_bySeriesRods) // R => List[R] .flatMap(f_byPhysicalRods) // R => List[R] .groupBy(f_byOrderID).valuesIterable .map(f_byWeightings2) // List[R] => R .flatMap(f_byMaxStacking) // R => List[R] .flatMap(f_byAltOrReg) // R => List[R] .map(f_SimulateCutting) // R => R .finalMerge )

I'm afraid I'm not really sure how to tighten up the vocabulary here.

In some sort of pseudo way, I'd ultimately like a DSL which looks something (showing a small subset of the complexity) like :

ITERATE(f_byProfileAndColour) > MERGE(f_byWeightings1) > BRANCH(f_bySeriesRods) > BRANCH(f_byPhysicalRods) > ITERATE(f_byOrderID) > MERGE(f_byWeightings2) > BRANCH(f_byMaxStacking) > BRANCH(f_byAltOrReg) > TRANSFORM(f_SimulateCutting)

where f_.... are externally defined functions. I envisage the ITERATE/MERGE/BRANCH/TRANSFORM in this case as control flow statements which make it abundently clear what the algorithm is doing, when and where (which isn't so obvious in the iterative code, or the function (hardcoded) code as I have it now).

It would be important that order of processing is Left to Right (with the > operator).

It is also important that the "Reality" object gets passed from each stage to the next.

I have tried using currying, case class matching, and even passing along lists of functions... but although I've learnt a LOT about Scala these last few days, for a "spare time" project it's slowly becoming frustrating.

I guess this is a generic sort of problem so I wondered if anybody on the list can advise how they would approach it?

Many thanks for any advice. It's appreciated :-)

Ben

--

Daniel C. Sobral

I travel to the future all the time.

--

Daniel C. Sobral

I travel to the future all the time.

Fri, 2010-02-05, 21:17

#3
Re: A question of structuring an optimisation algorithm

Thanks! Great answer, in
that I'm imspired by what you're driving at.

To get it working would be amazing, but after a lot of head scratching and false starting I'm still stuck in newb quicksand land, and not convinced I articulated the problem sufficiently well.

The first hurdle is the groupBy function (I am using the 2.8 Beta now).

Lets define some really simple objects :

class PRod ( val profile : String, val colour : String, val length : Int) { //Physical Rods

}

class SRod( val profile : String, val colour : String, val length : Int) { //Series Rods "target rods to be cut from physical rods"

}

class RRod ( val pRod : PRod, val sRods : List[SRod] ) { //Result rod which lists the series rods cut from a physical rod

}

class Reality ( val physicalRods : List[PRod], val seriesRods : List[SRod], val resultRods : List[RRod]) {

//Options will also go here

}

The idea was to call something like : realities.groupBy(f_byProfileAndColour), however, I'm not sure the application of groupBy is going to be so simple in this real world problem.

Lets instantiate a Reality object with a few rods :

val realities : Reality = new Reality(

List (

new PRod("p1","c1",100),

new PRod("p2","c1",100),

),

List (

new SRod("p1","c1",100),

new SRod("p1","c1",100),

new SRod("p2","c1",100),

new SRod("p1","c2",100)

),

List() )

If I were to call "realities.groupBy(f_byProfileAndColour)" I would be aiming for a List of Reality which looks something like :

List (

Reality ( List (("p1","c1",100),("p2","c1",100)),

List (("p1","c1",100),("p1","c1",100)),

()),

Reality ( List (("p1","c1",100),("p2","c1",100)),

List (("p2","c1",100)),

()),

Reality ( List (("p1","c1",100),("p2","c1",100)),

List (("p1","c2",100)),

()),

)

Is it really possible to supply a function to the groupBy function which might achieve this? What on earch might it look like?

I'm not even sure how best to get the groupBy method on the Reality in a scala way.

Should I be making these simple classes extend some sort of trait, and/or using generic types, such that the Reality object itself has a groupBy method?

Should I be implementing a groupBy method myself on the Reality object, in which case, how would I approach what would (in an iterative way) otherwise be a nested for-loop with some simple object cloning through constructors?

I'm seriously intrigued by all this...

Many Thanks,

Ben

On 04/02/2010 19:03, Daniel Sobral wrote:

To get it working would be amazing, but after a lot of head scratching and false starting I'm still stuck in newb quicksand land, and not convinced I articulated the problem sufficiently well.

The first hurdle is the groupBy function (I am using the 2.8 Beta now).

Lets define some really simple objects :

class PRod ( val profile : String, val colour : String, val length : Int) { //Physical Rods

}

class SRod( val profile : String, val colour : String, val length : Int) { //Series Rods "target rods to be cut from physical rods"

}

class RRod ( val pRod : PRod, val sRods : List[SRod] ) { //Result rod which lists the series rods cut from a physical rod

}

class Reality ( val physicalRods : List[PRod], val seriesRods : List[SRod], val resultRods : List[RRod]) {

//Options will also go here

}

The idea was to call something like : realities.groupBy(f_byProfileAndColour), however, I'm not sure the application of groupBy is going to be so simple in this real world problem.

Lets instantiate a Reality object with a few rods :

val realities : Reality = new Reality(

List (

new PRod("p1","c1",100),

new PRod("p2","c1",100),

),

List (

new SRod("p1","c1",100),

new SRod("p1","c1",100),

new SRod("p2","c1",100),

new SRod("p1","c2",100)

),

List() )

If I were to call "realities.groupBy(f_byProfileAndColour)" I would be aiming for a List of Reality which looks something like :

List (

Reality ( List (("p1","c1",100),("p2","c1",100)),

List (("p1","c1",100),("p1","c1",100)),

()),

Reality ( List (("p1","c1",100),("p2","c1",100)),

List (("p2","c1",100)),

()),

Reality ( List (("p1","c1",100),("p2","c1",100)),

List (("p1","c2",100)),

()),

)

Is it really possible to supply a function to the groupBy function which might achieve this? What on earch might it look like?

I'm not even sure how best to get the groupBy method on the Reality in a scala way.

Should I be making these simple classes extend some sort of trait, and/or using generic types, such that the Reality object itself has a groupBy method?

Should I be implementing a groupBy method myself on the Reality object, in which case, how would I approach what would (in an iterative way) otherwise be a nested for-loop with some simple object cloning through constructors?

I'm seriously intrigued by all this...

Many Thanks,

Ben

On 04/02/2010 19:03, Daniel Sobral wrote:

6698c0871002041003o7caa45bdy247a4ef8790c8104 [at] mail [dot] gmail [dot] com" type="cite">In this kind of situation, I recommend thinking about the types. Let's call the type of reality R.

On Thu, Feb 4, 2010 at 2:22 PM, Dr T B Senior <ben [at] sefol [dot] com" rel="nofollow">ben [at] sefol [dot] com> wrote:

Hello all.R => List[R] Applied to a list, it could be the method map. Or, if you want to join all maps, a flatMap.

It seems I only have four basic functional "archtypes" to worry about :

1) BRANCH

A type of function which takes a (quite complicated "reality" defined as an object), transforms this reality r to reality r',r'',r''....rn according to some function which may execute arbitrarily many times (e.g. trying different sortings of source and target rods) , calls the next required function with each of these generated "realities"

This one I'm not sure about. I don't quite understand what you are saying.

N.B. A reality object contains lists of everything which can be manipulated to create a different outcome, e.g. the list of rods which are to be produced, the list of rods which exist in stores, and the set of all options which can be used to vary how stages of the process are handled.

2) MERGE

A function which passes arguments onto the next function first, then processes a LIST of results (i.e. a list of "realities) which are returned from that next function to select the best one according to various riteria.Again, not quite sure. The partition part is easy. As a function, it would receive: (R => A, List[R] => List[List[R]]) That's somewhat similar to Scala 2.8's "groupBy", in fact. It's signature is [R](R => K): Map[K, List[A]]. So you could actually write this: listOfRealities.groupBy(f_byProfileAndColor).valuesIterator.toList Assuming, for instance, that "profile" and "color" are two values of a reality, it would go like this: listOfRealities.groupBy(r => (r.profile, r.color)).valuesIterable You also want to call the next function into each partition, which a simple "map" does, but I'm not sure where exactly do you want to go from there.

3) ITERATE

A type of function which *partitions* the reality in an arbitrary way with a supplied function (e.g. to cluster the desired rods by OrderID, or by Length, or by Colour) where it must then call the next function for each partition, but feed forward the returned "reality" as an input into each successive call and finally return the single processed reality.

That's a function R => R. Applied to a List, that's the method R.

4) TRANSFORM

A type of Transformation function which simply transforms a reality, and passes it onto the next function, returning the result from the next function to the previous function.

( realities .groupBy(f_byProfileAndColour).valuesIterable .map(f_byWeightings1) // type of f_byWeightings1 is List[R] => R .flatMap(f_bySeriesRods) // R => List[R] .flatMap(f_byPhysicalRods) // R => List[R] .groupBy(f_byOrderID).valuesIterable .map(f_byWeightings2) // List[R] => R .flatMap(f_byMaxStacking) // R => List[R] .flatMap(f_byAltOrReg) // R => List[R] .map(f_SimulateCutting) // R => R ) It is missing a final merge, it would seem. You'd have to pass the result of the above, which is a List[R], assuming "realities" is a List[R] as well, to the final merge function. You could define an implicit from List[R] => R: class mergeRealities(realities: List[R]) { def merge(f: List[R] => R) = f(realities) } implicit def toMergeRealities(realities: List[R]) = new mergeRealities(realities) Then you could write it like this: ( realities .groupBy(f_byProfileAndColour).valuesIterable .map(f_byWeightings1) // type of f_byWeightings1 is List[R] => R .flatMap(f_bySeriesRods) // R => List[R] .flatMap(f_byPhysicalRods) // R => List[R] .groupBy(f_byOrderID).valuesIterable .map(f_byWeightings2) // List[R] => R .flatMap(f_byMaxStacking) // R => List[R] .flatMap(f_byAltOrReg) // R => List[R] .map(f_SimulateCutting) // R => R .finalMerge )

I'm afraid I'm not really sure how to tighten up the vocabulary here.

In some sort of pseudo way, I'd ultimately like a DSL which looks something (showing a small subset of the complexity) like :

ITERATE(f_byProfileAndColour) > MERGE(f_byWeightings1) > BRANCH(f_bySeriesRods) > BRANCH(f_byPhysicalRods) > ITERATE(f_byOrderID) > MERGE(f_byWeightings2) > BRANCH(f_byMaxStacking) > BRANCH(f_byAltOrReg) > TRANSFORM(f_SimulateCutting)

Sat, 2010-02-06, 11:17

#4
Re: A question of structuring an optimisation algorithm

This approach with the method chaining isn't going to suffice because
of the "flat"/"linear" nature of its output loses the scoping of
different branchs "alternative realities" which are necessary to
maintain for processing (this is where I wish I had some training in
formal methods so I could at least use some common terminology). It
would be possible to build up lists of lists of lists of lists, but
that's going to quickly become ridiculous.

I believe a recursive structure is the only possible way to tackle this elegantly, because it inherently builds up its own tree of state (Realities) which can either be merged, or *fed forward into sibling childing*.

This was something I failed to get across in my description of the puzzle.

There are points at which a node (a function) will spawn multiple children, and each child function will receive the same Reality R as an input. Each reality which is returned will be assessed against weightings and the best chosen. (BRANCH)

There are other points at which a node (a function) will spawn multiple children, but each child must receive the output from the last - so R is passed to the first child function call, which returns R', which is passed into the next child function call, which returns R'' which is fed into the next child and so forth. (ITERATE)

A mixture of these two types of behaviour are needed, which means that MERGE operations become the links between the changes in strategy.

I didn't have such difficulty hacking up a functional prototype where function calls are embedded inside the body of calling functions, as that gives fine-grained control over whether you are recursively calling functions and passing them the same reality, or passing them "processed realities" in sequence. It also give simple control over where and when you want to merge, as you can insert a function which first calls a following function recursively, and then handles whatever is returned passing back the chosen reality. MERGE

What I'm really asking about, at the core of things, is how to generalise and parameterise this type of situation, where there are many nested function calls where each function call is likely unique, but they conform to a general patten of calls.

My goal was to try to use Scala to find an elegent way to "drop in" the expression of alternative realities, based on exhaustively tweaking arbitrary aspects of those realities which will affect the outcome of the cutting.

It's this problem which has really got me stuck in an obsessive loop, partly because I am failing to reduce the problem to a simple enough form that I can really think about it clearly!

Perhaps somebody recognises the core issue here through the murk, and can point in the direction of a paper/blog?

Thanks for your time,

Ben

On 05/02/2010 21:16, Dr T B Senior wrote:

I believe a recursive structure is the only possible way to tackle this elegantly, because it inherently builds up its own tree of state (Realities) which can either be merged, or *fed forward into sibling childing*.

This was something I failed to get across in my description of the puzzle.

There are points at which a node (a function) will spawn multiple children, and each child function will receive the same Reality R as an input. Each reality which is returned will be assessed against weightings and the best chosen. (BRANCH)

There are other points at which a node (a function) will spawn multiple children, but each child must receive the output from the last - so R is passed to the first child function call, which returns R', which is passed into the next child function call, which returns R'' which is fed into the next child and so forth. (ITERATE)

A mixture of these two types of behaviour are needed, which means that MERGE operations become the links between the changes in strategy.

I didn't have such difficulty hacking up a functional prototype where function calls are embedded inside the body of calling functions, as that gives fine-grained control over whether you are recursively calling functions and passing them the same reality, or passing them "processed realities" in sequence. It also give simple control over where and when you want to merge, as you can insert a function which first calls a following function recursively, and then handles whatever is returned passing back the chosen reality. MERGE

What I'm really asking about, at the core of things, is how to generalise and parameterise this type of situation, where there are many nested function calls where each function call is likely unique, but they conform to a general patten of calls.

My goal was to try to use Scala to find an elegent way to "drop in" the expression of alternative realities, based on exhaustively tweaking arbitrary aspects of those realities which will affect the outcome of the cutting.

It's this problem which has really got me stuck in an obsessive loop, partly because I am failing to reduce the problem to a simple enough form that I can really think about it clearly!

Perhaps somebody recognises the core issue here through the murk, and can point in the direction of a paper/blog?

Thanks for your time,

Ben

On 05/02/2010 21:16, Dr T B Senior wrote:

4B6C7CA3 [dot] 2070600 [at] sefol [dot] com" type="cite"> Thanks! Great answer, in that I'm imspired by what you're driving at.

To get it working would be amazing, but after a lot of head scratching and false starting I'm still stuck in newb quicksand land, and not convinced I articulated the problem sufficiently well.

The first hurdle is the groupBy function (I am using the 2.8 Beta now).

Lets define some really simple objects :

class PRod ( val profile : String, val colour : String, val length : Int) { //Physical Rods

}

class SRod( val profile : String, val colour : String, val length : Int) { //Series Rods "target rods to be cut from physical rods"

}

class RRod ( val pRod : PRod, val sRods : List[SRod] ) { //Result rod which lists the series rods cut from a physical rod

}

class Reality ( val physicalRods : List[PRod], val seriesRods : List[SRod], val resultRods : List[RRod]) {

//Options will also go here

}

The idea was to call something like : realities.groupBy(f_byProfileAndColour), however, I'm not sure the application of groupBy is going to be so simple in this real world problem.

Lets instantiate a Reality object with a few rods :

val realities : Reality = new Reality(

List (

new PRod("p1","c1",100),

new PRod("p2","c1",100),

),

List (

new SRod("p1","c1",100),

new SRod("p1","c1",100),

new SRod("p2","c1",100),

new SRod("p1","c2",100)

),

List() )

If I were to call "realities.groupBy(f_byProfileAndColour)" I would be aiming for a List of Reality which looks something like :

List (

Reality ( List (("p1","c1",100),("p2","c1",100)),

List (("p1","c1",100),("p1","c1",100)),

()),

Reality ( List (("p1","c1",100),("p2","c1",100)),

List (("p2","c1",100)),

()),

Reality ( List (("p1","c1",100),("p2","c1",100)),

List (("p1","c2",100)),

()),

)

Is it really possible to supply a function to the groupBy function which might achieve this? What on earch might it look like?

I'm not even sure how best to get the groupBy method on the Reality in a scala way.

Should I be making these simple classes extend some sort of trait, and/or using generic types, such that the Reality object itself has a groupBy method?

Should I be implementing a groupBy method myself on the Reality object, in which case, how would I approach what would (in an iterative way) otherwise be a nested for-loop with some simple object cloning through constructors?

I'm seriously intrigued by all this...

Many Thanks,

Ben

On 04/02/2010 19:03, Daniel Sobral wrote:6698c0871002041003o7caa45bdy247a4ef8790c8104 [at] mail [dot] gmail [dot] com" type="cite">In this kind of situation, I recommend thinking about the types. Let's call the type of reality R.

On Thu, Feb 4, 2010 at 2:22 PM, Dr T B Senior <ben [at] sefol [dot] com" rel="nofollow">ben [at] sefol [dot] com> wrote:

Hello all.R => List[R] Applied to a list, it could be the method map. Or, if you want to join all maps, a flatMap.

It seems I only have four basic functional "archtypes" to worry about :

1) BRANCH

A type of function which takes a (quite complicated "reality" defined as an object), transforms this reality r to reality r',r'',r''....rn according to some function which may execute arbitrarily many times (e.g. trying different sortings of source and target rods) , calls the next required function with each of these generated "realities"

This one I'm not sure about. I don't quite understand what you are saying.

N.B. A reality object contains lists of everything which can be manipulated to create a different outcome, e.g. the list of rods which are to be produced, the list of rods which exist in stores, and the set of all options which can be used to vary how stages of the process are handled.

2) MERGE

A function which passes arguments onto the next function first, then processes a LIST of results (i.e. a list of "realities) which are returned from that next function to select the best one according to various riteria.Again, not quite sure. The partition part is easy. As a function, it would receive: (R => A, List[R] => List[List[R]]) That's somewhat similar to Scala 2.8's "groupBy", in fact. It's signature is [R](R => K): Map[K, List[A]]. So you could actually write this: listOfRealities.groupBy(f_byProfileAndColor).valuesIterator.toList Assuming, for instance, that "profile" and "color" are two values of a reality, it would go like this: listOfRealities.groupBy(r => (r.profile, r.color)).valuesIterable You also want to call the next function into each partition, which a simple "map" does, but I'm not sure where exactly do you want to go from there.

3) ITERATE

A type of function which *partitions* the reality in an arbitrary way with a supplied function (e.g. to cluster the desired rods by OrderID, or by Length, or by Colour) where it must then call the next function for each partition, but feed forward the returned "reality" as an input into each successive call and finally return the single processed reality.

That's a function R => R. Applied to a List, that's the method R.

4) TRANSFORM

A type of Transformation function which simply transforms a reality, and passes it onto the next function, returning the result from the next function to the previous function.

( realities .groupBy(f_byProfileAndColour).valuesIterable .map(f_byWeightings1) // type of f_byWeightings1 is List[R] => R .flatMap(f_bySeriesRods) // R => List[R] .flatMap(f_byPhysicalRods) // R => List[R] .groupBy(f_byOrderID).valuesIterable .map(f_byWeightings2) // List[R] => R .flatMap(f_byMaxStacking) // R => List[R] .flatMap(f_byAltOrReg) // R => List[R] .map(f_SimulateCutting) // R => R ) It is missing a final merge, it would seem. You'd have to pass the result of the above, which is a List[R], assuming "realities" is a List[R] as well, to the final merge function. You could define an implicit from List[R] => R: class mergeRealities(realities: List[R]) { def merge(f: List[R] => R) = f(realities) } implicit def toMergeRealities(realities: List[R]) = new mergeRealities(realities) Then you could write it like this: ( realities .groupBy(f_byProfileAndColour).valuesIterable .map(f_byWeightings1) // type of f_byWeightings1 is List[R] => R .flatMap(f_bySeriesRods) // R => List[R] .flatMap(f_byPhysicalRods) // R => List[R] .groupBy(f_byOrderID).valuesIterable .map(f_byWeightings2) // List[R] => R .flatMap(f_byMaxStacking) // R => List[R] .flatMap(f_byAltOrReg) // R => List[R] .map(f_SimulateCutting) // R => R .finalMerge )

I'm afraid I'm not really sure how to tighten up the vocabulary here.

In some sort of pseudo way, I'd ultimately like a DSL which looks something (showing a small subset of the complexity) like :

ITERATE(f_byProfileAndColour) > MERGE(f_byWeightings1) > BRANCH(f_bySeriesRods) > BRANCH(f_byPhysicalRods) > ITERATE(f_byOrderID) > MERGE(f_byWeightings2) > BRANCH(f_byMaxStacking) > BRANCH(f_byAltOrReg) > TRANSFORM(f_SimulateCutting)

Sat, 2010-02-06, 17:07

#5
Re: A question of structuring an optimisation algorithm

I have to say, I'd expected to find the solution in Currying somehow..
to get that linear form of

t'(f'') t''(f''') t'''(f''') where t is a sort of "template function" and f is a function parameterising that function, so that as each "t" uses the "f" to recurse, the "f" will consume the next "t" as the function to call next... thus keeping a normal tree-like recursion but being freely and easily able to define which functions are executed, and what general control flow they follow in calling successive functions, at each level of recursion.

Does that sound plausible?

I couldn't get it to work, however (just couldn't seem to get the syntax right).

Thanks,

Ben

On 06/02/2010 11:09, Dr T B Senior wrote:

t'(f'') t''(f''') t'''(f''') where t is a sort of "template function" and f is a function parameterising that function, so that as each "t" uses the "f" to recurse, the "f" will consume the next "t" as the function to call next... thus keeping a normal tree-like recursion but being freely and easily able to define which functions are executed, and what general control flow they follow in calling successive functions, at each level of recursion.

Does that sound plausible?

I couldn't get it to work, however (just couldn't seem to get the syntax right).

Thanks,

Ben

On 06/02/2010 11:09, Dr T B Senior wrote:

4B6D3FD5 [dot] 7030008 [at] sefol [dot] com" type="cite"> This approach with the method chaining isn't going to suffice because of the "flat"/"linear" nature of its output loses the scoping of different branchs "alternative realities" which are necessary to maintain for processing (this is where I wish I had some training in formal methods so I could at least use some common terminology). It would be possible to build up lists of lists of lists of lists, but that's going to quickly become ridiculous.

I believe a recursive structure is the only possible way to tackle this elegantly, because it inherently builds up its own tree of state (Realities) which can either be merged, or *fed forward into sibling childing*.

This was something I failed to get across in my description of the puzzle.

There are points at which a node (a function) will spawn multiple children, and each child function will receive the same Reality R as an input. Each reality which is returned will be assessed against weightings and the best chosen. (BRANCH)

There are other points at which a node (a function) will spawn multiple children, but each child must receive the output from the last - so R is passed to the first child function call, which returns R', which is passed into the next child function call, which returns R'' which is fed into the next child and so forth. (ITERATE)

A mixture of these two types of behaviour are needed, which means that MERGE operations become the links between the changes in strategy.

I didn't have such difficulty hacking up a functional prototype where function calls are embedded inside the body of calling functions, as that gives fine-grained control over whether you are recursively calling functions and passing them the same reality, or passing them "processed realities" in sequence. It also give simple control over where and when you want to merge, as you can insert a function which first calls a following function recursively, and then handles whatever is returned passing back the chosen reality. MERGE

What I'm really asking about, at the core of things, is how to generalise and parameterise this type of situation, where there are many nested function calls where each function call is likely unique, but they conform to a general patten of calls.

My goal was to try to use Scala to find an elegent way to "drop in" the expression of alternative realities, based on exhaustively tweaking arbitrary aspects of those realities which will affect the outcome of the cutting.

It's this problem which has really got me stuck in an obsessive loop, partly because I am failing to reduce the problem to a simple enough form that I can really think about it clearly!

Perhaps somebody recognises the core issue here through the murk, and can point in the direction of a paper/blog?

Thanks for your time,

Ben

On 05/02/2010 21:16, Dr T B Senior wrote:4B6C7CA3 [dot] 2070600 [at] sefol [dot] com" type="cite"> Thanks! Great answer, in that I'm imspired by what you're driving at.

To get it working would be amazing, but after a lot of head scratching and false starting I'm still stuck in newb quicksand land, and not convinced I articulated the problem sufficiently well.

The first hurdle is the groupBy function (I am using the 2.8 Beta now).

Lets define some really simple objects :

class PRod ( val profile : String, val colour : String, val length : Int) { //Physical Rods

}

class SRod( val profile : String, val colour : String, val length : Int) { //Series Rods "target rods to be cut from physical rods"

}

class RRod ( val pRod : PRod, val sRods : List[SRod] ) { //Result rod which lists the series rods cut from a physical rod

}

class Reality ( val physicalRods : List[PRod], val seriesRods : List[SRod], val resultRods : List[RRod]) {

//Options will also go here

}

The idea was to call something like : realities.groupBy(f_byProfileAndColour), however, I'm not sure the application of groupBy is going to be so simple in this real world problem.

Lets instantiate a Reality object with a few rods :

val realities : Reality = new Reality(

List (

new PRod("p1","c1",100),

new PRod("p2","c1",100),

),

List (

new SRod("p1","c1",100),

new SRod("p1","c1",100),

new SRod("p2","c1",100),

new SRod("p1","c2",100)

),

List() )

If I were to call "realities.groupBy(f_byProfileAndColour)" I would be aiming for a List of Reality which looks something like :

List (

Reality ( List (("p1","c1",100),("p2","c1",100)),

List (("p1","c1",100),("p1","c1",100)),

()),

Reality ( List (("p1","c1",100),("p2","c1",100)),

List (("p2","c1",100)),

()),

Reality ( List (("p1","c1",100),("p2","c1",100)),

List (("p1","c2",100)),

()),

)

Is it really possible to supply a function to the groupBy function which might achieve this? What on earch might it look like?

I'm not even sure how best to get the groupBy method on the Reality in a scala way.

Should I be making these simple classes extend some sort of trait, and/or using generic types, such that the Reality object itself has a groupBy method?

Should I be implementing a groupBy method myself on the Reality object, in which case, how would I approach what would (in an iterative way) otherwise be a nested for-loop with some simple object cloning through constructors?

I'm seriously intrigued by all this...

Many Thanks,

Ben

On 04/02/2010 19:03, Daniel Sobral wrote:6698c0871002041003o7caa45bdy247a4ef8790c8104 [at] mail [dot] gmail [dot] com" type="cite">In this kind of situation, I recommend thinking about the types. Let's call the type of reality R.

On Thu, Feb 4, 2010 at 2:22 PM, Dr T B Senior <ben [at] sefol [dot] com" rel="nofollow">ben [at] sefol [dot] com> wrote:

It seems I only have four basic functional "archtypes" to worry about :

1) BRANCH

A type of function which takes a (quite complicated "reality" defined as an object), transforms this reality r to reality r',r'',r''....rn according to some function which may execute arbitrarily many times (e.g. trying different sortings of source and target rods) , calls the next required function with each of these generated "realities"

N.B. A reality object contains lists of everything which can be manipulated to create a different outcome, e.g. the list of rods which are to be produced, the list of rods which exist in stores, and the set of all options which can be used to vary how stages of the process are handled.

2) MERGE

A function which passes arguments onto the next function first, then processes a LIST of results (i.e. a list of "realities) which are returned from that next function to select the best one according to various riteria.

3) ITERATE

A type of function which *partitions* the reality in an arbitrary way with a supplied function (e.g. to cluster the desired rods by OrderID, or by Length, or by Colour) where it must then call the next function for each partition, but feed forward the returned "reality" as an input into each successive call and finally return the single processed reality.

4) TRANSFORM

A type of Transformation function which simply transforms a reality, and passes it onto the next function, returning the result from the next function to the previous function.

I'm afraid I'm not really sure how to tighten up the vocabulary here.

In some sort of pseudo way, I'd ultimately like a DSL which looks something (showing a small subset of the complexity) like :

ITERATE(f_byProfileAndColour) > MERGE(f_byWeightings1) > BRANCH(f_bySeriesRods) > BRANCH(f_byPhysicalRods) > ITERATE(f_byOrderID) > MERGE(f_byWeightings2) > BRANCH(f_byMaxStacking) > BRANCH(f_byAltOrReg) > TRANSFORM(f_SimulateCutting)

Wed, 2010-02-10, 20:07

#6
Re: A question of structuring an optimisation algorithm

I think lists of lists are easier to deal with in Scala than you take them to be. See, for instance, my example, where lists of lists where dealt with without a hitch. But be it as it may.
To do the chaining you mention, I think you'll need to return functions. So ITERATE and MERGE might be defined like this:
trait R
def ITERATE[A, B](f: R => A)(g: A => B): R => B = (r: R) => (f andThen g)(r)
def MERGE[A, B](f: A => R)(g: R => B): A => B = (t: A) => (f andThen g)(t)

def f_byProfileAndColor(r: R) = List(r) def f_byWeightings1(l: List[R]) = l.head Then you can write the following, which will return a function R => R: ITERATE(f_byProfileAndColor)(MERGE(f_byWeightings1)(identity)) The problem here is that you'll have to keep enclosing the right side in parenthesis, which lead to the very problem with deep nesting that you fear. Let's see if a forward pipe operator might help: object Functional {

class PipedObject[T] private[Functional] (value:T)

{

def |>[R] (f : T => R) = f(this.value)

}

implicit def toPiped[T] (value:T) = new PipedObject[T](value)

} import Functional._

trait R def ITERATE[A](f: R => A)(g: R => R) = (f compose g) def MERGE[A](f: A => R)(g: R => A) = (f compose g) def f_byProfileAndColor(r: R) = List(r) def f_byWeightings1(l: List[R]) = l.head And that let you write the following, resulting in a function R => R identity[R] _ |> ITERATE(f_byProfileAndColor) |> MERGE(f_byWeightings1) Since ITERATE, MERGE, etc are expected to take a function from as the second argument, I had to pass an identity R => R to "turn it on". Another possibility that occurs to me is to use operators that end in ":", as these are read right to left instead of left to right, which might produce the desired result as well. Making examples of that is not that trivial, however. At any rate, I can work with you to define the other operators you mentioned if this is more suited to your requirements. Is it? On Sat, Feb 6, 2010 at 1:58 PM, Dr T B Senior <ben [at] sefol [dot] com> wrote:

--

Daniel C. Sobral

I travel to the future all the time.

def f_byProfileAndColor(r: R) = List(r) def f_byWeightings1(l: List[R]) = l.head Then you can write the following, which will return a function R => R: ITERATE(f_byProfileAndColor)(MERGE(f_byWeightings1)(identity)) The problem here is that you'll have to keep enclosing the right side in parenthesis, which lead to the very problem with deep nesting that you fear. Let's see if a forward pipe operator might help: object Functional {

class PipedObject[T] private[Functional] (value:T)

{

def |>[R] (f : T => R) = f(this.value)

}

implicit def toPiped[T] (value:T) = new PipedObject[T](value)

} import Functional._

trait R def ITERATE[A](f: R => A)(g: R => R) = (f compose g) def MERGE[A](f: A => R)(g: R => A) = (f compose g) def f_byProfileAndColor(r: R) = List(r) def f_byWeightings1(l: List[R]) = l.head And that let you write the following, resulting in a function R => R identity[R] _ |> ITERATE(f_byProfileAndColor) |> MERGE(f_byWeightings1) Since ITERATE, MERGE, etc are expected to take a function from as the second argument, I had to pass an identity R => R to "turn it on". Another possibility that occurs to me is to use operators that end in ":", as these are read right to left instead of left to right, which might produce the desired result as well. Making examples of that is not that trivial, however. At any rate, I can work with you to define the other operators you mentioned if this is more suited to your requirements. Is it? On Sat, Feb 6, 2010 at 1:58 PM, Dr T B Senior <ben [at] sefol [dot] com> wrote:

I have to say, I'd expected to find the solution in Currying somehow.. to get that linear form of

t'(f'') t''(f''') t'''(f''') where t is a sort of "template function" and f is a function parameterising that function, so that as each "t" uses the "f" to recurse, the "f" will consume the next "t" as the function to call next... thus keeping a normal tree-like recursion but being freely and easily able to define which functions are executed, and what general control flow they follow in calling successive functions, at each level of recursion.

Does that sound plausible?

I couldn't get it to work, however (just couldn't seem to get the syntax right).

Thanks,

Ben

On 06/02/2010 11:09, Dr T B Senior wrote:This approach with the method chaining isn't going to suffice because of the "flat"/"linear" nature of its output loses the scoping of different branchs "alternative realities" which are necessary to maintain for processing (this is where I wish I had some training in formal methods so I could at least use some common terminology). It would be possible to build up lists of lists of lists of lists, but that's going to quickly become ridiculous.

I believe a recursive structure is the only possible way to tackle this elegantly, because it inherently builds up its own tree of state (Realities) which can either be merged, or *fed forward into sibling childing*.

This was something I failed to get across in my description of the puzzle.

There are points at which a node (a function) will spawn multiple children, and each child function will receive the same Reality R as an input. Each reality which is returned will be assessed against weightings and the best chosen. (BRANCH)

There are other points at which a node (a function) will spawn multiple children, but each child must receive the output from the last - so R is passed to the first child function call, which returns R', which is passed into the next child function call, which returns R'' which is fed into the next child and so forth. (ITERATE)

A mixture of these two types of behaviour are needed, which means that MERGE operations become the links between the changes in strategy.

I didn't have such difficulty hacking up a functional prototype where function calls are embedded inside the body of calling functions, as that gives fine-grained control over whether you are recursively calling functions and passing them the same reality, or passing them "processed realities" in sequence. It also give simple control over where and when you want to merge, as you can insert a function which first calls a following function recursively, and then handles whatever is returned passing back the chosen reality. MERGE

What I'm really asking about, at the core of things, is how to generalise and parameterise this type of situation, where there are many nested function calls where each function call is likely unique, but they conform to a general patten of calls.

My goal was to try to use Scala to find an elegent way to "drop in" the expression of alternative realities, based on exhaustively tweaking arbitrary aspects of those realities which will affect the outcome of the cutting.

It's this problem which has really got me stuck in an obsessive loop, partly because I am failing to reduce the problem to a simple enough form that I can really think about it clearly!

Perhaps somebody recognises the core issue here through the murk, and can point in the direction of a paper/blog?

Thanks for your time,

Ben

On 05/02/2010 21:16, Dr T B Senior wrote:Thanks! Great answer, in that I'm imspired by what you're driving at.

To get it working would be amazing, but after a lot of head scratching and false starting I'm still stuck in newb quicksand land, and not convinced I articulated the problem sufficiently well.

The first hurdle is the groupBy function (I am using the 2.8 Beta now).

Lets define some really simple objects :

class PRod ( val profile : String, val colour : String, val length : Int) { //Physical Rods

}

class SRod( val profile : String, val colour : String, val length : Int) { //Series Rods "target rods to be cut from physical rods"

}

class RRod ( val pRod : PRod, val sRods : List[SRod] ) { //Result rod which lists the series rods cut from a physical rod

}

class Reality ( val physicalRods : List[PRod], val seriesRods : List[SRod], val resultRods : List[RRod]) {

//Options will also go here

}

The idea was to call something like : realities.groupBy(f_byProfileAndColour), however, I'm not sure the application of groupBy is going to be so simple in this real world problem.

Lets instantiate a Reality object with a few rods :

val realities : Reality = new Reality(

List (

new PRod("p1","c1",100),

new PRod("p2","c1",100),

),

List (

new SRod("p1","c1",100),

new SRod("p1","c1",100),

new SRod("p2","c1",100),

new SRod("p1","c2",100)

),

List() )

If I were to call "realities.groupBy(f_byProfileAndColour)" I would be aiming for a List of Reality which looks something like :

List (

Reality ( List (("p1","c1",100),("p2","c1",100)),

List (("p1","c1",100),("p1","c1",100)),

()),

Reality ( List (("p1","c1",100),("p2","c1",100)),

List (("p2","c1",100)),

()),

Reality ( List (("p1","c1",100),("p2","c1",100)),

List (("p1","c2",100)),

()),

)

Is it really possible to supply a function to the groupBy function which might achieve this? What on earch might it look like?

I'm not even sure how best to get the groupBy method on the Reality in a scala way.

Should I be making these simple classes extend some sort of trait, and/or using generic types, such that the Reality object itself has a groupBy method?

Should I be implementing a groupBy method myself on the Reality object, in which case, how would I approach what would (in an iterative way) otherwise be a nested for-loop with some simple object cloning through constructors?

I'm seriously intrigued by all this...

Many Thanks,

Ben

On 04/02/2010 19:03, Daniel Sobral wrote:In this kind of situation, I recommend thinking about the types. Let's call the type of reality R.

On Thu, Feb 4, 2010 at 2:22 PM, Dr T B Senior <ben [at] sefol [dot] com> wrote:

It seems I only have four basic functional "archtypes" to worry about :

1) BRANCH

A type of function which takes a (quite complicated "reality" defined as an object), transforms this reality r to reality r',r'',r''....rn according to some function which may execute arbitrarily many times (e.g. trying different sortings of source and target rods) , calls the next required function with each of these generated "realities"

N.B. A reality object contains lists of everything which can be manipulated to create a different outcome, e.g. the list of rods which are to be produced, the list of rods which exist in stores, and the set of all options which can be used to vary how stages of the process are handled.

2) MERGE

A function which passes arguments onto the next function first, then processes a LIST of results (i.e. a list of "realities) which are returned from that next function to select the best one according to various riteria.

3) ITERATE

A type of function which *partitions* the reality in an arbitrary way with a supplied function (e.g. to cluster the desired rods by OrderID, or by Length, or by Colour) where it must then call the next function for each partition, but feed forward the returned "reality" as an input into each successive call and finally return the single processed reality.

4) TRANSFORM

A type of Transformation function which simply transforms a reality, and passes it onto the next function, returning the result from the next function to the previous function.

I'm afraid I'm not really sure how to tighten up the vocabulary here.

In some sort of pseudo way, I'd ultimately like a DSL which looks something (showing a small subset of the complexity) like :

ITERATE(f_byProfileAndColour) > MERGE(f_byWeightings1) > BRANCH(f_bySeriesRods) > BRANCH(f_byPhysicalRods) > ITERATE(f_byOrderID) > MERGE(f_byWeightings2) > BRANCH(f_byMaxStacking) > BRANCH(f_byAltOrReg) > TRANSFORM(f_SimulateCutting)

--

Daniel C. Sobral

I travel to the future all the time.

On Thu, Feb 4, 2010 at 2:22 PM, Dr T B Senior <ben [at] sefol [dot] com> wrote:

R => List[R] Applied to a list, it could be the method map. Or, if you want to join all maps, a flatMap. This one I'm not sure about. I don't quite understand what you are saying. Again, not quite sure. The partition part is easy. As a function, it would receive: (R => A, List[R] => List[List[R]]) That's somewhat similar to Scala 2.8's "groupBy", in fact. It's signature is [R](R => K): Map[K, List[A]]. So you could actually write this: listOfRealities.groupBy(f_byProfileAndColor).valuesIterator.toList Assuming, for instance, that "profile" and "color" are two values of a reality, it would go like this: listOfRealities.groupBy(r => (r.profile, r.color)).valuesIterable You also want to call the next function into each partition, which a simple "map" does, but I'm not sure where exactly do you want to go from there. That's a function R => R. Applied to a List, that's the method R. ( realities .groupBy(f_byProfileAndColour).valuesIterable .map(f_byWeightings1) // type of f_byWeightings1 is List[R] => R .flatMap(f_bySeriesRods) // R => List[R] .flatMap(f_byPhysicalRods) // R => List[R] .groupBy(f_byOrderID).valuesIterable .map(f_byWeightings2) // List[R] => R .flatMap(f_byMaxStacking) // R => List[R] .flatMap(f_byAltOrReg) // R => List[R] .map(f_SimulateCutting) // R => R ) It is missing a final merge, it would seem. You'd have to pass the result of the above, which is a List[R], assuming "realities" is a List[R] as well, to the final merge function. You could define an implicit from List[R] => R: class mergeRealities(realities: List[R]) { def merge(f: List[R] => R) = f(realities) } implicit def toMergeRealities(realities: List[R]) = new mergeRealities(realities) Then you could write it like this: ( realities .groupBy(f_byProfileAndColour).valuesIterable .map(f_byWeightings1) // type of f_byWeightings1 is List[R] => R .flatMap(f_bySeriesRods) // R => List[R] .flatMap(f_byPhysicalRods) // R => List[R] .groupBy(f_byOrderID).valuesIterable .map(f_byWeightings2) // List[R] => R .flatMap(f_byMaxStacking) // R => List[R] .flatMap(f_byAltOrReg) // R => List[R] .map(f_SimulateCutting) // R => R .finalMerge )

--

Daniel C. Sobral

I travel to the future all the time.