[racket] in praise of if's mandatory else clause

From: Matthias Felleisen (matthias at ccs.neu.edu)
Date: Tue May 31 08:41:18 EDT 2011

Nice generalization of the days in a month function. This is called generative recursion, and no, there's nothing but Eureka :-) 


On May 31, 2011, at 1:07 AM, Richard Cleis wrote:

> Buggy loops can also be avoided by reducing the problem.  These leap-year cases are less troubling if the function that really matters is used: the days in a given year.
> 
> (define (days-in-year year) (if (= 0 (remainder year 4)) 366 365))
> 
> (define (yr-da yr da)
>  (cond  ((<= da (days-in-year yr)) (values yr da))         ; Done: da is within the year, yr.
>         (else (yr-da (+ 1 yr) (- da (days-in-year yr)))))) ; reduce da by days in the year, yr.
> 
> A little rearranging can remove the inefficiency of computing days-in-a-year twice.
> 
> But how would I arrive at that solution by using the blue book?
> 
> rac
> 
> 
> On May 30, 2011, at 8:31 PM, Matthias Felleisen wrote:
> 
>> 
>> On May 30, 2011, at 9:11 PM, Richard Cleis wrote:
>> 
>>> An HtDP solution would more likely describe the data first (days are less than 366, equal to 366, or greater than 366). One cond would handle all three, two would terminate, and the the last would continue the accumulation. 
>> 
>> I had actually written the program in HtDP style, and yes, the accumulator made it clear that the if was wrong: 
>> 
>> ;; N -> [List N N N] 
>> (define (my-date days)
>> ;; N N -> N 
>> ;; accu: y is the number of complete years between days and d, plus 1980
>> ;; gen. recursion (subtract number of days until the number is w/i a year)
>> (define (year d y)
>>   (cond
>>     [(<= d 365) (values y d)]
>>     [else (if (leap-year? y) 
>>               (cond
>>                 [(> d 366) (year (- d 366) (+ y 1))]
>>                 [(= d 366) (values y d)])
>>               (year (- d 365) (+ y 1)))]))
>> (define-values (the-year remaining-days-in-year) (year days 1980))
>> ;; N N -> N 
>> ;; accu: m is the months between remaining-days-in-year and d, starting in Jan
>> ;; gen. recursion (subtract number of days until w/i a month) 
>> (define (month d m)
>>   (cond
>>     [(<= d (month->days m the-year)) (values m d)]
>>     [else (month (- d (month->days m the-year)) (+ m 1))]))
>> (define-values (the-month remaining-days-in-month) (month remaining-days-in-year 1))
>> ;; -- IN -- 
>> (list the-year the-month remaining-days-in-month))
>> 
>> ;; N -> Boolean 
>> ;; simplistic definition 
>> (define (leap-year? y)
>> (= (remainder y 4) 0))
>> 
>> ;; N N -> N 
>> ;; the number of days in month m for year y 
>> (define (month->days m y)
>> (case m 
>>   [(1 3   5   7 8   10 12) 31]
>>   [(    4   6     9 11)    30]
>>   [else (if (leap-year? y) 29 28)]))
>> 
>> ;; -- testing --- 
>> 
>> (check-equal? (my-date 364) '(1980 12 29))
>> (check-equal? (my-date 366) '(1980 12 31))
>> (check-equal? (my-date (+ 365 366)) '(1981 12 31))
>> (check-equal? (my-date (+ 365 365 365 366)) '(1983 12 31))
>> 
>> (define long 
>> (let ([years# (- 2009 1980)])
>>   (apply + (build-list years# (lambda (i) (define y (+ i 1980)) (if (leap-year? y) `366 365))))))
>> 
>> (check-equal? (my-date long) '(2008 12 31))
>> 
>> 
>>> In other words, the possibility of that hard-to-read bug doesn't exist.
>> 
>> There are bugs in FP programs for sure, but the [while-]loop  exit bugs disappear. 
>> 
>> 
> 




Posted on the users mailing list.