[plt-scheme] Help With Abstraction - HtDP 27.2.2

From: David Yrueta (dyrueta at gmail.com)
Date: Tue May 5 00:27:30 EDT 2009

Hi All --

The task of HtDP exercise 27.2.2 is to abstract the two functions
below into a single function:

;; first-line : file  ->  (listof symbol)
;; to compute the prefix of afile up to the first occurrence of NEWLINE
(define (first-line afile)
   [(empty? afile) empty]
   [else (cond
     [(symbol=? (first afile) NEWLINE) empty]
     [else (cons (first afile) (first-line (rest afile)))])]))

;; remove-first-line : file  ->  (listof symbol)
;; to compute the suffix of afile behind the first occurrence of NEWLINE
(define (remove-first-line afile)
   [(empty? afile) empty]
   [else (cond
     [(symbol=? (first afile) NEWLINE) (rest afile)]
     [else (remove-first-line (rest afile))])]))

Because they appear structurally different, though, "first-line" and
"remove-first-line" don't seem to me like good candidates for
abstraction.  While "first-line" appears to be a variant of the
"reduce/combine" abstraction template introduced in 21.5 --

;; reduce : X (X  Y  ->  Y) (listof Y)  ->  Y
(define (reduce base combine l)
    [(empty? l) base]
    [else (combine (first l)
             (reduce base combine (rest l)))]))

-- (the only difference from "first-line" being the lack of
conditional statement ([(symbol=? (first afile) NEWLINE) empty]) --

-- "remove-first-line" only reduces the input list.  As a test, I
tried designing versions of both "first-line" and "remove-first-line"
using the basic structure of the abstract function template "reduce"
from HtDP.   "First-line" was straight-forward:

;reduce-symbols : (listof symbols) (listof symbols) (symbol listof
symbols -> listof symbols) -> listof symbols
;function with two termination cases which consumes and produces a
(listof symbols)
(define (reduce-symbols l base combine)
    [(empty? l) empty]
    [else (cond
            [(symbol=? (first l) NEWLINE) base]
            [else (combine (first l)
                  (reduce-symbols (rest l) base combine))])]))

(define NEWLINE 'NL)
(define list0 (list 'a 'b 'c 'NL 'd 'e 'f))
(define list1 (list 'NL))

(define (first-line-abs alist)
  (reduce-symbols alist empty cons))

(equal? (first-line list0) (first-line-abs list0))
(equal? (first-line list1) (first-line-abs list1))

"Remove-first-line" did not yield to similar efforts.  This leads me
to believe they are structurally different, and not easily

Next I tried to abstract the condition(s) under which the two
functions either "combine/reduce" or just "reduce."  At first, it
seemed that setting 'empty' as the base value triggers the 'combine'
function, so I tried this:

(define (combine-reduce l base combine)
    [(empty? l) empty]
    [else (cond
            [(symbol=? NEWLINE (first l)) base]
            [(empty? base) (cons (first l) (combine-reduce (rest l)
base combine))]
            [else (combine-reduce (rest l) (rest base) combine)])]))

(define (remove-first-line1 alist)
  (combine-reduce alist (rest alist) cons))

That works for any list longer than 1 element.  For a 1 element list,
though, the base evaluates to 'empty,' which changes
"remove-first-line1" from a "reduce" function to a "combine/reduce"
function. Also, having to reduce the base argument via (rest base)
during the recursive call in anticipation of a specific task-- that
is, applying it to the design of "remove-first-line" -- suggests that
"combine-reduce" is not an authentic abstraction.

At this point, I've run out of ideas.  I can't design / find a
template that accommodates abstract versions of both "first-line" and
"remove-first-line," and also can't manage to successfully abstract
the conditions under which the functions vary.  What am I missing?

Many thanks!

Dave Yrueta

Posted on the users mailing list.