Folds and parallelism

Those are some good examples of using the Par monad.

I was once asked during an interview to transform a tree into a linked list. The interview went pretty well, but immediately after leaving, I was struck by l'esprit de l'escalier and this nice one-liner (featured in the article) popped into my head:

    toList = foldr (:) []

It's the identity function on lists, but it can actually transform any Foldable into a list as well, and it's very efficient. O(n) for trees, very little overhead, and lazy. I believe it's used in a number of Haskell containers.

Slightly off-topic but if anyone is interested in the awesome resources buried deep in university pages, I've tried to compile a few courses[0] that have all their lectures & assignments available online (CS240h is one of them). Feel free to send PRs!

[0] - https://github.com/prakhar1989/awesome-courses

I'm reminded a little of Guy Steele's talk, "Organizing Functional Code for Parallel Execution; or, foldl and foldr Considered Slightly Harmful" (http://vimeo.com/6624203).

The author's definition of foldr is wrong, which makes the post pretty much impossible to understand if you don't already know what it's trying to say.

The correct definition, in the author's style, is

    foldr :: (a -> b -> b) -> b -> [a] -> b
    foldr f = go
      where
        go z (x:xs) = f x (go z xs)
        go z []     = z

It's better written with the cases for go reversed, so the base case comes first, or without the helper function at all, as

    foldr :: (a -> b -> b) -> b -> [a] -> b
    foldr f z [] = z
    foldr f z (x:xs) = f x (foldr z xs)

But I suppose that if you're reading this then you already knew that. I'm really writing because I noticed that this submission, like another submission that made the front page of HN twice in the past two days [0], touches on the same material as Ch. 6 of Richard Bird and Philip Wadler's book Introduction to Functional Programming [1], which I happened to be re-reading a couple of nights ago. And I want to tell you to go read it.

Really, if you find this sort of thing interesting, you should read it. The book isn't strictly a Haskell book—it was published in 1988, just as Haskell's designers (the book's authors among them) were getting going. But their book remains one of the best, most timeless introductions to programming in a lazy functional language. It's written in a sort of functional pseudo-code (which Haskell aspires to be) and captures all of the excitement and optimism of the coming of age of functional programming in the years after Miranda.

Bird and Wadler's book is quite different from standard contemporary recommendations like Learn You a Haskell for Great Good; it's more like an extended version of John Hughes's famous paper Why Functional Programming Matters [2], which is to say that it makes the case for functional programming over imperative programming and illustrates the strengths of lazy evaluation. The book continues on from the basics to discuss evaluation strategies, efficiency, and other practical mid-level topics in some depth, without breaking stride; it doesn't touch much of the algebraic or categorical underpinnings of Haskell, which is the relative strength of an introduction like Learn You. That makes the two together a great one-two punch for learning Haskell.

0. https://news.ycombinator.com/item?id=8645292

1. http://www.nlda-tw.nl/janmartin/vakken/TFIT/Extra%20materiaa... [PDF]

2. http://worrydream.com/refs/Hughes-WhyFunctionalProgrammingMa... [PDF]

"Parallel and Concurrent Programming in Haskell" by Simon Marlow is a great resource: http://chimera.labs.oreilly.com/books/1230000000929

Post related to folds and parallelism:

https://news.ycombinator.com/item?id=8646181

haskell