search

haskell / fgl

A Functional Graph Library for Haskell
http://hackage.haskell.org/package/fgl
Other
185 stars 54 forks source link

Question: Are lazy patricia trees and laziness necessary? #61

Closed MisanthropicBit closed 7 years ago

MisanthropicBit commented 7 years ago

I have recently read Martin Erwig's papers and looked over the fgl library. The graphs are backed by a Patricia tree through Data.IntMap which, as far as I can tell, defaults to Data.IntMap.Lazy.

I am currently considering porting parts of the fgl to another functional language that is strict by default, so I was wondering if the performance hinges on the lazy implementation or not? None of the papers mention laziness as a requirement for the backing data structure or even for the graph's implementation language, but I can understand why it would be the default in a language like Haskell.

ivan-m commented 7 years ago

I doubt it.

Note that strictness in this aspect refers to the keys/structure; the actual values in a strict IntMap remain lazy.

The only time laziness may play a part is in some kind of tying-the-knot aspect if e.g. you have a node's label be dependent upon its value (using newNodes or some such function), but then that's al algorithmic aspect and - at least in Haskell - that's where the laziness of the values can help.