From ce10606b3b1de35a37d4f4df12eeedd1e434b0e1 Mon Sep 17 00:00:00 2001 From: jim Date: Sun, 22 Feb 2015 16:51:32 -0500 Subject: [PATCH] add paragraph about Little Schemer --- topics/week4_fixed_point_combinators.mdwn | 11 +++++++++++ 1 file changed, 11 insertions(+) diff --git a/topics/week4_fixed_point_combinators.mdwn b/topics/week4_fixed_point_combinators.mdwn index 41a52737..c904bdc8 100644 --- a/topics/week4_fixed_point_combinators.mdwn +++ b/topics/week4_fixed_point_combinators.mdwn @@ -178,6 +178,17 @@ Many simpler functions always *could* be defined using the resources we've so fa But functions like the Ackermann function require us to develop a more general technique for doing recursion --- and having developed it, it will often be easier to use it even in the cases where, in principle, we didn't have to. +The example used to illustrate this in Chapter 9 of *The Little Schemer* is a function `looking` where: + + (looking '(6 2 4 caviar 5 7 3)) + +returns `#t`, because if we follow the path from the head of the list argument, `6`, to the sixth element of the list, `7` (the authors of that book count positions starting from 1, though generally Scheme follows the convention of counting positions starting from 0), and then proceed to the seventh element of the list, `3`, and then proceed to the third element of the list, `4`, and the proceed to the fourth element of the list, we find the `'caviar` we are looking for. On other hand, if we say: + + (looking '(6 2 grits caviar 5 7 3)) + +our path will take us from `6` to `7` to `3` to `grits`, which is not a number but not the `'caviar` we were looking for either. So this returns `#f`. It would be very difficult to define these functions without recourse to something like `letrec` or `define`, or the techniques developed below (and also in that chapter of *The Little Schemer*. + + ## Using fixed-point combinators to define recursive functions ## ### Fixed points ### -- 2.11.0