Comments (6)
I'm surprised GHC doesn't turn uncurry edge
into your edge'
automatically. You could perhaps add a rewrite rule so that the user code also benefits from this optimisation (uncurry edge
might be common).
What about edges = overlays . map (\(x, y) -> edge x y)
? This doesn't require an extra function.
By the way, here is how uncurry
is implemented:
uncurry :: (a -> b -> c) -> ((a, b) -> c)
uncurry f p = f (fst p) (snd p)
from alga.
Perhaps, the problem is that the call to uncurry
is partially applied and GHC does not want to inline it.
This may be a relevant SO thread:
from alga.
@nobrakal I just realised that your new implementation is not equivalent to the original one: the strictness properties are different:
> g = edges [undefined]
> isEmpty g
False
> g = newEdges [undefined]
> isEmpty g
*** Exception: Prelude.undefined
The reason is that you pattern match on the tuple constructor (x, y)
in edge'
, but uncurry
doesn't.
I wonder if it is possible to both keep the full laziness and increase the performance.
from alga.
@snowleopard Ah I didn't thought about strictness.
Looking a the code produced by GHC, with the current lazy implementation:
Rec {
-- RHS size: {terms: 21, types: 33, coercions: 0, joins: 0/0}
Algebra.Graph.edges1 [Occ=LoopBreaker]
:: forall a. [(a, a)] -> Graph a
[GblId, Arity=1, Caf=NoCafRefs, Str=<S,1*U>]
Algebra.Graph.edges1
= \ (@ a_a8YM) (ds_icea :: [(a_a8YM, a_a8YM)]) ->
case ds_icea of {
[] -> Algebra.Graph.Empty @ a_a8YM;
: y_icef ys_iceg ->
Algebra.Graph.Overlay
@ a_a8YM
(Algebra.Graph.Connect
@ a_a8YM
(Algebra.Graph.Vertex
@ a_a8YM (case y_icef of { (a1_aclW, b1_aclX) -> a1_aclW }))
(Algebra.Graph.Vertex
@ a_a8YM (case y_icef of { (a1_acm1, b1_acm2) -> b1_acm2 })))
(Algebra.Graph.edges1 @ a_a8YM ys_iceg)
}
end Rec }
[...]
edges
= \ (@ a_a8YM) (x_ic4h :: [(a_a8YM, a_a8YM)]) ->
Algebra.Graph.edges1 @ a_a8YM x_ic4h
Using edge'
:
Rec {
-- RHS size: {terms: 18, types: 28, coercions: 0, joins: 0/0}
Algebra.Graph.edges1 [Occ=LoopBreaker]
:: forall a. [(a, a)] -> Graph a
[GblId, Arity=1, Caf=NoCafRefs, Str=<S,1*U>]
Algebra.Graph.edges1
= \ (@ a_a8Wo) (ds_icbK :: [(a_a8Wo, a_a8Wo)]) ->
case ds_icbK of {
[] -> Algebra.Graph.Empty @ a_a8Wo;
: y_icbP ys_icbQ ->
Algebra.Graph.Overlay
@ a_a8Wo
(case y_icbP of { (x_a798, y1_a799) ->
Algebra.Graph.Connect
@ a_a8Wo
(Algebra.Graph.Vertex @ a_a8Wo x_a798)
(Algebra.Graph.Vertex @ a_a8Wo y1_a799)
})
(Algebra.Graph.edges1 @ a_a8Wo ys_icbQ)
}
end Rec }
So yes, all of this is a strictness issue !
Not sure what is the good way to go because I don't see a solution:
Either you pattern match for tuple before Connect
either you use fst
and snd
after Connect
from alga.
@nobrakal I think I'd prefer to keep edges
maximally lazy.
My understanding is that edgesOrd
will have to be strict, since it will be comparing actual values in the list of edges, so let's keep edges
as a maximally lazy alternative.
from alga.
I guess we can close thig now, since it doesn't seem possible to make uncurrying faster while staying lazy.
from alga.
Related Issues (20)
- Algebraic trees HOT 3
- Hackage Release HOT 5
- How to handle goodness inherited from other libraries HOT 2
- Bump upper bound for base-compat for version 0.4 on Hackage HOT 4
- Unable to use ghcid HOT 6
- Algorithms should be in terms of typeclasses not data structures HOT 15
- Acyclic graphs with Int labels HOT 5
- Tests failed to build with QuickCheck 2.14.2
- Multitree HOT 3
- Monoid instance HOT 6
- support for GraphViz "HTML strings" for node or edge labels HOT 1
- Add benchmarks to CI HOT 2
- Supporting different node and edge types HOT 7
- v0.6 fails to build with GHC 8.0 and 8.2 HOT 3
- Doubt about decorating a Graph HOT 4
- Compatibility with mtl-2.3 HOT 2
- Smart constructor for Symbol rather than requiring -XOverloadedLists HOT 1
- Proposal : foldgM HOT 2
- Algebra.Graph.Labelled.AdjacencyMap.edges appears to be broken HOT 2
- Semigroup version of Algebra.Graph.Labelled.AdjacencyMap HOT 7
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from alga.