; Classic reduce function:
; applies a two-parameter function to a list of values, propagating the result forward.
(define reduce
  (lambda (fn init vals)
    (if (empty? vals) init
        (reduce fn (fn init (car vals)) (cdr vals)))))
 
; Returns a list of entries that do NOT match an assoc query.
(define not-assoc
  (lambda (val entries)
    (filter (lambda (x) (not (eq? val (car x)))) entries)))

; Returns the result of an assoc query, returning "default" if the query fails.
(define assoc-default
  (lambda (val default entries)
    (let ((found (assoc val entries)))
      (if (eq? #f found) default found))))

; Adds a word to a trie.
; Recursively consumes the next item from new-entry, exploring existing subtries
; and creating new ones if necessary.
(define add-trie (lambda
    (new-entry trie)
    (if (empty? new-entry) (list (car trie) (list))
        (list (car trie) ; trie node
              (list* (add-trie (cdr new-entry) ; all affected
                                      (assoc-default (car new-entry) (list (car new-entry) (list)) (cadr trie)))
                     (not-assoc (car new-entry) (cadr trie))))))) ; all children not on the path

; Given a list of strings, returns a search trie.
(define populate-trie (lambda
    (strings)
    (reduce (lambda (trie entry) (add-trie entry trie))
            '(root ())
            (map (lambda (x) (string->list x)) strings))))

(define query-trie (lambda
    (val trie)
    (query-trie-internal (string->list val) trie)))

(define query-trie-internal (lambda
    (val trie)
    (if (empty? val)
        #t ; string completely consumed - it matches
        (let ((search-result (assoc (car val) (cadr trie))))
          (if (eq? #f search-result)
              #f
              (query-trie-internal (cdr val) search-result))))))
                     

(define test-trie (populate-trie (list "apple" "maggot" "quarantine" "area" "do" "not" "transport" "home" "grown" "fruit")))
; should be true
(query-trie "apple" test-trie)
(query-trie "area" test-trie)
(query-trie "quarantine" test-trie)
; should be false
(query-trie "yoho" test-trie)
(query-trie "apples" test-trie)
(query-trie "aren't" test-trie)