Reading group: Learn You a Haskell: Part Two

Haskell
1

This Friday, February 21, we’ll do our second discussion of Learn You a Haskell For Great Good!

The next couple chapters are very dense, so I suggest that we only cover two:

  • Recursion
  • Higher Order Functions

I checked, and the HTML and PDF chapters correspond.

I will be in New York on Friday, so I’ll conference in for the discussion.

2

@jferris How are you guys handling this book club ? Or it is this just for the Haskell discussion board?

3

@Rafael_George we’re doing this as a group in the Boston thoughtbot office. If you’d like to read along, you’re more than welcome to, and definitely feel free to post any thoughts or questions here.

4

@jferris Sounds good; thanks

5

From our discussion today, we covered:

  • Recursive edge condition
  • Infinite recursion (take 5 $ repeat 3)
  • Currying - (a -> a -> a) = a -> (a -> a)
  • Higher order functions, map, filter
  • Lambdas
  • Folds
  • Function application with $
  • Function composition with .
  • Pointfree style

We cleared up the type definition of $:

($) :: (a -> b) -> a -> b

Everything left of :: is the function name; everything to the right is the type. If you add parenthesis, you can see that $ takes a function and returns the same function:

($) :: (a -> b) -> (a -> b)

We learned that function application has precedence over operators, so a b $ c d is the same as (a b) $ (c d). We also touched on the fact that infix functions (like operators) can be given custom precedence.

We also discussed how foldr works with infinite lists, but I don’t remember what the specific issue was. @pat / @derekprior - can you guys explain what the confusion was here and how we cleared it up?

6

Sure!

I was confused when the book says “foldr folds right-to-left”, then goes on to say “foldr can work on infinite lists”. Since infinite lists have no right, this doesn’t seem to make sense. Where does it start?

The confusion (I think) comes from what we think of as “starting”.

foldr builds up a set of function calls from right-to-left, like so:

-- Generically
x = foldr f z [1, 2, 3]
x = f 1 (f 2 (f 3 z))

-- A concrete example
sum = foldr (+) 0 [1, 2, 3]
sum = (+) 1 ((+) 2 ((+) 3 0))

-- Again, but written as infix
sum = 1 + (2 + (3 + 0))

You’ll notice that this indeed “starts” on the right with (+) 3 0 and folds “to the left” applying your function to each successive result in an outward fashion.

Since haskell is lazy, the evaluation of the functions will start on the left.

sum = 1 + (... + (... + (... + ...

And if the function used doesn’t always need to evaluate its second argument, it simply never will. If this were the case, the ... above wouldn’t matter and thus, could be infinite. The example the author uses is (&&) folded over an infinite list of False values.

A left fold, on the other hand, folds left-to-right:

sum = foldl (+) 0 [1, 2, 3]
sum = ((0 + 1) + 2) + 3

Think about (lazily) evaluating this function and convince yourself that it can’t do anything until it finds the end of the list:

sum = ... + ...) + ...) + ...) + ?
2 Likes