Everything is a fold! or is it?
As any other novice in Haskell I've noticed I can write "map" and "filter" in terms of fold. I suspect I could write scan (so unfolds) in terms of folds as well.
I've looked in vain for a proof or a hint generalizing this: could any (higher order?) function be written as a fold (or nested folds)? could you find a counter-example?
Thank you!
Posted Sep 17, 2016, 6:31 AM UTC
66
For proof or counterexample, you'd have to specify more precisely what you mean by "in terms of folds". One possible question would be, "given a function
f, are thereg, zsuch thatf = foldr g z?"You're right, I didn't define what I'm looking for precisely, mainly because I'm still trying to wrap my head around it too hehe. Edward Yang linked me to http://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/urs.pdf
I thought so; therefore I asked for a more precise definition, which is usually the first (sometimes also the last) step to enlightenment. ;)
Besides, a word of caution (such as to not further perpetuate the myth that you need a Ph.D. to do Haskell): Expect to understand not a word of that paper if you're just starting out with folds. From a quick skimming, it assumes a lot of mathematical machinery as well as a modicum of familiarity with functional programming. I'd like to stress that none of this theory is necessary (or, I'd argue, even particularly helpful) for standard functional programming, even though one can certainly find it interesting.
Thank you! I've been dabbling with Haskell for a few years (I do Elixir for work), but definitely not an advanced Haskeller. I've started reading the Hutton article which looks much more approachable :)