[racket] a small programming exercise

From: Nadeem Abdul Hamid (nadeem at acm.org)
Date: Thu Oct 14 12:39:23 EDT 2010

> Thanks for setting my head straight!


Oh, I wasn't meaning to do that! :)

Incidentally, why does your solution run even when the language level
is set to "Intermediate Student"? In fact, even mine runs in ISL while
I use lambda. I'm running DrRacket, version 5.0.1.7--2010-10-06.

--- nadeem


On Thu, Oct 14, 2010 at 12:29 PM, Matthias Felleisen
<matthias at ccs.neu.edu> wrote:
>
> I ran this stress test for your 5 line solution and mine:
>
>> (define *the-list* (build-list 10000000 (lambda (i) (random (+ i 1)))))
>> (time (______ *the-list*))
>
> For small benchmarks, your solution may take twice as long as my 8 line ASL solution,
> but for something of the above size -- there can't be that many lakes in MN -- it takes
> almost the same time.
>
> In short, don't be afraid of 10 iterations over long lists, and don't bother with
> hash tables and fancy algorithmics until you know you need it -- by measuring.
>
> I used to believe this but have temporarily forgotten this lesson due to external influences.
>
> -- Matthias
>
>
>
>
> On Oct 14, 2010, at 12:09 PM, Nadeem Abdul Hamid wrote:
>
>> Here's a solution in ISL:
>>
>> ;; benson : [listof positive-number] -> [listof (list number number)]
>> (define (benson a-lon)
>>  (let ([digs (map (compose
>>                    string->number first explode number->string
>> exact->inexact) a-lon)])
>>    (build-list 10
>>                (λ(i) (list i
>>                            (/ (length (filter (λ(d) (= i d)) digs))
>>                               (length digs)))))))
>>
>>
>> ;; TESTS (matthias' and jay's, modified)
>>
>> (require racket)   ; (only-in ... for/list)
>>
>> (check-expect (filter (lambda (p) (not (zero? (second p))))
>>                      (benson '(123 124 125 126 23 24 31)))
>>              (list (list 1 4/7) (list 2 2/7) (list 3 1/7)))
>>
>> (check-expect
>> (benson (list 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 0.10
>>            11 12 13 14 15 16 17 18 19
>>            21 22 23 24 25 26 27 28
>>            31 32 33 34 35 36 37
>>            41 42 43 44 45 46
>>            51 52 54 54 55
>>            61 62 63 64
>>            71 72 73
>>            81 82
>>            91))
>> (for/list ([i (in-range 10)])
>>   (list i
>>         (/ (- 10 i)
>>            (+ 10 9 8 7 6 5 4 3 2 1))))
>> )
>>
>>
>>
>>
>> On Thu, Oct 14, 2010 at 11:30 AM, Matthias Felleisen
>> <matthias at ccs.neu.edu> wrote:
>>>
>>>
>>> I love this solution but let me supply a solution in ASL, the teaching language:
>>>
>>>
>>> ;; ASL
>>> (require racket) ; (only-in ... hash->list)
>>> ;; I could have used the key for sort to get around the second lambda
>>>
>>> ;; [Listof String] -> [Listof (cons Digit Nat)]
>>> ;; compute a frequency count of the leading digit in the number of lon
>>> ;; assume: the digits are positive
>>> (define (collect lon)
>>>  (local ((define loch (map (compose string->list number->string) lon))
>>>          (define (upd c H) (hash-set H c (+ (hash-ref H c 0) 1)))
>>>          (define hash (foldl (lambda (x H) (upd (first x) H)) #hash() loch))
>>>          (define loh# (hash->list hash))
>>>          (define srtd (sort loh# (lambda (l r) (> (cdr l) (cdr r))))))
>>>    (map (lambda (x) (cons (string->number (string (car x))) (cdr x))) srtd)))
>>>
>>> (check-expect (collect '(123 124 125 126 23 24 31))
>>>              (list (cons 1 4) (cons 2 2) (cons 3 1)))
>>>
>>>
>>> If actual I/O is required, I'd use batch-io to read CSV files and
>>> display the list above in a batch action.
>>> _________________________________________________
>>>  For list-related administrative tasks:
>>>  http://lists.racket-lang.org/listinfo/users
>>>
>>
>>


Posted on the users mailing list.