Create a NFData instance for Trie

user_8661022 0
Viewed 213

I'm currently working on a project using the vcache-trie module. I'm looking to test the execution speed of a research inside the trie with the lookupPrefix function.

This is a benchmark created with Criterion for this purpose :

bench "trieSearch"  $ nf (lookupPrefix (pack "ab")) trie

where trie is created in an environment for criterion. The type of this trie is Trie Int.

As the environment is evaluated to normal form I need to create an instance of NFData for this specific type.

The content of the trie for this specific case is [(ByteString, Int)], I assume the instance of NFData should evaluate each tuple but I'm not sure how to proceed.

Any help would be greatly appreciate, thanks for taking the time to read my issue.

haskell
2 Answers

The following should do the trick, but may be slightly less efficient than writing an NFData with access to the internal representation (as suggested by @JonPurdy):

instance NFData a => NFData (Trie a) where rnf = rnf . toList
user_7916040

Ideally, you should contact the maintainer of vcache-trie with a feature request or patch to add the instance, since you would need access to the internal representation of Trie in order to write it.

As a workaround, you can make a locally modified version of the package (e.g., adding a local checkout to extra-deps in Stack) and either add an NFData instance yourself, or add deriving (Generic) to Trie and use deepseq-generics to implement NFData.

user_2468860
Related