[Enh]: implement {Expr,Series}.approx_quantile in Narwhals #4105

We would like to learn about your use case. For example, if this feature is needed to adopt Narwhals in an open source project, could you please enter the link to it below?

We are currently building internal tooling for our company that leverages narwhals as a compatibility layer between different data sources or dataframe libraries (parquet files read through pandas/polars, Snowflake tables). This has been massively beneficial, but there are some optimizations that are missing from the Narwhals API. For example, we often will calculate summary statistics over millions of rows and thousands of columns, so operations like quantile over an entire table involve sorts over thousands of columns.

Please describe the purpose of the new feature or describe the problem to solve.

Polars released several new functions as of v2.0.0. One of these was approx_quantile which allows a user to approximate quantiles, sacrificing accuracy for speed and reduced memory footprint.

Suggest a solution if possible.

Implement approx_quantile as a function in the Narwhals API.

Several full API support libraries in Narwhals already has or has recently implemented this functionality:

• cuDF has an exact flag, where exact = False corresponds to approximate quantile.
• Polars has this recently implemented
• Pyarrow uses tdigest to calculate approximate quantiles.

From what I can tell, Modin and pandas do not support approx_quantile, but for full compatibility, one could use the exact quantile method instead.

Approximate quantile calculations are also supported in the Lazy-only support libraries:

• Dask uses its own algorithm and exposes 'tdigest' as well as two approximate quantile methods.
• DuckDB offers approximate quantiles with t-digest
• Ibis also has this
• PySpark has approxQuantile using Greenwald-Khanna
• SQLFrame implements PySpark Dataframe API and supports approxQuantile.
• Daft offers an approx_percentile expression as well.

If you have tried alternatives, please describe them below.

No response

Additional information that may help us understand your needs.

I would be interested in opening a pull request to fix this, but have not previously contributed to narwhals or any other open source project. My coworker (@CangyuanLi) has also offered to open a PR to address this issue as we both are working on the same internal tooling.