Persistent Red Black Trees in Haskell. reddit.
red-black-tree: Red Black Trees implemented in Haskell.
Deletion: The curse of the red-black tree
Are open sum types dual to stores with allocation?.
Functor-generic programming. sop-core and streaming are good examples of functor-generic programming.
Why doesn't TypeSynonymInstances allow partially applied type synonyms to be used in instance heads?
A Touch of Topological Quantum Computation in Haskell Pt. II. Type-level tree tricks.
Laziness at type level. "The type level evaluation order is unspecified, so it’s best avoid defining your own control structure functions"
Hide one of the type params of a multi-param typeclass in a function signature
How to work with variations of sum types
Explicit forall on a type class function
comparison of record libraries
generic-data seems quite general
Empirical observations (which might be incorrect):
-
If a typeclass has an associated type family that is expensive to compute, and the type family is "invoked" more than once in the signature of a method of the typeclass, the type family seems to be executed more than once for each occurrence of that method in the code.
-
Auxiliary type families can help to recover sharing in these computations.
-
Type synonyms can't.
-
What about the "constraint trick"? I haven't checked.
-
I still have questions. What about functions whose implementations use these "exensive to compile" typeclass methods, and have themselves type family invocations in their signatures? Is the work doubled?
SO question about this: https://stackoverflow.com/questions/54298813/when-does-type-level-computation-happen-with-type-families
Some confusing (?) results:
- `unI $ snd $ field @"bfoo" s` doesn't seem to be faster than "getFieldI".
- Aumenting the number of getters over 50 doesn't seem to ralentize
compilation time (!?)
- for 50 fields & 50 ops, modifyFieldI does seem to add a second or two vs.
getFieldI.
- using the "constraint trick" to unify the two Value invocations
doesn't seem to change anything either way.
Some conclusions:
- If a typeclass function uses an expensive type family computation twice in its signature, use an auxiliary type family to increase sharing.
- Pull type family invocations out of typeclass parameters, first assign them to a var with ~, then pass the var.
- Type equalities in the preconditions of a typeclass are available for type application at the term level. BUT in some cases they seem to slow things down!? Better pass CmpSymbol k k' as a type parameter each time?