gistfile1.rkt

#lang racket/base
(require test-engine/racket-tests)
(require racket/list)

;; YIKES! you clearly wrote the function before the tests, because what you have below
;; is just nuts.  Specifically, you have a table that maps strings to ... tables!
;; Let's rewrite those test cases first:

(check-expect (add-stat (add-stat (hash) '("a" "b" "c")) '("a" "b" "d"))
              (hash "a" 2 "b" 2 "c" 1 "d" 1))

;; we should have a test where a number gets added more than once:
(check-expect (add-stat (add-stat (hash) '("a" "b" "a" "c")) '("a" "b" "d"))
              (hash "a" 3 "b" 2 "c" 1 "d" 1))

;; that is, each number is mapped to its number of occurrences, right?

;; Now, the problem in the code below is that you're not using the hash table
;; that results from the recursive call in the right way. Also, there's no need
;; to use the template for non-empty lists! To see this, here's a simple test case:

(check-expect (add-stat (hash) '()) (hash))

;; this one also currently fails on your code.  

;; also, there's a neat trick you can use to avoid your "is it already there"
;; check, below. Specifically, hash-ref takes another, optional argument to specify
;; a value to return if the key is not found. In your case, you want to return 0,
;; so that a key that's not found behaves as though it's there, with a zero.

;; Okay, next up you have a fundamental decision to make: write this in accumulator
;; style or not. Probably the easiest way to describe this is to show you both of
;; them, and let you decide which one you like better. Accumulator-style is a better
;; fit for languages like C or Python that favor loops over recursion. For more
;; discussion of this, you can see section 6 of HtDP 2e:
;; http://www.ccs.neu.edu/home/matthias/HtDP2e/part_six.html

;; this version uses regular recursion:

;; Takes a hash table and a sequence of items and increments the
;; entry in the hash table associated with that sequence
;; hash list-of-anythings -> hash
(define (add-stat hashT sequence)
  (cond 
    ;; use a simple null case, per discussion above:
    [(null? sequence) hashT]
    [else 
     ;; without this define, you get code that either runs exponentially slowly
     ;; or has a bug, shown by the second test case above:
     (define rest-done (add-stat hashT (cdr sequence)))
     (hash-set rest-done (car sequence) 
                    (add1 (hash-ref rest-done (car sequence) 0)))]))

;; this version is entirely independent, and uses accumulator style:

;; Takes a hash table and a sequence of items and increments the
;; entry in the hash table associated with that sequence
;; hash list-of-anythings -> hash
(define (add-stat/accum hashT sequence)
  (cond 
    ;; use a simple null case, per discussion above:
    [(null? sequence) hashT]
    [else (add-stat/accum 
           (hash-set hashT (car sequence) (add1 (hash-ref hashT (car sequence) 0)))
           (cdr sequence))]))

;; let's copy those test cases again, for the accumulator-style one:

(check-expect (add-stat/accum (add-stat/accum (hash) '("a" "b" "c")) '("a" "b" "d"))
              (hash "a" 2 "b" 2 "c" 1 "d" 1))

(check-expect (add-stat/accum (add-stat/accum (hash) '("a" "b" "a" "c")) '("a" "b" "d"))
              (hash "a" 3 "b" 2 "c" 1 "d" 1))





;;add-all calls add-stat a bunch of times to add every sequence of sequence (of length degree) to the pass hash table
;; hash list-of-anything number -> hash
(define (add-all hashT sequence degree)
  (cond [(<= degree (length sequence))
         (add-all (add-stat hashT (take sequence degree)) (cdr sequence) degree)]
        [else
         hashT]))

;;given a hash table and a list of anythings, predicts the next thing according to statistics noted in hashT
;; hash list-of-anything -> anything
;(define (predict-next hashT prev)

;; next, you wanted a function that chose the next one according to the distribution
;; implied by the counts in the hash table. To do this, you probably don't really
;; want them in a hash table; you want them in a list; it's easier to get a guaranteed
;; order of keys.

;; given a hash table mapping keys to nats and a random number between 0 and 1, 
;; produce one of the keys based on the distribution implied by the values in the
;; hash table.
;; (hashof any nat) real -> any
(define (pick-one table rand)
  (pick-one/list (hash-map table list) (* (sum-of-values table) rand)))

(check-expect (pick-one (hash "a" 5 "b" 2 "c" 3) 0.68) "b")
(check-expect (pick-one (hash "a" 5 "b" 2 "c" 3) 0.71) "c")

;; given a list mapping keys to numbers and a real number between
;; 0 adn the sum of all the keys, return the appropriate key
;; (listof (list/c any nat)) nat real -> any
(define (pick-one/list assoc r)
  (cond [(empty? assoc)
         (raise-argument-error 'pick-one/list
                               "number <= the sum of the keys in the table"
                               1 assoc r)]
        [else
         (define weight-of-first (second (first assoc)))
         (cond [(<= r weight-of-first)
                (first (first assoc))]
               [else
                (pick-one/list (rest assoc) (- r weight-of-first))])]))

;; sum the values in the table
(define (sum-of-values ht)
  (for/sum ([v (in-hash-values ht)]) v))

(test)