Consider adding `converge` and friends.

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Consider adding `converge` and friends.

Ignat Insarov
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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Consider adding `converge` and friends.

Henning Thielemann

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#v:mapAdjacent
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Consider adding `converge` and friends.

Bardur Arantsson-2
In reply to this post by Ignat Insarov
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 :)

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Consider adding `converge` and friends.

Andreas Abel
In reply to this post by Ignat Insarov
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
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries