Dear Cafe,
I have faced a type-level performance problem (with GHC 7.10.3). I am trying to implement type-level Nub which removes duplicates from a type-level list. My implementation [1] with an example of a list of length 20 takes forever to compile. If you reduce the size of the example list (e.g. to 15 items), it will compile faster. Also, if you remove the Nub application from exampleVals, it compiles instantly (this is how I know the problem is in Nub). My question is how can I speed up type-level Nub? And less importantly why exactly is it this slow? The practical application for this is building automatic tests [2] for servant-swagger. There I am interested in generating exactly one test for each distinct type. Kind regards, Nick _______________________________________________ Haskell-Cafe mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe |
If you have a practical example of where GHC's current type-level reduction machinery is too slow, please post a bug report. We have only a few real examples of this, and so GHC's implementation is tuned for those examples. With more examples, we can tune more widely. Thanks! Richard On Feb 7, 2016, at 8:37 AM, Nickolay Kudasov <[hidden email]> wrote:
_______________________________________________ Haskell-Cafe mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe |
In reply to this post by Nickolay Kudasov
Hi Nickolay, I'm not sure why your version was *that* slow. But the algorithm was not optimal. I translated the Haskell Report prelude version of nub to the type level. That version compiles instantly with the long list. I tested with GHC 7.10.2. Regards, Roel 2016-02-07 14:37 GMT+01:00 Nickolay Kudasov <[hidden email]>:
_______________________________________________ Haskell-Cafe mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe |
Roel, thanks, your solution works perfectly for me! I should've checked that implementation myself. Richard, since Roel's solution works for me, I think I should not file this. I think type-list [1] is the place on Hackage for list-related type-level functions. I probably should send a PR adding Roel's Nub there. Thanks for your help! Nick On Sun, 7 Feb 2016 at 18:24 Roel van Dijk <[hidden email]> wrote:
_______________________________________________ Haskell-Cafe mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe |
In reply to this post by Nickolay Kudasov
I suppose that a problem is with "non-lazy type-level If". Best regards, Dmitry 2016-02-07 16:37 GMT+03:00 Nickolay Kudasov <[hidden email]>:
_______________________________________________ Haskell-Cafe mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe |
In reply to this post by Nickolay Kudasov
Hello, I wonder if singletons library doesn't satisfy your requrements? Did you look at this opportunity? Here is a Nub implementation. I am particulary interested in this because I am checking now this library for usung it in my project. Had you some reasons to refuse it? Best regards, Dmitry 2016-02-07 16:37 GMT+03:00 Nickolay Kudasov <[hidden email]>:
_______________________________________________ Haskell-Cafe mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe |
Dmitry,
Well, actually, I was not aware that singletons provide this functionality! From what I see singletons seem to be an overkill for my use case. Thanks for the hint though, I will look into singletons more to see if it fits the bill. Kind regards, Nick On Mon, 8 Feb 2016 at 13:21 Dmitry Olshansky <[hidden email]> wrote:
_______________________________________________ Haskell-Cafe mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe |
Free forum by Nabble | Edit this page |