Levels of recursion
I won't speak for anyone else, but I remember when recursion first "clicked". It was in a 400-level data structures and algorithms class. I had already done a fair amount of chess programming (which of course does a massive amount of recursion), but it still seemed a bit magical to me. When the professor pointed out that you simply have to assume that the recursive call will work, and then the whole recursive definition will, a light bulb went on. Of course, once I started learning haskell, such "aha!" moments quickly became a way of life. Things like map, foldr, and the lazy definition of fibs all made me stop and think for a while, and when I understood them, I was better for it. I had a sort of interesting moment like this last night. In hacking on some code, I wrote the following function: combine :: [Int] -> [Int] -> [[Int]] combine [] _ = [] combine (x:xs) ys = (take x ys) : (combine xs (drop x ys)) To me, this is recursion. Define your base case, take care of one part of the problem, and then call yourself recursively to take care of the rest. This is how I was taught recursion, and this is how I think about it. Now for the fun part. A much more experienced haskeller told me he preferred to write it like this: combine' :: [Int] -> [Int] -> [[Int]] combine' xs ys = snd $ mapAccumL aux ys xs where aux ys n = (b,a) where (a,b) = splitAt n ys Ack! Where'd the nice "base-case, take a chunk, recursively do the rest" pattern go? Suddenly, recursion isn't so simple when it's done using composition and higher-order functions which abstract recursive patterns. Like I said, I'm familiar with map, foldr, etc. But this is the first time it's dawned on me that I need to think in more general recursive patterns like this instead of simple, raw recursion. That map and foldr aren't JUST a nice way of doing things to a little list, but they are recursive operators, building blocks that I need to use as fluently as anything else. I suspect I'm not alone, though of course I could be wrong. But I would bet that a significant difference between newbies and more experienced Haskell programmers is the degree to which they can think in this composition/HOF way. Where the beginner wants to program using raw, simple recursion, the more experienced sees an opportunity to apply an abstraction. So, a couple of questions to ponder about this: Is this unique to Haskell, or could the same be said about any functional language? How can we teach this better to newbies? Most of what I see in the tutorials is "Higher order functions accept as parameters and/or return other functions. Here's some examples: <explanation of map>, <explanation of foldr>. Moving on, ..." But clearly, this is something important, and I think we can do a better job of teaching it. Suggestions?
Hi Andrew, You wrote:
combine :: [Int] -> [Int] -> [[Int]] combine [] _ = [] combine (x:xs) ys = (take x ys) : (combine xs (drop x ys))
...A much more experienced haskeller told me he preferred to write it like this:
combine' :: [Int] -> [Int] -> [[Int]] combine' xs ys = snd $ mapAccumL aux ys xs where aux ys n = (b,a) where (a,b) = splitAt n ys
Ack!
For real work, I like your version better. I might make it a little more clear what I am trying to do by writing it as: combine :: [Int] -> [a] -> [[a]] combine (x:xs) ys = let (h, t) = splitAt x ys in h : combine xs t combine _ _ = [] Raw recursions is a bit like goto in imperative programming - it is often the simplest, but it also can make programs very difficult to understand. But as you point out, you can lose more than you gain with higher-level constructs, unless they are simple, well-documented, and widely used. My favorite geeky way of writing your function would be: combine = evalState . mapM (State . splitAt) But in real life, I like yours better. Regards, Yitz
On 31/01/07, Andrew Wagner
Like I said, I'm familiar with map, foldr, etc. But this is the first time it's dawned on me that I need to think in more general recursive patterns like this instead of simple, raw recursion. That map and foldr aren't JUST a nice way of doing things to a little list, but they are recursive operators, building blocks that I need to use as fluently as anything else.
I suspect I'm not alone, though of course I could be wrong. But I would bet that a significant difference between newbies and more experienced Haskell programmers is the degree to which they can think in this composition/HOF way. Where the beginner wants to program using raw, simple recursion, the more experienced sees an opportunity to apply an abstraction.
So, a couple of questions to ponder about this: Is this unique to Haskell, or could the same be said about any functional language? How can we teach this better to newbies? Most of what I see in the tutorials is "Higher order functions accept as parameters and/or return other functions. Here's some examples: <explanation of map>, <explanation of foldr>. Moving on, ..." But clearly, this is something important, and I think we can do a better job of teaching it. Suggestions?
This is absolutely correct. I suppose I was lucky in that it was probably my first epiphany of functional programming, and came before I'd really learned much Haskell at all. I somehow determined that working on understanding the translation from loops in the imperative programming I knew to map, filter, zip, fold and so on was going to be important, which helped a lot. I had a good time taking things that way, and I certainly think it should be a key point near the beginning of any functional programming tutorial. Higher order functions, and higher-order list processing functions in particular, are the control structures of functional programming. They stick everything else together. They are every bit as important as loops are to the imperative programmer. They can also be more natural ways of thinking about how things fit together than the imperative approach offers. My friend, who'd had a bit of C++ and a bit of Java, (and had pretty much hated it), preferred the Haskell approach. He gave me the example that "map wash dishes" is a whole lot closer to what you're thinking when washing dishes than numbering the dishes and incrementing a counter, washing dish n at each step. This approach to functional programming is especially important in a lazy language, since it works so well. Lists are, in a sense, loops which haven't yet happened, and much of programming is done by transforming them. Due to laziness, those elements not needed won't be computed, which is a similar capability as that of being able to break out of a loop early. This inversion allows you to essentially extend the code which would be in the "loop body" after the fact (that is, without modifying the existing code), which is not something you could do in a strict imperative language unless you'd specifically provided for passing in a continuation in the loop, or were modelling lazy lists somehow. Eventually, you come to mostly forget about loops and just think in terms of the lists themselves, but it's a very useful alternate view to have handy. Of course, lists aren't the only data structure just as loops aren't the only kind of recursion. Laziness basically makes data structures into tools giving you the ability to "reify" recursion such that only those steps which end up needed later on are actually carried out. - Cale
On 1/31/07, Andrew Wagner
So, a couple of questions to ponder about this: Is this unique to Haskell, or could the same be said about any functional language? How can we teach this better to newbies? Most of what I see in the tutorials is "Higher order functions accept as parameters and/or return other functions. Here's some examples: <explanation of map>, <explanation of foldr>. Moving on, ..." But clearly, this is something important, and I think we can do a better job of teaching it. Suggestions?
The first time I really thought about this much was after reading Meijer, Fokkinga and Patterson's "Functional Programming with Bananas, Lenses and Barbed Wire," which makes the comparison between arbitrary recursion and goto early on, and develops four replacement operators (cata-, ana-, hylo-, and paramorphisms). At the time, I was involved in teaching an introduction FP class in which we frequently discovered that students would latch onto primitive recursion early in the course and never stop using it, even as their functions became more convoluted and using maps and filters correspondingly easier. My natural thought was to wonder if the beginning of the course could be rewritten without primitive recursion, only introducing it later after the students were already comfortable with the higher-order combinators. Sadly, that never went anywhere. I'd be interested in hearing if anybody else got farther in attempting that teaching technique. /g -- It is myself I have never met, whose face is pasted on the underside of my mind.
participants (4)
-
Andrew Wagner -
Cale Gibbard -
J. Garrett Morris -
Yitzchak Gale