Improve handleArcs function in translate/Main.hs

[jrbeaumont]

This was designed to include OR-causality handling, and has been tested and working, but was done quickly and without much thought on efficiency.

A TODO has been included in the code, but this issue serves to document it better.

What needs to be done:

• [x] Get rid of explicit recursion. Possibly by using groupBy
• [ ] Generally improve performance.

[snowleopard]

I suggest to have a look at function groupSortOn in Data.List.Extra library: https://hackage.haskell.org/package/extra-1.5/docs/Data-List-Extra.html

[jrbeaumont]

groupSortOn requires that the type we're testing for is of type Ord.

[jrbeaumont]

groupOn might work. I'm trying that now

[jrbeaumont]

@snowleopard: OK groupOn doesn't work either. It groups them individually by snd but not all where snd are grouped together. groupSortOn would probably do the same

[jrbeaumont]

For example: arcs = [([A+, B+], C+), ([A-], C-), ([B-], C-), ([D+], C+), ([E+], C+), ([D-,E-], C-)] This is: orGate a b c <> andGate d e c

When using groupOn or groupSortOn, the result is:

[A+,B+] C+
[A-] C-
[B-] C-
[D+] C+
[E+] C+
[D-,E-] C-

It doesn't combine them like I hoped. I was hoping for:

[[A+, B+], [D+], [E+]] C+
[[A-], [B-], [D-, E-]] C-

[snowleopard]

groupSortOn would probably do the same

@jrbeaumont No, actually it will sort them and then group, which is what we need. It does require a more complex constraint Ord instead of just Eq, but I think this is not a big deal for us. Essentially we ask for a to be not only comparable by ==, but also by <, so I suggest to try it.

[snowleopard]

When using groupOn or groupSortOn, the result is:

Could you show the code?

[jrbeaumont]

@snowleopard The latest version is in my repo: [https://github.com/jrbeaumont/concepts]

[jrbeaumont]

@snowleopard: Currently this doesn't print anything usable by a .g parser, just what the list contains for debugging.

[snowleopard]

Just an experiment:

Prelude Data.List.Extra> let arcs = [([1,2], 'a'), ([3], 'b'), ([4,5], 'a')]
Prelude Data.List.Extra> let grouped = groupSortOn snd arcs
Prelude Data.List.Extra> grouped
[[([1,2],'a'),([4,5],'a')],[([3],'b')]]

So it looks like groupSortOn does sort elements. There is still a bit of work to be done though :)

[snowleopard]

By the way, without Ord constraint we wouldn't really be able to improve efficiency of the code anyway.

[jrbeaumont]

Yeah I found an issue. Take a look at lines 36-44 in translate/Main.hs

This is what I've had to do to include Ord for DynSignal, as well as Ord for Transition a in order for this to work. Are you aware of a better way?

I understand the importance of Ord but I couldn't find the best way to do it. The whole thing works with this.

[snowleopard]

Mmm, what about data DynSignal = Signal Int deriving (Eq, Ord)? :)

Otherwise, I'd implement it as:

instance Ord DynSignal where
    compare (Signal x) (Signal y) = compare x y

[jrbeaumont]

Mmm, what about data DynSignal = Signal Int deriving (Eq, Ord)? :)

I have tried that, and it just throws errors in the handleArcs function, needing Ord x => included, but I cannot work out what to put there, as there isn't an a or something associated with DynSignal.

So I added my own instance. compare x y is the same, but a better than (<=) ... I'll pop that in :)

[jrbeaumont]

Fixed in #51