Recursion schemes are elegant and useful patterns for expressing general computation. In particular, they allow you to 'factor recursion out' of whatever semantics you may be trying to express when interpreting programs, keeping your interpreters concise, your concerns separated, and your code more maintainable.
...
In this article I want to avoid building up the machinery meticulously and instead concentrate mostly on understanding and using Edward Kmett's recursion-schemes library, which, while lacking in documentation, is very well put together and implements all the background plumbing one needs to get started.In particular, to feel comfortable using recursion-schemes I found that there were a few key patterns worth understanding:
--Factoring recursion out of your data types using pattern functors and a fixed-point wrapper.
--Using the 'Foldable' & 'Unfoldable' classes, plus navigating the 'Base' type family.
--How to use some of the more common recursion schemes out there for everyday tasks.
(Score: 2, Funny) by Anonymous Coward on Monday December 07 2015, @06:41PM
10 PRINT "HASKELL IS CRAP, BASIC 4 LYFE"
20 GOTO 10
(Score: 2) by Adamsjas on Monday December 07 2015, @06:48PM
Quote: Recursion schemes are elegant and useful patterns for expressing general computation.
What the hell does that even mean?
This is bafflegab of the highest order.
Recursion means a particular thing in computing, and if its not built into your compiler, you are using the wrong compiler.
(Score: 2) by PizzaRollPlinkett on Monday December 07 2015, @08:40PM
I don't know Haskell, but Scheme is a language that uses recursion instead of loops. I guess that the article is talking about letting your compiler turn tail recursion into iterative loops behind the scenes, to allow you to write higher-level programs using recursion but not pay the performance penalty. Surely Haskell's compiler does this, too. I've never found recursion-looping to be intuitive or easy, and neither has most of programming over the past 30+ years, since these languages which do it have always been off in a niche. Whatever elegance it may or may not have, it hurts my brain too much. Sometimes a loop is the most natural way to express something.
(E-mail me if you want a pizza roll!)
(Score: 0) by Anonymous Coward on Monday December 07 2015, @09:52PM
Why write recursive code just to have the compiler change it to a loops and unrolled them?
Because recursion....man. Brogrammers unite.
(Score: 2, Funny) by Anonymous Coward on Monday December 07 2015, @09:58PM
Recursion schemes are elegant and useful for expressing recursion.
FTFY
(Score: 0) by Anonymous Coward on Monday December 07 2015, @11:45PM
What the hell does that even mean?
Two things. First, it means "many useful things can be defined using recursion". Second, it means he's a douche.
(Score: 3, Insightful) by darkfeline on Tuesday December 08 2015, @02:13AM
It means that recursion is elegant and recursion is useful for expressing certain computations. The original isn't written extremely well, but it's still perfectly understandable.
For example,
fibonacci n = fibonacci (n-1) + fibonacci (n-2)
fibonacci 1 = 1
fibonacci 2 = 1
is much clearer, elegant, and useful than
def fibonacci(n):
if n in [1, 2]:
return 1
a = 1
b = 1
for _ in range(3, n+1):
c = a + b
a, b = b, c
return b
Join the SDF Public Access UNIX System today!
(Score: 0) by Anonymous Coward on Tuesday December 08 2015, @08:57AM
And has much worse performance, even with tail recursion elimination, because it contains a recursive call that is not tail recursive. The iterative algorithm is O(N), the recursive O(N^2).
Yes, there are ways to resolve this, by adding complexity in the form of memoization, at the cost of O(N) memory where the iterative algorithm has O(1) memory requirement.
But I know, modern programmers don't care about whether their software scales well. Fuck efficiency, fuck memory, elegance is everything! If you run out of memory, just buy more memory. If it is too slow, just buy a faster computer. After all, money is free </sarcasm>
(Score: 0) by Anonymous Coward on Tuesday December 08 2015, @04:38PM
I don't understand the obsession some people have with recursion. As a theoretical concept, it has its uses. As for it being a practical implementation of an algorithm, usually it is lacking (both in space and time measures). Since recursion can always be replaced with iteration, and iteration, even if you need to include a small stack data structure to do the job, is easily understood by even knuckle-dragging programmers, what is the attraction? It seems more like a puzzle to say you did it using recursion and it still performed well.
Maybe it gives academic compiler writers a source of employment (i.e., papers) to continually work on compiler optimizations to undo the programmer's recursion to the iteration that he just could've just used in the first place.
Recursion is OK if used in limited quantities, like salt on food.
(Score: 2) by darkfeline on Thursday December 10 2015, @02:57AM
Actually, if you only memoize the last two calls, the recursive form runs exactly the same as the iterative form (assuming the recursive function calls are optimized).
And obviously, I only used Fibonacci as an example because it's simple and the first thing I thought of, it's practically the worst thing you can do recursively.
"Oh, the worst thing you can do recursively doesn't perform well when done recursively." Yes, thank you very much.
"Oh, why did you choose it if it's not a good example?" Because I wasn't going to spend half an hour trying to think up a good example, and it demonstrates my point that some things are more elegantly EXPRESSED (read: not executed) recursively.
Recursion is a useful programming tool, just like OOP. That doesn't mean you have to force it onto everything you write (but tell that to the OOP folks).
Join the SDF Public Access UNIX System today!
(Score: 0) by Anonymous Coward on Monday December 07 2015, @07:09PM
(Score: -1, Flamebait) by Anonymous Coward on Monday December 07 2015, @07:25PM
I hope randall munroe dies in a car crash so we don't have to read anymore of his pretentious bullshit reposted by lamers such as yourself.
(Score: 1, Interesting) by Anonymous Coward on Monday December 07 2015, @07:29PM
....don't have to read anymore of his pretentious bullshit reposted by lamers such as yourself.
This is the first post I've ever read that shoots down XKCD.
Is XKCD "over?"
(Score: 0) by Anonymous Coward on Monday December 07 2015, @08:14PM
It's been over.
(Score: 3, Insightful) by Tork on Tuesday December 08 2015, @04:31AM
🏳️🌈 Proud Ally 🏳️🌈
(Score: 0) by Anonymous Coward on Tuesday December 08 2015, @12:44PM
OP here. Popular? With who? Circle jerking nerds who mentally high fiving each other because they all like XKCD? I couldn't stand his webcomics and the incessant linking since people first started linking his drek on the green site years ago.
(Score: 2) by Tork on Tuesday December 08 2015, @06:06PM
🏳️🌈 Proud Ally 🏳️🌈
(Score: 0) by Anonymous Coward on Monday December 07 2015, @07:39PM
if he dies in a car crash I promise to link to his webcomics every time I make a comment here.
(Score: 3, Interesting) by VLM on Monday December 07 2015, @07:38PM
Probably need to start here
http://blog.sumtypeofway.com/an-introduction-to-recursion-schemes/ [sumtypeofway.com]
The documentation for the recursion-schemes library is kinda, uh, lacking. Which probably lead to the linked medium article, which assumes the reader has been Haskell-ized for a couple years.
Every time I try to learn Haskell I start to notice that the people who thought Perl wasn't write-only enough had to end up somewhere and I think I've just found them, then I get worried if I make a typo I'll summon Cthulhu. And then I recover and move on to other things. My ex-favorite window manager was written in Haskell so I kinda had to dive in a little, and its not that bad as long as you dip your little toe in.
I guess an embarrassingly bad one liner of whats going on is functional code has its own "interesting" spots and a very poor analogy is much like you have pointer arithmetic to navigate a data structure you have schemes to navigate a recursive algo. Sorta kinda, if you're really drunk and squint at it just right.
The standard SN car analogy would probably resemble the reaction to the very first Japanese car to import into the USA complete with a Japanese language only technical manual and of course no metric tools and the tech manual is actually a tentacle manga but it takes a couple days for the reader to figure out the true horror of it.
Its purely functional and strongly typed, the sheer weirdness of it can't be understated for 99% of programmers. Its like, imagine modern Perl changed to pure functional and strongly typed but still just as write only as ever. And just like Perl it can and will do anything but you will pay a price that being a small slice of madness.
It never fails to amuse me how noobs can read OO or imperative source and generally know whats going on even without knowing the language, but feed them functional and the WTF anti-lightbulbs all snap on.
Haskell is a real language. Its not intercal. It looks weird when someone shows a page or two of code to turn a string into a vector (equivalent) aka the Perl single line "split" command. None the less its a real language and some hard things are easy in it.... supposedly.
(Score: 3, Interesting) by E_NOENT on Monday December 07 2015, @08:10PM
My ex-favorite window manager was written in Haskell so I kinda had to dive in a little
Xmonad? I'm still on it after 2 (3?) years. Love it, can't bring myself to switch, though I've tried. Glad to run into another fan.
I'm not in the business... I *am* the business.
(Score: 2) by PizzaRollPlinkett on Monday December 07 2015, @08:42PM
Funny you mention INTERCAL. Remember that INTERCAL has a COME FROM statement. I've never bothered to look at Haskell, but I made the mistake of looking at Erlang once. And Erlang has the equivalent of a COME FROM. As I remember it, code starts executing at some random place for no obvious reason that you can figure out from the code itself. That's when I decided to stick to LISP.
(E-mail me if you want a pizza roll!)
(Score: 0) by Anonymous Coward on Monday December 07 2015, @08:44PM
Hard things are hard in Haskell too. The real advantage of Haskell has is that it is easy to abstract patterns with -- some interfaces that look like complete ass in OOP/procedural code can be laid out elegantly with it.
(Score: 2) by Marand on Tuesday December 08 2015, @06:48AM
The problem I have with Haskell is that it's pure functional, which turns a lot of things that should be easy into overengineered messes. I find that something more practical, like Clojure, works out a lot better, pushing you toward functional programming without forcing you to turn everything into over-engineered pure-functional messes. It's the same sort of problem I have with Python with regard to its indentation rules: it's not the language's place to restrict me from doing something in some misguided attempt at "purity". Make the intended style easy to do but don't stop me from doing what I want.
With Clojure, immutability and purity are default, but adding side effects is as simple as adding a (do) form where needed, and mutability is always there waiting with a call to (atom) or (ref). You don't usually need them, you can do most things cleanly without them, but the minute you need your side effects and mutability, the tools are there, waiting to be used. The result is functional programming that's a lot easier to grok than a pure language like Haskell.
It probably helps that the creator of Clojure, Rich Hickey, seems to have his head on straight in regard to practicality vs. purity. The idea is that you can do most of your code the "right" way, with pure functions and immutable state, and easily do the "bad" things in the small portions of code that require it, limiting potential problems with bugs and concurrency to a smaller chunk of the codebase.
If you've got time to waste, you can find a lot of Hickey's talks on Youtube, and they're pretty interesting if you're into this kind of topic at all. This post [changelog.com] is a good starting point, linking to a handful of his talks. I also remember one where he spoke at a Ruby conf (no idea why) being decent, though it overlaps a bit with some of the others in content.
It's not just Clojure, though; I'm finding that the functional style is more agreeable to me in general, at least once the zealous adherence to purity is left behind. Without the zealotry, you end up with a programming style that's generally readable, concise, and flexible enough to implement other styles like OOP where useful. (Rather than using FP, OOP, or anything else as a one-size-fits-all bludgeon.)
(Score: 2) by VLM on Tuesday December 08 2015, @12:43PM
It probably helps that the creator of Clojure, Rich Hickey, seems to have his head on straight in regard to practicality vs. purity.
There's a recent (within the last month) congitek or cognitecht or cognitechcast or WTF they call themselves podcast that mostly interviews clojure-ish people and is a pretty decent podcast, anyway the topic about two episodes ago was its the orthogonality of design that shows its a good design where you can pick and choose components and there's no systemd-style product tying going on where deciding to use feature A automagically creates dependency hell and you gotta haul in B, C, D, ... X, Y and freaking Z too all because you wanted just "A". At least if the design is orthogonal and good that doesn't happen
It was the Liberator / Billy Meier episode. Note there is a much more famous Billy Meier in the UFO-ology field AFAIK they are not the same dude. Although that would be funny if it were true. Its a good podcast but I was disappointed however interesting it was they didn't talk about liberator very much which ironically disappointed me because I am mulling around making a REST interface for another group to use, with liberator. For everyone else reading along, liberator is kinda like the router in ring turned up to a million in capability. That's a bad analogy but I've never seen a description of liberator thats shorter than this entire post, so it isn't so bad. Maybe another awful one liner for liberator is it handles all the HTTP-layer BS for you, liberating you from the task of writing something fluent in HTTP protocol, or something. Anyway its a cool interview although it somehow contains almost no liberator content.
Anyway its just a different way to look at it, that requiring "purity of orthogonality" means you can pick and choose components and its a better worldview than trying "purity of paradigm" which is what you're talking about.
you can find a lot of Hickey's talks on Youtube
All the clojure conj too.
The videos on that list may or may not contain my favorite talk of his which boiled down to why trying to run multi-threaded programs with a non-immutable language is a fools errand. That might or might not be the "Are we there yet" talk.
Hammock driven development is a good video. Its general enough that it could nearly be unleashed upon the normies at a TED talk.
(Score: 0) by Anonymous Coward on Tuesday December 08 2015, @05:00PM
If it really boils down to that, I don't need to see it. It's bullshit. Anything you don't share between threads is no more complicated in multi-threaded programs than in single-threaded ones. That especially includes local variables of automatic storage duration (such as loop counters for iterative implementations of algorithms).
(Score: 2, Interesting) by wirelessduck on Monday December 07 2015, @10:32PM
This article was posted previously. Can we get the editors to stop posting dupes?
https://soylentnews.org/article.pl?sid=15/12/07/0348240 [soylentnews.org]
(Score: 0) by Anonymous Coward on Tuesday December 08 2015, @12:16AM
This comment was posted previously. Can we get commenters to stop posting dupes?
https://soylentnews.org/comments.pl?sid=11011&cid=273081 [soylentnews.org]
(Score: 3, Funny) by Anonymous Coward on Monday December 07 2015, @10:55PM
In order to understand recursion, one must first understand recursion.
(Score: 2) by Subsentient on Tuesday December 08 2015, @05:43AM
I like C. It has its flaws, the string handling functions being by far the worst imho, but as far as functional programming, I never end up wanting a different language.
"It is no measure of health to be well adjusted to a profoundly sick society." -Jiddu Krishnamurti
(Score: 0) by Anonymous Coward on Tuesday December 08 2015, @04:48PM
The string manipulation is not built into the C language -- it is handled by a library. The C standard library string functions suck. Fortunately, this is replaceable by a better library, and everyone always does this. Too bad the C standards committee didn't recognize this and include support in the C standard library for Pascal-style strings that know their length. It would be better if C strings were a struct containing a 32-bit unsigned int for string length and an unsigned 8-bit int * (castable to char* for legacy string function use) to the start of the string data. Internal encoding to be UTF-8, of course. Many people do this, but it ought to be in the C standard library.