Consider adding `converge` and friends.

Ignat Insarov kindaro at gmail.com
Thu Aug 20 16:36:31 UTC 2020


Hello…

This function first appeared _(to my knowledge)_ in [a Stack Overflow
answer][1]. I found it useful several times, and eventually [I extended it to a
family of 4 derived functions][2]: `converge`, `convergeBy`, `fixp` and
`fixpBy`.

* `convergeBy` is like `takeWhile` but with a binary predicate.
* `converge` cuts a list at a point where it starts to repeat itself.
* `fixp` takes the last element.

These operations are useful in many practical cases. For example, the
Newton-Raphson approximation method:

    λ r a = \x -> (x + a/x) / 2
    λ fixp (r 2) 1
    1.414213562373095

Or let us compute the alternating group A₄:

    λ import qualified Data.List as List
    λ xs */ ys = fmap (xs !!) ys
    λ generate1 gens elems = List.union elems [ elem */ gen | elem <-
elems, gen <- gens ]
    λ ε = [0.. 3]
    λ rota3 = [1, 2, 0, 3]
    λ rota3' = [0, 2, 3, 1]
    λ length $ fixp (generate1 [rota3, rota3']) [ε]
    12

I propose adding these functions to `Data.List`.

[1]: https://stackoverflow.com/a/7443379
[2]: https://stackoverflow.com/q/48353457


More information about the Libraries mailing list