search

CatalaLang / catala

Programming language for literate programming law specification
https://catala-lang.org
Apache License 2.0
1.98k stars 77 forks source link

Add a list sorting builtin to the language #646

Open denismerigoux opened 3 months ago

denismerigoux commented 3 months ago

This feature request comes from exchanges with the CNAF. Its use will be quite broad, and it justifies having this list sorting builtin in the Catala standard library that is implemented and maintained by us. Since it's polymorphic, it will probably require special syntax.

We looking at a function with signature : sort_list : 'a list -> ('a -> int) -> 'a list for elements that have a total order. The sort should be stable.

We may also have sort_list_partial : 'a list -> ('a -> 'a -> int) -> 'a list for elements with a partial ordering, though the need for this relaxed mode is less clear and it could be more confusing to lawyers.

AltGr commented 2 weeks ago

I will not claim that this is an appropriate solution, but this part of #715 seems worth mentioning: https://github.com/CatalaLang/catala/pull/715/files#diff-dbf6a0ad63bfdf74c44a0d71479400669f28e30f2e26a757191fc09745618026R68-R70

Non-polymorphic and quadratic, obviously.