Higher-order list operations

http://matt.might.net/articles/higher-order-list-operations/

by Adrock • 13 years ago

91 24 13 years ago

matt.might.net

gridaphobe3• 13 years ago

Learn You A Haskell is a really great book for newcomers to functional programming, I can't recommend it enough.

It also takes the same approach as the posted article: reimplementing basic standard library functions. It's really enlightening.

mattmight4• 13 years ago

I love the "reimplement the standard library" approach to learning a programming language.

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.

danenania• 13 years ago

While I've heard good things about LYAH, I personally found its approach to be too wordy with too many not-illustrative-enough examples for each concept, and ultimately confusing. I felt like I gained a much better understanding from 2 hours spent reading "Learn Haskell Fast And Hard"(1) which is more concise, pragmatic, and presents a better logical build up of explanation and examples.

1.) http://yannesposito.com/Scratch/en/blog/Haskell-the-Hard-Way...

ced• 13 years ago

Manipulating lists is a solved problem in functional programming IMO, but I struggle to define good higher-order tree operations. Complex operators compose very poorly, and have too many options. So instead I write many simple operators, most of which I don't use frequently enough to remember that they exist at all. Or, I just give up and use recursion.

mattmight4• 13 years ago

Stay tuned.

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.

tel• 13 years ago

SYB is basically required reading... but Uniplate is much easier to grasp at first, I feel.

cgag• 13 years ago

Is there any chance of you ever doing your compilers class on Coursera or just posting videos of the lectures online somewhere? Your blog posts are great, I'd love to be able to see the lectures as well.

dxbydt• 13 years ago

> I give up and use recursion.

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

tikhonj4• 13 years ago

Maps and folds, at the very least, generalize to trees fairly naturally. They also behave essentially the same way as for lists.

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.

tikhonj4• 13 years ago

One really cool thing is that you do not you do not need to stick to lists. Many of these functions naturally generalize to other data types.

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.

Jare• 13 years ago

> In many ways this parallels the transition from goto to structured programming

This is imho the most important bit an imperative programmer needs to learn and understand functional.

seanmcdirmid• 13 years ago

But it's not necessary to use these operations with functions at all; they were mostly invented and refined in the array programming space like APL. Just in a functional language you have all those nice lambdas to help out and can keep your language simple.

drallison• 13 years ago

Another insightful note from Matt Might. There's more in his blog, http://matt.might.net/articles/.

minopret• 13 years ago

I haven't actually learned monads yet, but am I correct that the end of this article leaves readers a hair's breadth away from an introduction to monads (and without another round of distracting analogies)?

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

mattmight4• 13 years ago

You're absolutely right that the end of the article is a hair's breadth away from monads.

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.

Higher-order list operations

Related Stories