Consider adding `converge` and friends.
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
On Thu, 20 Aug 2020, Ignat Insarov wrote:
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.
This one may help: https://hackage.haskell.org/package/utility-ht-0.0.15/docs/Data-List-HT.html...
On 20/08/2020 18.36, Ignat Insarov wrote:
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.
FWIW, I've had occasion to have to implement both converge and convergeBy (albeit in Scala), albeit very rarely. My case was one of post-processing a linear list of 'instructions' to remove useless ones -- e.g. adjacement push-pop, etc. Easier to do just do it be repeated application than trying to figure out how to do it in a single pass. +½ from me, I guess :)
Here are some related functions for fixpoint computation: http://hackage.haskell.org/package/Agda-2.6.1/docs/Agda-Utils-Function.html On 2020-08-20 18:36, Ignat Insarov wrote:
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 _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
participants (4)
-
Andreas Abel -
Bardur Arantsson -
Henning Thielemann -
Ignat Insarov