fast, strongly typed heterogeneous collections
Hi What is the speed of hProjectByLabel/s in Data.HList.Record? . The documentation in hackage http://hackage.haskell.org/packages/archive/HList/latest/doc/html/Data-HList...does not mention it. Perhaps this is because Hlist is designed for supposedly short records and this does not matter too much. looking at the code I guess that everything in HList is O(n) because it uses type-level list structure, but I think that nothing prevents from using a type level balanced tree, Data.Map style, instead. This would permit to implement large heterogeneous Maps with fast access and strongly typed. AFAIK, the alternative is to use a fast data container with data elements encapsulated within Data.Dynamic, that is weakly typed, produces type errors at runtime, which is unsatisfactory and dangerous. Any comments?
2010/2/19 Alberto G. Corona
What is the speed of hProjectByLabel/s in Data.HList.Record? . The documentation in hackage does not mention it. Perhaps this is because Hlist is designed for supposedly short records and this does not matter too much. looking at the code I guess that everything in HList is O(n) because it uses type-level list structure, but I think that nothing prevents from using a type level balanced tree, Data.Map style, instead.
GHC could inline most of what looks like O(n). And, actually, what looks like O(n) at the compile time is O(1) at runtime. This is so because it is really hard to create types at runtime. ;)
В сообщении от 19 февраля 2010 15:20:30 Serguey Zefirov написал:
And, actually, what looks like O(n) at the compile time is O(1) at runtime. This is so because it is really hard to create types at runtime. ;)
What did you mean by "really hard"? One have to use black magic and ask demons for help or possible but very difficult.
2010/2/19 Khudyakov Alexey
And, actually, what looks like O(n) at the compile time is O(1) at runtime. This is so because it is really hard to create types at runtime. ;)
What did you mean by "really hard"? One have to use black magic and ask demons for help or possible but very difficult.
You could create only certain kind of types in runtime< ones like Peano numbers. I think that complexity of creating, managing and using those numbers (or trees) in runtime with strong type checking at compile time obviously makes creating types at runtime very hard. At least it isn't convenient.
Hi
What is the speed of hProjectByLabel/s in Data.HList.Record? . The documentation in hackage http://hackage.haskell.org/packages/archive/HList/latest/doc/html/Data-HList...does not mention it. Perhaps this is because Hlist is designed for supposedly short records and this does not matter too much. looking at the code I guess that everything in HList is O(n) because it uses type-level list structure, but I think that nothing prevents from using a type level balanced tree, Data.Map style, instead.
This would permit to implement large heterogeneous Maps with fast access and strongly typed. AFAIK, the alternative is to use a fast data container with data elements encapsulated within Data.Dynamic, that is weakly typed, produces type errors at runtime, which is unsatisfactory and dangerous.
Any comments? Hi Alberto, I think this idea isn't unreasonable, and I am curious whether it would
Alberto G. Corona schrieb: pay off in practice. I think you are right with your O(n) guess for the standard HList implementation. Rebalancing the trees at the type level and mirroring the rebalancing efficiently at the term level could be a little bit tricky though. Btw, I found type-level functions to be more comfortable than type classes when playing with heterogenous lists. cheers, benedikt
------------------------------------------------------------------------
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
participants (4)
-
Alberto G. Corona -
Benedikt Huber -
Khudyakov Alexey -
Serguey Zefirov