[racket] on contract violation after adding 1471 strings to a BST

What happens in create-bst-word, when the word to inserted is the same
as (node-word bst) ?

/Jens Axel


2014-08-05 21:56 GMT+02:00 Daniel Bastos <dbastos at toledo.com>:
> After studying chapter 14 of HtDP, I decided to try putting strings into a
> BST. The code below works with a few strings. I have a file with 22064
> strings --- one per line. Up until 1471 words, it works. With 1472 it yields
> a contract violation.
>
>> (length (read-words))
> 22064
>
>> (create-bst-word-from-list (take (read-words) 1471))
> #<node>
>
>> (create-bst-word-from-list (take (read-words) 1472))
> node-word: contract violation
>   expected: node?
>   given: #<void>
>   context...:
>    /home/dbastos/public_html/rkt/functions.rkt:974:0: create-bst-word
>    /home/dbastos/public_html/rkt/functions.rkt:987:0:
> create-bst-word-from-list
>    /home/dbastos/public_html/rkt/functions.rkt:987:0:
> create-bst-word-from-list
>    /home/dbastos/public_html/rkt/functions.rkt:987:0:
> create-bst-word-from-list
>    /home/dbastos/public_html/rkt/functions.rkt:987:0:
> create-bst-word-from-list
>    /home/dbastos/public_html/rkt/functions.rkt:987:0:
> create-bst-word-from-list
>    /home/dbastos/public_html/rkt/functions.rkt:987:0:
> create-bst-word-from-list
>    /home/dbastos/public_html/rkt/functions.rkt:987:0:
> create-bst-word-from-list
>    /home/dbastos/public_html/rkt/functions.rkt:987:0:
> create-bst-word-from-list
>    /home/dbastos/public_html/rkt/functions.rkt:987:0:
> create-bst-word-from-list
>    /home/dbastos/public_html/rkt/functions.rkt:987:0:
> create-bst-word-from-list
>    /home/dbastos/public_html/rkt/functions.rkt:987:0:
> create-bst-word-from-list
>    /home/dbastos/public_html/rkt/functions.rkt:987:0:
> create-bst-word-from-list
>    /home/dbastos/public_html/rkt/functions.rkt:987:0:
> create-bst-word-from-list
>    /home/dbastos/public_html/rkt/functions.rkt:987:0:
> create-bst-word-from-list...
>
>>
>
> It seems node-word says I gave it a #<void>. Perhaps my list of words
> contains a #<void>, but when I search for it, I do not find it.
>
>> (define ls (read-words))
>> (length ls)
> 22064
>> (length (filter string? ls))
> 22064
>> (filter void? ls)
> ()
>
> So I'm perplexed.
>
> (define-struct node (word left right))
>
> (define (create-bst-word bst str)
>   (cond
>    ((false? bst)
>     (make-node str false false))
>    ((string<? str (node-word bst)) ;; insert at the left
>     (make-node (node-word bst)
>                (create-bst-word (node-left bst) str)
>                (node-right bst)))
>    ((string>? str (node-word bst)) ;; insert at the right
>     (make-node (node-word bst)
>                (node-left bst)
>                (create-bst-word (node-right bst) str)))))
>
> (define (create-bst-word-from-list ls)
>   (cond
>    ((empty? ls) false)
>    (else
>      (create-bst-word (create-bst-word-from-list (rest ls)) (first ls)))))
>
> (define (read-lines in)
>   (let* ((ln (read-line in)))
>     (cond
>      ((eof-object? ln) empty)
>      (else (cons ln (read-lines in))))))
>
> (define (read-words)
>   (call-with-input-file "words" read-lines))
>
> Thank you in advance for any information.
>
> ____________________
>   Racket Users list:
>   http://lists.racket-lang.org/users
>



-- 
--
Jens Axel Søgaard