Is the PatriciaTree matchGr too strict?
- Dominant language
- Haskell
- Stars
- 200
- Forks
- 58
- PR merge metrics
- No merged PRs in 30d
Description
I was trying to figure out the time complexity of `suc` which lead me to the `matchGr` function.
https://github.com/haskell/fgl/blob/86dc04d2ae9ca73a0923bdc8d78b53bf2f2876c8/Data/Graph/Inductive/PatriciaTree.hs#L146-L158
All the work being done with the bang patterns does not seem to be necessary for the `suc` function as far as I can tell. I think the strict evaluation could cause the asymptotic complexity of the `suc` function to change from `O(k + min(n,W))` (where `k` is the number of nodes in the output and `n` and `W` are the familiar `IntMap` variables) to `O(n)` (because of the `clearPred` and `clearSucc` functions). Should this be rewritten to:
```Haskell
matchGr :: Node -> Gr a b -> Decomp Gr a b
matchGr node (Gr g)
= case IM.lookup node g of
Nothing
-> (Nothing, Gr g)
Just (p, label, s)
-> let g1 = IM.delete node g
p' = IM.delete node p
s' = IM.delete node s
g2 = clearPred g1 node s'
g3 = clearSucc g2 node p'
in (Just (p' `seq` toAdj p', node, label, toAdj s), g3 `seq` Gr g3)
```
Or something similar.
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.