• QuestionsHarperHigherOrderFunctions

Per request of AdamChlipala, I am reducing the number of pages I create. All questions for a particular chapter will be placed in one page in reverse chronological order (most recent questions at the top)

Overview

This page concerns questions in the chapter entitled "Higher Order Functions" in Robert Harper's SML Book.

Patterns of Control

My first set of questions revolves around his discussion and implementation of several reduce functions. We start with the following definition of an append function for lists that takes both arguments at once:

fun append (nil, l) = l
| append (h::t, l) = h :: append(t,l)

Harper then provides the following scenario:

Suppose that we will have occasion to append many lists to the end of a given list.

Ok, I'm already lost. As far as I can tell, a list only has one end and therefore can only have one thing appended to it. I think this is what he means:

val fixed_list = [1,2,3];
val m = [4,5,6];
val n = [7,8,9];
val p = [10,11,12];

(* and here we append many lists to the end of a given list, namely fixed_list *)

val f_m = A(fixed_list, m);
val f_n = A(fixed_list, n);
val f_p = A(fixed_list, p);

Is this what he means?

What we’d like is to build a specialized appender for the first list that, when applied to a second list, appends the second to the end of the first. Here’s a naive solution that merely curries append:

fun curried_append nil l = l
| curried_append (h::t) l = h :: append t l

To this he says:

Unfortunately this solution doesn’t exploit the fact that the first argument is fixed for many second arguments. In particular, each application of the result of applying curried append to a list results in the first list being traversed so that the second can be appended to it.

Ah yes, I see, he has not saved himself the process of heading and consing the first list before getting to the next list.

Harper improves on this by staging the computation as follows:

fun staged_append nil    = (fn l => l) 
  | staged_append (h::t) = 
   let 
       val tail_appender = staged_append t 
   in 
    fn l => h :: tail_appender l 
   end