[racket] First try with hashes in Racket

Hi Neil and Racket-users,

Thanks for the good inputs.  Using your help I rewrote Euler #14:

; recursive function that returns the chain length of the passed argument
; invoked as (collatz-length hash-table-instance n)
(define (collatz-length ht n)
  (define colval (hash-ref ht n #f))
  (unless colval
      (if (even? n)
          (set! colval (add1 (collatz-length ht (/ n 2))))
          (set! colval (add1 (collatz-length ht (add1 (* 3 n))))))
      (hash-set! ht n colval))
  colval)

; same function with a different syntax
(define (collatz-length2 ht n)
  (cond [(hash-ref ht n #f) => (lambda (colval) colval)]
        [else
         (define colval 0)
         (if (even? n)
             (set! colval (add1 (collatz-length2 ht (/ n 2))))
             (set! colval (add1 (collatz-length2 ht (add1 (* 3 n))))))
         (hash-set! ht n colval)
         colval]))

; ProjectEuler problem #14
(define (euler14)
  (define ht (make-hash (list '(1 . 1))))
  (define start-of-longest-chain 1)
  (define longest-chain 1)
  (for ([i (in-range 2 1000000)])
    (define col-len (collatz-length2 ht i))
    (when (< longest-chain col-len)
      (set! longest-chain col-len)
      (set! start-of-longest-chain i)))
  (values start-of-longest-chain longest-chain))

*The good news*: it is simpler, more idiomatic and faster

*The bad news*: it still feels a little clunky.  It has a lot of imperative
statements and the memoization in the hash table feels too much like a
side-effect to me.

Any more help?

Thanks again!
-Joe

On Mon, Apr 2, 2012 at 12:37 AM, Neil Van Dyke <neil at neilvandyke.org> wrote:

> Joe Gilray wrote at 04/02/2012 12:44 AM:
>
>> 1) [,,,]
>>
>> > (define ggg (make-hash (list '(1 4))))
>>
>
> Instead of  '(1 4) , which is a list, you want a pair, '(1 . 4)) .
>
> If you're not yet familiar with pairs, you might want to soon take a
> detour from the numerical Project Euler problems, to play a bit with making
> your own pairs and lists.  They're still pretty fundamental.  Maybe try
> making some recursive procedures that build lists in different ways.
>  (Don't use Hashes, nor the "do" form, nor "map", nor any of the
> "for"-something forms.  Just you, recursive procedures, and "cons".)
>
>
>  2) My use of hash-has-key? feels clunky, Could I better use hash-ref?
>> especially here:
>>
>>        (if (hash-has-key? ht col)
>>            (let ([colval (hash-ref ht col)]) ...
>>
>
> Good eye.  One way to do this is to use an optional argument to
> "hash-ref", to supply a default value that would never be returned if "col"
> were in "ht", and then to test against that default value.  When possible,
> use #f for this default value, so that it works nicely as a Boolean, such
> as with "if".
>
> (let ((my-value-from-ht (hash-ref ht col #f)))
>  (if my-value-from-ht
>      [...do something with my-value-from-ht...]
>      [...do something else...]))
>
> Even better, you can do this with "cond" "=>", like so:
>
> (cond ((hash-ref ht col #f)
>       => (lambda (my-value-from-ht)
>            [...do something with my-value-from-ht...]))
>      (else [...do something else...]))
>
> This code pattern with the "=>" thing looks cryptic to someone who's never
> seen it before, but it has a couple advantages: (1)  you can't accidentally
> use "my-value-from-ht" in the ``do something else'' part; and (2) your code
> might be cleaner, if ``do something else'' part can become additional
> clauses for the "cond", rather than just the "else" clause.
>
> BTW, remember that "(lambda (my-value-from-ht) ...)" is just defining a
> procedure.  In the "cond" example above, you might be able to put a
> variable identifier for a procedure instead, so "=> (lambda ...)" would
> look something like "=> my-proc", and somewhere else there would something
> like "(define (my-proc val) ...)".  This is perhaps most useful when
> "my-proc" is more general than just that one "cond" clause.
>
> Neil V.
>
> --
> http://www.neilvandyke.org/
>
> ____________________
>  Racket Users list:
>  http://lists.racket-lang.org/**users <http://lists.racket-lang.org/users>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20120402/b79eb867/attachment-0001.html>