Question: Are lazy patricia trees and laziness necessary?

[MisanthropicBit]

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]

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.