Resource: Fixed-point combinator

lkbaerenfaenger
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 13. Mär 2012 12:44

Resource: Fixed-point combinator

Beitrag von lkbaerenfaenger »

Hi all,

last Friday in the group exercise it was announced that we should take a look at fixed-point combinators before the next group exercise. It took me quite some time to find a non-cryptic explanation, but eventually I found one. So It thought I'd save you guys the trouble:

https://medium.com/@ayanonagon/the-y-co ... 268d8d9c46

The author gives a quick intro to the lambda calculus and then proceeds to the Y combinator, which is "one of the most well-known fixed-point combinators in untyped lambda calculus" (Wikipedia). She even applies it in a practical example (factorial).

Cheers :mrgreen:

paprikawuerzung
Mausschubser
Mausschubser
Beiträge: 80
Registriert: 23. Mär 2014 23:33

Re: Resource: Fixed-point combinator

Beitrag von paprikawuerzung »

I also enjoyed this one :lol:

https://www.youtube.com/watch?v=FITJMJjASUs

(you can skip the start - he explains computability, lambda calculus, etc. and afterwards he implements the ycombinator iteratively)

(btw jim weirich died last year - his last commit: https://github.com/jimweirich/wyriki/co ... 901617c2d4 )

memovsgodzilla
Neuling
Neuling
Beiträge: 6
Registriert: 18. Apr 2013 19:48

Re: Resource: Fixed-point combinator

Beitrag von memovsgodzilla »

I want to recommend this one.

http://www.berniepope.id.au/docs/open_recursion.pdf

Its really good, it explain fixed points with no lambda calculus and very little mathematical words.
It goes directly to the code all in scala and it shows an actual good motivation for fixed points (memoization) which makes everything more clear.
Once I understood the difference between open recursive and closed recursive function, fixed points make sense and they can be used for interesting use cases other than "emulating recursion LOL".

paprikawuerzung
Mausschubser
Mausschubser
Beiträge: 80
Registriert: 23. Mär 2014 23:33

Re: Resource: Fixed-point combinator

Beitrag von paprikawuerzung »

They are useful? Say one real-world application of a fixed-point combinator, which is faster and more readable than a not fixed-point version :lol:

From the PDF you linked (last slide):

(I know I am risking being really, really wrong, but I think if you would use a fixed-point combinator in the code-base of any project, the other developers wouldn't be that happy - not because they can't understand it, but because it's inherently more difficult to figure out than a straight forward and also correct version without it :D )
Dateianhänge
asdjask.png
asdjask.png (49.67 KiB) 1144 mal betrachtet

memovsgodzilla
Neuling
Neuling
Beiträge: 6
Registriert: 18. Apr 2013 19:48

Re: Resource: Fixed-point combinator

Beitrag von memovsgodzilla »

Well I never said its better, but if you look into memoization there are some good use case there, and it can actually make the code more readable since you are not putting everything in one function you use composition to plug different functions together, and that also makes your code more scalable and maintainable. So for cases where you have lots of functions working together in a very functional programming style, fixed points are pretty cool. I dont know many problems that are solved with recursion, so its hard to give good examples. Maybe when working with fractals? or signal processing? I dont know.

Edit: You can write ugly code with any paradigm,language or style. For sure fixed points can get complicated, but if done right they can be useful, thats why I like the example in the url I post because I wasnt happy with the supposedly motivation given in the lecture.

paprikawuerzung
Mausschubser
Mausschubser
Beiträge: 80
Registriert: 23. Mär 2014 23:33

Re: Resource: Fixed-point combinator

Beitrag von paprikawuerzung »

Yeah, I think fixed-points are cool, too! Memoization itself can easily be implemented without fixed-point combinators and you can have scalable code without fixed-point combinators, too.

Other combinators like map, filter, etc. have an apparent use-case.

It would be interesting to know what "real", non-mathematical, non-academical use-cases for fixed-point-combinators there are!

memovsgodzilla
Neuling
Neuling
Beiträge: 6
Registriert: 18. Apr 2013 19:48

Re: Resource: Fixed-point combinator

Beitrag von memovsgodzilla »

I agree, well I think fixed points are not that complicated once you really get the idea of how the "fix" function works,
the rest is just adapting your function to have the same definition. In the world of objects pluging functions doesnt seem very intuitive but with
functional programming it seems to make more sense. Also recursion is more popular. The thing is Im not very familiar with scala or any functional
programming language, but I guess for big systems that are implemented in scala fixedpoints can be a good option if the problem demand it(recursive + requires modularization)

Antworten

Zurück zu „Archiv“