Introduction

Trevor says there were three points here in the introduction:

• first class functions
• no side effects
• lazy evaluation

Why was lazy evaluation a new kind of glue?

• "Lazy evaluation let you glue functions together in new ways because

  you could separate what you're generating from how you want to generate it."

Gluing functions together

What was the foldr function about?

• It's the same as the eject function (in ruby), or reduce (in python)

• foldr as in "fold right" versus left

• Also, foldr was mentioned but not foldl, because fold left has to go te the end of the array (and thus means recurring to the bottom of the possibly infinite list).

• foldr count, given Cons 1 (Cons 2 (Cons 3 Nil)), is functionally a replacement of each Cons with count:

  count 1 (count 2(count 3 nil))
  

• Kyle notes that there's also pattern matching or destructuring in how we define foldr:

  (foldr f x) Nil = x
  (foldr f x) (Const a l) = f a ((foldr f x) l)
  

  This is basically a case statement -- if the element to folder is an empty list, then return x. Else, if there's a list has at least one element, i.e. (Const a l), then return recur and call f with a and (foldr f x) l.

How do we make sense of this MIRANDA syntax? How about an example with count?

• Suppose we're trying to get the count of items in a list:

  length x = foldr count 0 x
  

  Here, we're defining length as a function that calls foldr with three arguments, count, the integer 0, and x. Note well: the syntax we see in the paper has ommitted the x (Dan notes something about Bacchus and not naming arguments).

  The second function, then is:

  count a n = n + 1
  

• In python, this would be:

  def count(a, n):
      return n + 1
  

fandncons, doubleall

• fandcons f = Cons . f

• doubleall, for instance, takes one argument, a list:

  doubleall = foldr(Cons . double) Nil

  but can be modularized further, if we have map:

  doubleall = map double
  

What's the difference between map() and reduce()?

• map takes each item and a list and converts it to a new item, returning a list of the same length
• reduce takes each item in a list and returns a single thing (the result of calling the reduce function recursively). ((of course, that single thing can be a list))

Does this paper still matter?

• It seems like most of what we're seeing here is already available: I can do this now with much easier syntax in Ruby.
• True, but, Ruby wasn't around in 1990.

Trees and nodes

We see the tree:

  1
 / \
2   3
    |
    4

written as:

Node 1
    (Cons (Node 2 Nil)
          (Cons (Node 3
                      (Cons (Node 4 Nil) Nil))
                Nil))

What is the Nil about at the end?

• That last Nil is an empty list -- it's the second argument to the (Cons (Node 3 ...) ...). It means there's only one child in the 3 node of the tree.

How do we make sense of the foldtree definition?

• foldtree f g a (Node label subtrees) = f label (foldtree f g a substrees) and so on.
• It's another case statement -- if the tree has no nodes, some nodes, etc, then return different things.
• Kyle notes that in foldtree's functional args, f and g, one applies to the leaf and one applies to when you're folding the leaves together.

Making sense of sumtree:

• sumtree = foldtree (+) (+) 0
• In this case, we replace Node with f and Cons with g

Making sense of maptree:

• maptree f = foldtree (Node . f) Cons Nil
• here, Node is composed with f. The reason for this, Kyle notes, is because foldtree is going to visit every node in the tree -- and here we want to return a Node for every Node we visit! Thus we call Node(f(x)) for each x in the tree.
• also here, Cons means you simply take a list of Nodes and return that same list!

What did label mean?

• That is just the label of the node -- it is the * in:

  treeof * ::= Node * (listof (treeof *))
  

Gluing programs together

How do we get a square root:

• The square root of n is a, such that a = (a + n/a)/2

• We then create:

  next n x = (x + n/x)/2
  

• Calling this enough times, we get a good approximation:

  repeat f a = Cons a (repeat f (f a))
  

• But, it runs forever. So, we make it break up:

  sqrt a0 eps n = within eps (repeat (next n) a0)
  

  where within returns b if abs(a - b) <= eps, else returns within eps (Cons b rest)

How is this improved using a ratio between successive approximations?

• It is observed that if the square root is very small or very big, then both your next and your next next will be within the error range of your floating point. At that point, you may want to do this instead.
• The author's point here is that you can easily change this algorithm in functional programming by replacing only the within function, so that it divides next by next next, and compares it to 1.

It's observed that one of the nice things in this paper is how the generator of an inifinite list, such as repeat, can be used not only for this use in approximation, but also for many other purposes.

It is also observed, as a sidebar, that Mark Jason Donis' (sp?) blog/magazine, and elsewhere, that many of the design patterns of yesteryear are now language features, or else, as Kyle observes, should be.

Higher Order Perl is recommended highly be a number of folks, incidentally, as one of the best introductions to functional programming.

How we do the same sort of approximation, but this time with differentiation:

• You guessed it, using another lazily evaluated recursive function!
• There's some fancy math for eliminating the error term -- basically folding in the removed error terms.
• Interestingly, the improve function here gets you close to the target of your optimization much faster than with the square root algorithm above?

Conclusion

Could any of this not be done just with Python generators?

• Not that we can tell, in this series of examples.

Kyle analogizes the functional/structured question to the two sides of the garbage collection debate: C programmers are right that you aren't managing memory with garbage collection, but Java programmers did save a lot of time by having garbage collection. He argues that the same can be the case in immutability, where he gets to avoid state. In his case, if performance becomes a problem, he can always drop down into the JVM.

Picking papers

Dan says, look up "referential transparency". He recommends the first ten pages of Bacchus' paper "Can computer programming be liberated from ...": it defines what's wrong with wrong with imperative languages and how they got improved upon in Haskell/ocaml/MIRANDA. Ben recommends "Tackling the awkward squad": How Haskell went from an ideal to making it work in the real word. He also recommends Guy Steel's work.

It's remarked that perhaps more contemporary papers would be good.

Trevor says we're doing continuations a little later in the series.

For the next meeting: Ben is the moderator, Nick is the notetaker!