Recursion Where it’s not Wanted

So I’m still noodling through “Learn you a Haskell”, and I finally figured out this sentence:

One big difference between the two types of folds is that right folds work on infinite lists, whereas left ones don’t!

When I first read it, I genuinely thought it had been a typo. Folds in Haskell are equivalent to the reduce function in Swift and Scala. They take a closure that takes two arguments, and a list, and they apply that closure to every element of the list and the last value it returned. So something like this:

let closure = {
  (accum: Int, element: Int) -> Int in
  return accum + element
}

let list = [1, 2, 3, 4]

list.reduce(0, combine: closure) // 10

Here, on step 1, the closure gets the initial value, and the first element of the list. So it goes:

accum /** == 0 (which was the 0 given to reduce)  */ + element /** == 1 */ = 1

And this is what’s given to the next closure, which takes the next element of the list:

accum /** == 1 */ + element /** == 2 */ = 3

And so on and so forth.

In Haskell, these functions are a big deal – but they’re called fold. foldl starts from the left, working just like reduce in Swift, whereas folder starts from the right, but works the same otherwise. For the example above, they both give the same answer. And here’s where the brain-bending began for me. Back to the quote:

One big difference between the two types of folds is that right folds work on infinite lists, whereas left ones don’t!

Eh, what? But doesn’t foldr start with the last element? What?!

First off, it might not seem that either would work with an infinite list. I mean, both of them only finish applying the closure when the list is finished, right? Well… not in Haskell. In Haskell, everything is lazy, so not all arguments to a function need to be evaluated. the example given in LUAH is the logical functions:

True && True  == True  // Fair enough. This bit makes sense.
True && False == False // Yes, yes. We all know what the operators do.
False && True == False // Yup.
//BUT:
False && _    == False // _? What does _ mean?

In our case, _ means “anything”. In Swift, it’s referred to as “wildcard”. So, if we were in a dynamically typed language:

False && 1                 == False
False && elephant          == False
False && pasta             == False
False && U2's later albums == False

But we’re not. In Haskell, in particular, since functions don’t automatically evaluate their arguments, that means:

False && (some long, complex, recursive expression) == False

And It doesn’t have to evaluate the expression! That means, as is done in the book, a logical “and” to be used on lists can be defined like:

and' :: [Bool] -> Bool
and' xs = foldr (&&) True xs

And it works!

So how is this relevant to Swift? Well, as it turns out, Swift’s logical operators are also lazy. Meaning that you can define the functions any and all recursively!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s