> splitting a string into words not very intuitive
It seems okay?
split :: String -> [String]
split s = w s "" where
w [] "" = []
w [] a = [reverse a]
w (' ':ss) "" = w ss ""
w (' ':ss) a = reverse a : w ss ""
w (c:ss) a = w ss (c:a)
If you're done then you're done (and dump the accumulator), if it's a space get rid of it (and dump the accumulator), otherwise add it to the acuumulator. That the accumulator is stored backward is a bit wierd, but seems more a consequence of linked lists than recursion per se.
Yeah it's ok ;) Going back to my original comment this code is exactly what I meant with "patterns to deal with other problems". You clearly used a pattern (accumulator) with wich you are familiar.
Do you agree that most imperative programmers would not come up with this solution on their own, if you didn't teach them the "accumulator pattern"?
For me personally a tutorial with a lot code like that would be interesting.
Showing me another version of a recursive descent parser doesn't teach me anything, because I know how to write it (with recursion!!!) in an imperative language...
Do you agree that most imperative programmers would not come up with this solution on their own, if you didn't teach them the "accumulator pattern"?
Background: I’m currently working as a full time assistant for the first year computer science course at my university. We have around 1800 people enrolled in the class including over 1000 first year CS students. Many of our first years were exposed to imperative programming in high school, either at home or with a high school CS class.
The course we teach is based on the book HTDP and uses a purely functional teaching dialect of Racket. Many of our students struggle to figure out how to use the different recursion patterns such as accumulative recursion and mutual recursion.
I’m not the GP but I will answer your question anyway: yes, I agree that most imperative programmers would not come up with that solution. I have witnessed it myself first hand.
Where I disagree is with any implication or suggestion that they should, given no prior functional programming experience. Accumulative recursion is a standard pattern in functional programming but if you’re an imperative programmer you may not have ever needed to learn it. Therefore, I think it would be unreasonable to expect you to come up with it on the fly.
> You clearly used a pattern (accumulator) with wich you are familiar.
No, I didn't, and please refrain from imputing thought processes without evidence. I didn't even think the word "accumulator" until I got to the last paragraph and needed a term to describe the second argument to w.
> Do you agree that most imperative programmers would not come up with this solution on their own
If we assume most imperative programmers are idiots as a special case of most people are idiots, sure. I'm not sure that's a good assumption or particularly relevant, though.
> Showing me another version of a recursive descent parser doesn't teach me anything
Ah, I think I misunderstood your point, then:
> > Which problems are hard to solve with recursion instead of iteration?
> I found something like splitting a string into words not very intuitive...
I assumed you meant that "splitting a string into words" was a example of a problem that was hard to solve with recursion (which I found rather puzzling, because as my example shows, it really isn't), rather than that it wasn't a good/intuitive example to illustrate recursion in the general case (which makes a quite a bit more sense, and I'm afraid I don't have a immediate solution to, sorry).
> There where at least two other replies talking about accumulators. I call that pattern, like it or not.
It's true that you use this way of programming so often in functional languages that it earned itself a name, so that it's easier to talk about it. However calling it a 'pattern' feels weird (to me), even though it technically is one.
The equivalent of accumulators in imperative languages would be the 'pattern' of having some variables outside of the loop and mutating them from within the loop. Maybe you can appreciate that it feels weird calling this a 'pattern' — and now you can better understand how I feel about accumulators being called a pattern.
Skipping back to your original question: I write Haskell for living and teach two high-school classes in another functional language, and the only two 'patterns' regarding recursion I can think of are accumulators and mutual recursion. So, you know almost everything there is to know already! :-) [0]
Let me add that you use recursion very rarely in day-to-day programming; mostly you try to spare yourself writing the recursion explicitly and you instead use map, filter and foldr/foldl (sometimes called reduce) to do the recursion for you. Especially the folds are super-powerful (AFAIK you can write any recursive function using folds, should you wish to do so), and often under-appreciated.
> Haskell is a genius language but I don't like the community
IMHO the community around Haskell is (in general) great; the people are always eager to help. I'm a self-learned Haskeller and I couldn't have done it without the community. Come join us at r/haskell or the IRC and see for yourself :-)
[0]: Why do I say this? I remember my old days when I was learning Swift and encountered one new design pattern every day. Factory, Facade, ... I decided to get 'em all (why reinvent the wheel?), I was always anxious that I was coding something that could be better served by a ready-made design pattern. So I just wanted to let you know it's nothing like this with recursion, and that you can save yourself the anxiety (if you are anything like me).
Hey thanks for the nice reply. I know you can't generalize like that. There are probably a lot friendly Haskellers around ;)
I was just angry when I wrote my last comment, because I had to read this:
>> as a special case of most people are idiots
which is so low in multiple ways. It's also just wrong, because by definition most people have average intelligence. Even if you think this is true, a smart person would not use it as an argument^^
It's on my todo-list to dive a bit into haskell, when I find time.
> It's true that you use this way of programming so often in functional languages that it earned itself a name, so that it's easier to talk about it. However calling it a 'pattern' feels weird (to me), even though it technically is one.
> The equivalent of accumulators in imperative languages would be the 'pattern' of having some variables outside of the loop and mutating them from within the loop. Maybe you can appreciate that it feels weird calling this a 'pattern' — and now you can better understand how I feel about accumulators being called a pattern.
That's a fair point, actually. I read "patterns" as "design patterns" a la the book of same name, based on the implied^Wlater stated title "accumulator pattern", but I agree it does fit a weaker notion of "pattern" such as "less-than-maximally-entropic (aka compressible in the information-theoretic sense) feature of code".
It seems okay?
If you're done then you're done (and dump the accumulator), if it's a space get rid of it (and dump the accumulator), otherwise add it to the acuumulator. That the accumulator is stored backward is a bit wierd, but seems more a consequence of linked lists than recursion per se.