[Haskell-cafe] Incredibly slow type-level Nub

[Richard Eisenberg]

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 <nickolay.kudasov at gmail.com> wrote:

> 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
> 
> [1] https://gist.github.com/fizruk/06458fe8b62a1e562af1
> [2] http://hackage.haskell.org/package/servant-swagger-1.0.2/docs/Servant-Swagger-Test.html
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20160207/c18b9622/attachment.html>