Higher-order list operations
matt.might.net
matt.might.net
And that reminds me, lately I have been kicking around a suspicion that, given the right example, it wouldn't be hard to understand how to use call/cc to implement a lazy function in Scheme--perhaps one that returns a lazy list of the natural numbers.
As a step in that direction, I managed to construct the following example, which I hope is pretty clear.
; Return anon function returning its argument's value at n: _(n).
(define (at n) (lambda (s) (s n)))
; The curried (schönfinkeled) function t(m, n) = 2m+n: (t m) returns anon function 2m+_.
(define (t m) (lambda (n) (+ (* 2 m) n)))
; Example of using these "at" and "t" together.
(define (f n m) ((at n) (t m))) (display (f 5 3)) (newline); 11
(display (f 3 5)) (newline) ; 13
; Write an equivalent function inside-out using call/cc!
(define (g n m) ((t m) (call/cc (at n)))) (display (g 5 3)) (newline) ; 11
(display (g 3 5)) (newline) ; 13
In fact, monads were secretly used throughout the article in the form of the comprehension notation (which desugars to the List monad).
There's also a tight connection between continuation-passing style, continuations and monads.
More on that in a future post...
That's a major topic in my compilers class, and I'll likely write a post on that as well.
In the meantime, I recommend you check out "Scrap Your Boilerplate" in Haskell.
I don't know if my teaching style would translate well to Coursera or Udacity.
My classes tend to be very interactive. Assuming I recorded in front of a live class, some of that would come across.
But, it would lose some of the spontaneity that comes from sitting in the class and being able to interject.
I do post my (unanimated) lecture slides online as pdfs.
Well, trees are recursive. Sometimes the cost bugs me, so I implement the tree as a list of lists ( each level in tree is its own list) ... this brings costs down but the code looks nasty and lot more bookkeeping under the hood. If anything, I've fallen in love with recursion all over again...it is so bloody natural
If you want more versatile functions, you could look at the famous "Bananas, Envelopes, Lenses and Barbed Wire" paper which introduces a bunch of recursion schemes that apply to trees as well as lists and other structures. These have Greek names you might have heard like "catamorphism" (a generalized fold).
Even if you don't end up using the functions, it's a good read. Might be a bit dense though, but it's not that bad or terribly heavy on math.
When I learned C and Unix, the instructor had us reimplement libs like string.h and stdio.h, command line tools like date, ls and cut and then build tools like make.
It made me a much better C programmer.
I think a nice approach would be to start off with a high-level, functional language like Haskell or Scheme, and then move down the ladder of abstraction in subsequent courses, culminating in a hardcore C (or maybe even assembly) course.
Overall, it's a pretty good system. The middle Java class was completely worthless and a big waste of time though; in hindsight, I should have skipped it. Also, while we learned a bunch of cool things in the SICP class, every single other class except for programming languages/compilers completely ignored it. Most retaught some of the same concepts, but poorly.
Also, apart from SICP, there aren't any undergraduate classes doing functional programming! What's up with that?
At least at my university, there's plenty of C and C++--even in places where it blatantly doesn't fit, like the other version of the compilers class. And far, far too much Python. And too little functional programming. Ah well, c'est la vie.
I would love a compilers course taught in ML (maybe OCaml?), and it's a possibility, but not before I graduate :(.
I had to discover and learn Haskell on my own :)
I also had to find Haskell on my own, but I think it worked out reasonably well in the end. The type theory/semantics class did use a bit of OCaml, but it took a while to get to it.
Also, I should add that--largely due to my own preferences--I've taken a disproportionate number of classes that do not really focus on programming at all. The aforementioned type theory/semantics course only had a token amount of programming, and three other CS classes had no programming at all. They were also some of the coolest and most fun. (After all, I can do programming on my well enough; theory is a bit harder.)
1.) http://yannesposito.com/Scratch/en/blog/Haskell-the-Hard-Way...
The simplest is map. It turns out that there are a ton of types that you can map a function over, and many of them are extremely useful. There are obvious examples like trees and arrays, but they don't even have to be containers. In Haskell, we call any type with a map function that behaves like the standard list function a functor. This is all a functor is--pretty simple.
The next interesting example is fold. We can also fold over non-list structures. In this case, the structures are usually containers like trees and arrays.In Haskell, this is what the Foldable class represents.
You can also think of zipping--in a very abstract sense of applying a multi-argument function to a bunch of structures--as generalized by applicative functors. However, lists by default form an applicative functor with pairwise application rather than zipping; there is a wrapper called ZipList that does a normal zip. Applicative functors also come up very often, not just for container types.
All these generalizations let you take all the powerful list functions you're familiar with and use them in new contexts. They also let you write more polymorphic code.
Interestingly, you can also generalize these functions in a different way--instead of taking a different structure, take a different function. This is where monads come in: you can generalize these functions over monads. In Haskell, the generalized versions are named by a trailing M: foldM, mapM and so on.
At a high level, this lets you customize how functions get applied. So you can have a fold that maintains internal state, propagates errors or even computes the result non-deterministically. The exact behavior is specified very declaratively by your choice of monad.
And, of course, as with any good abstractions, you can combine these. Particularly, you can take a foldable and use a bunch of the monadic functions on it. So you might end up using a non-deterministic fold on a tree. Just by itself, this seems exotic and hard to grasp. However, since it was built up step-by-step from familiar abstractions, it's actually easier to understand. Each step along the way is relatively simple and intuitive; you just have to put them together.
Now, what are the benefits to all this? The main one is that it gives your code more structure. A map a fold always behaves the same way for a given type where a for-loop could be doing anything. This makes it easier to read because you know the structure of the computation just from its name. It also makes the code easier to write since all the iteration logic is hidden away; you only have to write the function dealing with one "step"which means you cannot accidentally mess up how the steps are combined (no more off-by-one errors) and you can't accidentally couple the computation itself with the iteration logic. They're guaranteed to be separate because one is encapsulated into the higher-order function.
In many ways this parallels the transition from goto to structured programming.
Another advantage is that it lets you write more generic, more polymorphic code. This sort of code is easier to write because the types are more restrictive. There are simply less ways to mess up. Also, naturally, the code is more general, letting you reuse it in more places.
This is imho the most important bit an imperative programmer needs to learn and understand functional.