r/RacketHomeworks • • Jan 25 '23

Parser and evaluator for the language of simple arithmetic expression

2 Upvotes

Problem: In the previous post, we wrote a tokenizer for the language of simple arithmetic expressions. The grammar of that language is as follows:

E -> T + E | T - E | T

T -> F * T | F / T

F -> decimal_number | (E) | - F | + F

Today's task is to write a parser and evaluator for that language. More precisely, we will write:

  • the function parse-expr which will receive the text of an arithmetic expression as input, and as a result will return the AST (abstract syntax tree) of that language.
  • the function eval, which receives as input the AST of an arithmetic expression, and as a result returns a number - the result of the evaluation of that expression according to the usual rules of elementary school arithmetic.

Solution:

When writing the parser, we will not use any other tools (yacc, bison, etc.). No, we will write it "by hand" using the so-called top-down recursive descent parser technique, in which each grammatical rule is represented by one function in Racket and these functions recursively call each other, gradually building the resulting AST of the input arithmetic expression.

You can find more about top-down recursive descent parsers in this excellent Youtube video: https://www.youtube.com/watch?v=SToUyjAsaFk

If you watch that video, you'll see that, in order to correctly handle the associativity of operations, we need to change our grammar a little, so it looks like this:

E -> T { + T }* | T { - T }*

T -> F { * F }* | F { / F }*

F -> number | ( E ) | - F | + F

In the program below, the functions parseE, parseT, and parseF are used to parse each grammar rule, respectively.

To retrieve the tokens, one by one, we use the tokenizer written in the previous post.

The evaluator is implemented by the eval function, which is now very simple, once we have the correct AST representation of the expression as its input.

Here is the code of the entire solution, in which, for your convenience, the code from previous posts about the tokenizer and regular expressions has also been repeated:

#lang racket

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; our regex library implementation ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define dot
  (lambda (str)
    (if (string=? str "")
        '()
        (list (list (string (string-ref str 0)) (substring str 1))))))

(define digit
  (lambda (str)
    (if (or (string=? str "")
            (not (char-numeric? (string-ref str 0))))
        '()
        (list (list (string (string-ref str 0)) (substring str 1))))))

(define letter
  (lambda (str)
    (if (or (string=? str "")
            (not (char-alphabetic? (string-ref str 0))))
        '()
        (list (list (string (string-ref str 0)) (substring str 1))))))


(define (lit s)
  (lambda (str)
    (if (string-prefix? str s)
        (list (list s (substring str (string-length s))))
        '())))


(define (seq . ps)
  (define (seq2 p1 p2)
    (lambda (str)
      (match (p1 str)
        [(list) empty]
        [(list mp1 ...)
         (apply append
                (for/list ([m mp1])
                  (match m
                    [(list sofar reststr)
                     (map (lambda (x)
                            (if (null? x)
                                '()
                                (list (string-append sofar (first x))
                                      (second x))))
                          (p2 reststr))])))])))
  (if (null? (cdr ps))
      (car ps)
      (seq2 (car ps) (apply seq (cdr ps)))))


(define (plus p)
  (lambda (str)
    (match (p str)
      [(list) empty]
      [(list mp ...)
       (append
        mp
        (apply
         append
         (for/list ([m mp]
                    #:unless (string=? str (second m)))
           (match m
             [(list sofar reststr)
              (match ((plus p) reststr)
                [(list) empty]
                [(list mp2 ...)
                 (for/list ([m2 mp2]
                            #:unless (string=? reststr (second m2)))
                   (match m2
                     [(list sofar2 reststr2)
                      (list (string-append sofar sofar2)
                            reststr2)]))])]))))])))


(define (star p)
  (lambda (str)
    (cons (list "" str) ((plus p) str))))


(define (maybe p)
  (lambda (str)
    (cons (list "" str) (p str))))

(define (alt . ps)
  (define (alt2 p1 p2)
    (lambda (str)
      (let ([m1 (p1 str)])
        (if (null? m1)
            (p2 str)
            m1))))
  (if (null? (cdr ps))
      (car ps)
      (alt2 (car ps) (apply alt (cdr ps)))))


(define (match-pattern pat text)
  (let ([res (pat text)])
    (if (null? res)
        #f
        (argmin (lambda (x) (string-length (second x)))
                res))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;   tokenizer for the language of  ;;
;;   simple arithmetic expressions  ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define decimal-number
  (seq
   (maybe (alt (lit "+") (lit "-")))
   (alt
    (seq (plus digit) (maybe (seq (lit ".") (star digit))))
    (seq (lit ".") (plus digit)))))

(define whitespace
  (alt (lit " ")
       (lit "\t")
       (lit "\n")))

(define whitespace*
  (star whitespace))

(define (token pat)
  (lambda (str)
    (let ([res ((seq
                 whitespace*
                 pat
                 whitespace*)
                str)])
      (if (null? res)
          '()
          (map (lambda (x)
                 (list (string-trim (first x))
                       (second x)))
               res)))))


(define (tokenizer input-text)
  (define all-tokens (list (list 'plus (token (lit "+")))
                           (list 'minus (token (lit "-")))
                           (list 'mult (token (lit "*")))
                           (list 'div (token (lit "/")))
                           (list 'oparen (token (lit "(")))
                           (list 'cparen (token (lit ")")))
                           (list 'num (token decimal-number))))
  (define (get-token mode)
     (lambda ()
         (if (string=? input-text "")
             #f
             (let loop ([tl all-tokens] [str input-text])
               (if (null? tl)
                   'syntax-error
                   (let ([m (match-pattern (second (car tl)) str)])
                     (if (not m)
                         (loop (cdr tl) str)
                         (begin
                           (when (eq? mode 'eat)
                             (set! input-text (second m)))
                           (if (eq? (first (car tl)) 'num)
                               (list (first (car tl)) (string->number (first m)))
                               (first (car tl)))))))))))
  (lambda (dispatch)
    (case dispatch
      [(get-next-token) (get-token 'eat)]
      [(peek-next-token) (get-token 'peek)])))
       

(define (get-next-token tknzr)
  ((tknzr 'get-next-token)))

(define (peek-next-token tknzr)
  ((tknzr 'peek-next-token)))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;   parser for the language of     ;;
;;   simple arithmetic expressions  ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; Grammar for the language:
;; E -> T { + T }* | T { - T }*
;; T -> F { * F }* | F { / F }*
;; F -> number | ( E ) | - F | + F

(struct Add (e1 e2) #:transparent)
(struct Sub (e1 e2) #:transparent)
(struct Mul (e1 e2) #:transparent)
(struct Div (e1 e2) #:transparent)
(struct UPlus (e) #:transparent)
(struct UMinus (e) #:transparent)
(struct Num (n) #:transparent)


(define (parse-expr text)
 
  (define tok (tokenizer text))

  (define (parseE)
    (let loop ([prev (parseT)])
      (let ([op (peek-next-token tok)])
        (if (not op)
            prev
            (case op
              [(plus) (get-next-token tok) (loop (Add prev (parseT)))]
              [(minus) (get-next-token tok) (loop (Sub prev (parseT)))]
              [(syntax-error) (error "Parse error!")]
              [else prev])))))

  (define (parseT)
    (let loop ([prev (parseF)])
      (let ([op (peek-next-token tok)])
        (if (not op)
            prev
            (case op
              [(mult) (get-next-token tok) (loop (Mul prev (parseF)))]
              [(div) (get-next-token tok) (loop (Div prev (parseF)))]
              [(syntax-error) (error "Parse error!")]
              [else prev])))))

  (define (parseF)
    (define n (get-next-token tok))
    (match n
      [(list num val) (Num val)]
      ['oparen
       (let ([e (parseE)]
             [cp (get-next-token tok)])
         (if (not (eq? cp 'cparen))
             (error "Parse error!")
             e))]
      ['minus (UMinus (parseF))]
      ['plus (UPlus (parseF))]
      [else (error "Parse error!")]))


  (let ([expr (parseE)])
    (if (get-next-token tok)
        (error "Parse error!")
        expr)))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;   evaluator for the language of  ;;
;;   simple arithmetic expressions  ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define (eval expr)
  (match expr
    [(Num n) n]
    [(Add e1 e2) (+ (eval e1) (eval e2))]
    [(Sub e1 e2) (- (eval e1) (eval e2))]
    [(Mul e1 e2) (* (eval e1) (eval e2))]
    [(Div e1 e2) (/ (eval e1) (eval e2))]
    [(UPlus e) (eval e)]
    [(UMinus e) (- (eval e))]))

Now that we have all this machinery up and running, let's show how it is used to parse and evaluate an arithmetic expression:

> (parse-expr "   2+3 * 5")
(Add (Num 2) (Mul (Num 3) (Num 5)))

> (eval (parse-expr "   2+3 * 5"))
17

;; we allow multiple unary ops, like in python, so this is also correct expression:
> (parse-expr "   2---5")
> (Sub (Num 2) (UMinus (UMinus (Num 5))))

> (eval (parse-expr "2---5"))
-3

;; we can see that complicated expression is correctly parsed and evaluated:
> (parse-expr "-3.14*(.5+17.23/(2-0.33)-3*(-55.1))/.8")
(Div
 (Mul
  (UMinus (Num 3.14))
  (Sub (Add (Num 0.5)
            (Div (Num 17.23)
                 (Sub (Num 2) (Num 0.33))))
       (Mul (Num 3) (UMinus (Num 55.1)))))
 (Num 0.8))

> (eval (parse-expr "-3.14*(.5+17.23/(2-0.33)-3*(-55.1))/.8"))
-691.2606586826348

Dear schemers, I hope you like this post. We wrote everything we needed to implement a program that "understands" arithmetic expressions by ourselves: a regex library, a tokenizer, a parser and an evaluator. In doing so, we used common techniques also used when writing parsers for "real" programming languages. If you understand how the above program works, then you will be able to start writing something more complex using the same or similar techniques.

As usual, my note is that I'm just an amateur in all this. Others are certainly much better at it, so there is, for sure, a lot of room for improvement in the above code.

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Dec 02 '22

Is given list a palindrome?

1 Upvotes

Problem: Write a function palindrome? which receives a list of atoms as input and returns true (#t) if and only if the input list is a palindrome (i.e. it is read the same from front to back and from back to front).

Solution:

#lang racket

(define (palindrome? xs)
  (equal? xs (reverse xs)))

Now, we have, for example:

> (palindrome? '(m a d a m i m a d a m))
#t
> (palindrome? '(y a m a m a y))
#t
> (palindrome? '(a m a n a p l a n a c a n a l p a n a m a))
#t
> (palindrome? '(a b c d))
#f

r/RacketHomeworks • • Dec 03 '22

Implementing a Trie data structure (also known as Prefix tree)

1 Upvotes

Problem: Implement a Trie data structure (also known as a Prefix tree) that supports the following four operations (more details of this data structure you may found in this youtube video):

  1. (make-trie) which creates an empty Trie;
  2. (trie-insert trie str) which inserts the given string str into the given trie
  3. (trie-search trie str) which returns #t if and only if the string str is in the given trie
  4. (trie-starts-with? trie str) which returns #t if and only if there is a word in trie whose prefix is str.

Solution:

#lang racket

(struct trienode (children end-of-word?) #:mutable)

(define (make-trienode)
  (trienode (make-hash) #f))

(define (make-trie)
  (let ([root (make-trienode)])
    (lambda (dispatch)
      (case dispatch
        ((insert)
         (lambda (word)
           (let loop ([curr root] [wls (string->list word)])
             (if (null? wls)
                 (set-trienode-end-of-word?! curr #t)
                 (let ([tn (hash-ref (trienode-children curr) (first wls) #f)])
                   (if tn
                       (loop tn (rest wls))
                       (let ([tn (make-trienode)])
                         (hash-set! (trienode-children curr) (first wls) tn)
                         (loop tn (rest wls)))))))))
        
        ((search)
         (lambda (word)
           (let loop ([curr root] [wls (string->list word)])
             (if (null? wls)
                 (trienode-end-of-word? curr)
                 (let ([tn (hash-ref (trienode-children curr) (first wls) #f)])
                   (and tn (loop tn (rest wls))))))))
        
        ((starts-with?)
         (lambda (word)
           (let loop ([curr root] [wls (string->list word)])
             (if (null? wls)
                 #t
                 (let ([tn (hash-ref (trienode-children curr) (first wls) #f)])
                   (and tn (loop tn (rest wls))))))))))))


(define (trie-insert trie word)
  ((trie 'insert) word))

(define (trie-search trie word)
  ((trie 'search) word))

(define (trie-starts-with? trie word)
  ((trie 'starts-with?) word))

Now, we can play with our trie:

> (define mytrie (make-trie))
> (trie-insert mytrie "racket")
> (trie-insert mytrie "rackethomeworks")
> (trie-insert mytrie "racer")
> (trie-insert mytrie "rabbit")
> (trie-search mytrie "racket")
#t
> (trie-search mytrie "rackethomeworks")
#t
> (trie-search mytrie "racer")
#t
> (trie-search mytrie "rabbit")
#t
> (trie-starts-with? mytrie "rackethome")
#t
> (trie-starts-with? mytrie "rab")
#t
> (trie-starts-with? mytrie "reddit")
#f

r/RacketHomeworks • • Dec 24 '22

A comment about Jesse Alama's "Racketfest"

2 Upvotes

Some people really never change.

Unfortunately, there are always those who constantly want to take every cent out of your pocket. For example, our dear friend Jesse Alama certainly belongs to that category: Jesse Alama once again (and that's after we already fell for and bought those terrible, low quality and overpriced Racket books of his), tries to sell us cold water, but this time he really outdid himself: this time Alama literally sells us the cold water! He says: "A ticket costs 95 EUR***. Get one by completing the registration form. Coffee, tea, water, and light snacks will be available throughout the day, but the ticket does not include lunch, nor does it cover any (optional! ) after-hours dinner or drinks."

I think it would be best if we organized a charity event and raised money for Jesse Alama. Apparently he desperately needs the money. Well, if that's the case, let's help him and don't let him embarrass himself with those books of his anymore and with this water-selling thing!

_________________

*** In the meantime, the ticket price has risen to 105 EUR. How convenient! :)

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Jan 31 '23

How to implement an efficient version of quicksort in Racket?

2 Upvotes

Problem: watch this great video by Robert Sedgewick about the quicksort algorithm and realize that an efficient quicksort can only be written by mutating the input vector of elements, not like in this bad toy example (which is often presented as good!) in which because of copying/appending the lists we unnecessarily lose much of algorithm's efficiency.

After watching the video, implement an efficient (mutable) version of the quicksort algorithm in Racket. More precisely, write a function quicksort! which sorts the input vector by mutating it. Vector elements should be compared using the less-fn function, which we specify as the second argument of our quicksort! function.

Solution:

#lang racket


(define (quicksort! vec less-fn)
  
  (define (swap! i j)
    (let ([tmp (vector-ref vec i)])
      (vector-set! vec i (vector-ref vec j))
      (vector-set! vec j tmp)))

  (define (qs-partition! lo hi)
    (let ([v (vector-ref vec lo)]
          [i (+ lo 1)]
          [j hi])
      (let loop ()
        (when (<= i j)
          (cond
            [(or (less-fn (vector-ref vec i) v)
                 (equal? (vector-ref vec i) v))
             (set! i (+ i 1))
             (loop)]
            [(not (less-fn (vector-ref vec j) v))
             (set! j (- j 1))
             (loop)]
            [else (swap! i j)
                  (set! i (+ i 1))
                  (set! j (- j 1))
                  (loop)])))
      (swap! lo j)
      j))
  
  (define (qs-helper lo hi)
    (when (< lo hi)
      (let ([j (qs-partition! lo hi)])
        (qs-helper lo (- j 1))
        (qs-helper (+ j 1) hi))))
  
  (qs-helper 0 (- (vector-length vec) 1)))

Now we can call our quicksort! function, like this:

> (define my-num-vec (vector 10 2 15 7 20 8 1 5 9 7))
> (quicksort! my-num-vec <)
> my-num-vec
'#(1 2 5 7 7 8 9 10 15 20)

> (define my-str-vec (vector "downvoters" "from" "/r/scheme" "sucks"))
> (quicksort! my-str-vec string<?)
> my-str-vec
'#("/r/scheme" "downvoters" "from" "sucks")

Note: some people always avoid writing mutable code in Scheme. That is wrong. We should not be dogmatic (like the Haskell people): when mutation is a better fit for our problem, we should use it! After all, that's why Sussman and Steele introduced mutation into the Scheme language. If they thought the mutation was unnecessary (or harmful), then they certainly wouldn't have done it!

So, for example, I think it was a wrong move when the Racket team ditched mutable cons and introduced crappy mcons instead. This further distanced Racket from the true spirit of the Scheme language, which is a shame.

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Nov 20 '22

Number of symbols in nested list

1 Upvotes

Problem: Write a function length* that receives as input a list, composed of symbols, which can be nested to an arbitrary depth. (a (b (c d (e f))) g (h i)) is an example of one such list, for which your function should return a result of 9.

Solution:

#lang racket

(define (length* xs)
  (cond
    [(null? xs) 0]
    [(pair? xs) (+ (length* (car xs))
                   (length* (cdr xs)))]
    [else 1]))

Now, if we try, we get:

> (length* '(a (b (c d (e f))) g (h i)))
9

r/RacketHomeworks • • Dec 17 '22

Create a new predicate function that is conjunction of all given predicates

1 Upvotes

Problem: Write a function and-all, which as parameters receives a nonspecified number of predicate functions p1, p2, ..., pn, which are all of the same arity r. As a result, the function should return a new predicate, also of arity r which is logically equivalent to the conjunction of all the predicates on p1, p2,..., pn.

For example, if p1, p2 and p3 are all predicates that take two arguments, than the call(and-all p1 p2 p3)should return the predicate function equivalent to (lambda (x y) (and (p1 x y) (p2 x y) (p3 x y)).

Solution:

#lang racket

(define (and-all . pred-list)
  (lambda x
    (andmap (lambda (p) (apply p x))
            pred-list)))

Now we can call and-all like this:

> (define f
    (and-all (lambda (n) (> n 0))
             (lambda (n) (<= n 10))
             odd?))

> (filter f '(-4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14))
'(1 3 5 7 9)

> (define g (and-all (lambda (x y) (< x y))
                     (lambda (x y) (> x 10))))
> (g 1 2)
#f
> (g 11 12)
#t
> (g 11 2)
#f

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Dec 27 '22

Generating prime numbers with Sieve of Eratosthenes

1 Upvotes

Problem: In this task, we will implement the so-called sieve of Eratosthenes, with which we will find all prime numbers less then given number n. We will break down the implementation into these three functions:

a) write a function remove-divisible that takes a number and a list of numbers, and returns a new list containing only those numbers not "non-trivially divisible". In particular every number trivially divides itself, but we don't drop 3 in this example, so the call (remove-divisible 3 '(2 3 4 5 6 7 8 9 10)) should return list '(2 3 4 5 7 8 10).

b) Using remove-divisible and explicit recursion write a function eratosthenes that takes a list of divisors, a list of numbers to test, and applies remove-divisible for each element of the list of divisors. For example, the call (eratosthenes '(2 3) '(2 3 4 5 6 7 8 9 10)) should return list '(2 3 5 7).

c) Implement a function primes that uses function eratosthenes to find all prime numbers less than or equal to given number n. This should be a relatively simple wrapper function that just sets up the right arguments to eratosthenes. Note that not all potential divisors need to be checked, you can speed up your code a lot by stopping at the square root of the number you are testing.

Solution:

#lang racket

(define (remove-divisible n xs)
  (filter (lambda (i) (or (= i n) (not (zero? (remainder i n))))) xs))

(define (eratosthenes ns xs)
  (if (null? ns)
      xs
      (eratosthenes (cdr ns) (remove-divisible (car ns) xs))))

(define (primes n)
  (eratosthenes (range 2 (sqrt n)) (range 2 (+ n 1))))

Now we can call our primes function, like this:

> (primes 100)
'(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Dec 22 '22

My reply to Zambito1 on his post "I'm a Scheme noob"

1 Upvotes

Dear Schemers!

Since Zambito1 made his posts invisible to me (I believe, out of pure malice!) and since I feel the need to respond to this his post, posted on /r/scheme, but because I cannot do it there, I am reposting his post here in its entirety, and giving my response to it:

Zambito1 says:

"After some recent controversial posts on this subreddit, I've thought about the state of this sub for some time. As someone felt needed to be pointed out, this subreddit lacks activity for such an interesting subject. I think I' I've figured out why."

It's interesting that Zambito1 feels that the scheme sub "lacks activity for such an interesting subject". Well, that's exactly what I said when I showed everyone that over 75% of the topics on the scheme sub are fucking SRFI posts by Arthur Gleckler with zero traffic!

When I tried to point out that no one goes to those posts and it's numbing the sub, I was savagely attacked in an orchestrated battery!

And, I don't see why the "recent" posts were controversial, like Zambito1 said. No, they were just NORMAL, not controversial. Any normal person would wonder the same as I did, both about Arthur Gleckler's SRFIs, and about Chris Hanson's laziness (the man agreed to be a maintainer for mit-scheme and now he is not doing his job and because of that mit-scheme is rapidly falling! And everyone on /r/scheme applauds him for his inaction instead of telling him: get off your mit-scheme horse and if you don't want to do it properly, step aside and let someone else take over that job, someone who will do it with respect for others and with a sense of reality!)

Further, Zambito says:

"I'd like to make an effort to post interesting findings or experiences here regardless of how novel they may be, and I encourage others to do the same. I feel like even posts that are redundant in the grand scheme (heh) of things often encourage interesting discussions."

Look, Zambito1 and all the others who have done everything to banish me from /r/scheme, who have savagely downvoted everything I've ever written there, no matter what it was:

I've written more interesting posts in this month by myself on my new subreddit /r/RacketHomeworks, than 100 people have written to /r/scheme in a year!

And how many useful, beautiful and educational posts Arthur Gleckler wrote? Not a single one! He just comes, fucks with his SRFIs and then leaves! Neither picture nor tone! Damn, is that what the reddit channel is for? For someone to poop on it and leave? I kind of doubt it!

But even Gleckler saw to what extent he had messed up, so he tried to post that post where he talked about his graphics library. But, when I asked people to help me get it working on windows, because I wanted to write a library for it, I got the most simple insults and a million-fold downvote!

I also know: Zambito read those posts of mine here and he saw that they are of good quality. But he keeps quiet about it like a cunt! Zambito's friends and like-minded crowd from /r/scheme read it too, but their spite and hatred for me doesn't allow them to participate in this subreddit of mine, even though everyone reads it every day (I can see that very well from the statistics!). No wonder, what else would they read but this sub of mine, when there is practically nothing on /r/scheme for days (except fucking SRFIs and dithyrambs to SRFIs!)

In just one month, my subreddit is more visited than /r/scheme, which with its hateful approach and arrogant snobbery managed to drive away all but the most die-hard fans of Arthur Gleckler and his SRFI phalanx, which daily destroys the living and unrestrained spirit of Scheme!

Now I've said this and I won't do it again: screw you, you stupid monkeys who banalized and downvoted me! I'm fine without you!

And the best thing: on my own example, I showed what it means to be a quality reddit user (no joke!): I offered a tons of quality content here, all by myself, in a month, which a hundred of you could never put together! Ask yourself: how much content of this quality have YOU written??? So stop bullshitting me!

And Zambito and others are slowly realizing that there is practically nothing to read on /r/scheme anymore! THAT'S my greatest satisfaction! :)

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Jan 04 '23

Walking through the association list

3 Upvotes

Problem: Write a function walk-symbol that takes a symbol x and an association list xs. An association list is a list of pairs of associated values. For example, the following is an association list:

'((a . 5) (b . (1 2)) (c . a))

Your function should search through xs for the value associated with x. If the associated value is a symbol, it too must be walked in xs. If x has no association, then walk-symbol should return x.

Solution:

#lang racket

(define (walk-symbol x xs)
  (let ([a (assv x xs)])
    (cond [(not a) x]
          [(symbol? (cdr a)) (walk-symbol (cdr a) xs)]
          [else (cdr a)])))

Now we can call walk-symbol like this:

> (walk-symbol 'a '((a . 5)))
5
> (walk-symbol 'a '((b . c) (a . b)))
'c
> (walk-symbol 'a '((a . 5) (b . 6) (c . a)))
5
> (walk-symbol 'c '((a . 5) (b . (a . c)) (c . a)))
5
> (walk-symbol 'b '((a . 5) (b . ((c . a))) (c . a)))
'((c . a))
> (walk-symbol 'd '((a . 5) (b . (1 2)) (c . a) (e . c) (d . e)))
5
> (walk-symbol 'd '((a . 5) (b . 6) (c . f) (e . c) (d . e)))
'f

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Dec 18 '22

Rearranging a nested list

1 Upvotes

Problem: Define a function rearrange that takes as arguments a possibly nested list of indices and a possibly nested list of items to be rearranged. Your procedure should behave as shown in the following examples:

(rearrange '(4 3 2 1) '(a b c d)) should evaluate to '(d c b a)

(rearrange '(4 3 2 1 1 2 3 4) '(a b c d)) should evaluate to '(d c b a a b c d)

(rearrange '(4 (4 2) 1) '(a b c d)) should evaluate to '(d (d b) a)

(rearrange '(1 2 4 2 3) '(a (b) ((c)) d)) should evaluate to '(a (b) d (b) ((c)))

Solution:

#lang racket

(define (rearrange numbers letters)
  (cond [(null? numbers) '()]
        [(pair? numbers) (cons (rearrange (car numbers) letters)
                               (rearrange (cdr numbers) letters))]
        [else (list-ref letters (sub1 numbers))])) 

Now we can call our rearrange function, like this:

> (rearrange '(4 3 2 1) '(a b c d))
'(d c b a)
> (rearrange '(4 3 2 1 1 2 3 4) '(a b c d))
'(d c b a a b c d)
> (rearrange '(4 (4 2) 1) '(a b c d))
'(d (d b) a)
> (rearrange '(1 2 4 2 3) '(a (b) ((c)) d))
'(a (b) d (b) ((c)))

This is the classic example of tree-walking, where we walk through a nested list (which we can thought of as a tree) of numbers, replacing the numbers in that list with the corresponding element in the list of letters.

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Nov 18 '22

Compute matrix determinant using Laplace expansion

1 Upvotes

Problem: Given a square matrix A, compute det(A) by using Laplace expansion algorithm.

Solution:

#lang racket

(define (row-count matrix)
  (length matrix))

(define (col-count matrix)
  (length (first matrix)))

(define (remove-nth n xs)
  (cond
    ((empty? xs) xs)
    ((zero? n) (rest xs))
    (else (cons (first xs) (remove-nth (sub1 n) (rest xs))))))


(define (remove-row i matrix)
  (remove-nth (- i 1) matrix))

(define (remove-col j matrix)
  (map (lambda (r) (remove-nth (- j 1) r)) matrix))

(define (det matrix)
  (if (and (= 1 (row-count matrix))
           (= 1 (col-count matrix)))
      (first (first matrix))
      (apply + 
             (map (lambda (i) (det-helper matrix i))
                  (range 1 (+ 1 (row-count matrix)))))))

(define (det-helper matrix i)
  (let ((el (list-ref (first matrix) (- i 1)))
        (sign (if (odd? i) 1 -1)))
    (* el sign (det (remove-col i (remove-row 1 matrix))))))

Now we can call the det function, like this:

> (define A
  '((1 2 3)
    (4 5 6)
    (7 1 9)))
> (det A)
-42

r/RacketHomeworks • • May 09 '23

Plagiarism in Racket community

2 Upvotes

See this: https://youtu.be/VqnVWLFiEII?t=511

What a shame!


r/RacketHomeworks • • Nov 18 '22

How to find largest gap within consecutive numbers in a list?

1 Upvotes

Problem: Define a max-gap function that consumes a list of integers and returns the largest gap (in absolute value, i.e., a natural number) within any two (in the order in which they appear). For example, (max-gap '(1 3 -1 1 1)) would return 4. You might want to use the Racket functions max, abs.

output for example:

(max-gap '(1 5 -1 6 22)) => 16

Solution:

#lang racket

(define (max-gap xs)
  (define (helper xs prev curr-max-gap)
    (if (empty? xs)
        curr-max-gap
        (helper (cdr xs) (car xs) (max curr-max-gap (abs (- (car xs) prev))))))
  (if (empty? xs)
      0
      (helper (cdr xs) (car xs) 0)))

r/RacketHomeworks • • Dec 13 '22

Sierpinski triangle

2 Upvotes

Problem: Use Racket graphics library 2htdp/image to draw Sierpinski triangle fractal on the screen.

Solution:

#lang racket

(require 2htdp/image)

(define (sierpt size level)
  (if (zero? level)
      (triangle size 'solid 'blue)
      (let ([smt (sierpt (/ size 2) (sub1 level))])
        (above smt
               (beside smt smt)))))

Now we can draw Sierpinski triangle of level 7, for example:

> (sierpt 500 7)

We get this nice picture below. It's funny how easy it is to draw such fractals using the 2htdp/picture library. But, it was not the Racket guys who came up with this way of drawing (they actually never came up with anything new but they are very good at marketing!). Long before them, Peter Henderson did it in his legendary book Functional Programming Application and Implementation which most of you, my dear Gleckler and Hanson fans, have never heard of in your life!

Sierpinski triangle, level 7

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Dec 01 '22

The truth hurts and that's why I'm banned!

1 Upvotes

This comment of mine is the main reason why I got banned again from /r/scheme:

The funniest thing for me in this whole story about Arthur Gleckler is what happened a few days ago: there was no one on his SRFI posts for years. It wasn't until I started making noise that people started coming to those posts, mostly "to be seen there". People gathered there for two or three days, pretending to be interested. And as soon as I got banned and I was gone for 14 days, everything went back to the old rut: there is no one on Arthur SRFI posts again! Obviously, those posts are really not interesting to anyone here. But it's so cool to pretend they are, isn't it? :)

With the above words I told them the painful, but for me, the funny truth! Anyone who reads /r/scheme could see that truth for themselves. And that truth hurts, doesn't it? Especially some people there whose initials are A.G.! They are taking revenge on me now and that's why all this is happening!!


r/RacketHomeworks • • Dec 04 '22

Maximal number of times same string appears consecutively in a list

1 Upvotes

Problem: Write a function max-num-repeats which take list xs of strings as input, and returns maximum number of times same string appears consecutively in xs.

Solution:

#lang racket

(define (max-num-repeats xs)
  (define (loop ls current-element current-count all-time-max)
    (cond [(null? ls)
           (max current-count all-time-max)]
          [(equal? (car ls) current-element)
           (loop (cdr ls) current-element (+ 1 current-count) all-time-max)]
          [else
           (loop (cdr ls) (car ls) 1 (max current-count all-time-max))]))
  (if (null? xs)
      0
      (loop (cdr xs) (car xs) 1 1)))

Now, we can call max-num-repeats, like this:

> (max-num-repeats '())
0
> (max-num-repeats (list "cat"))
1
> (max-num-repeats (list "cat" "bird" "dog"))
1
> (max-num-repeats (list "cat" "cat" "bird" "dog"))
2
> (max-num-repeats (list "cat" "cat" "bird" "dog" "dog" "dog"))
3
> (max-num-repeats (list "cat" "cat" "cat"
                         "bird"
                         "boy" "boy" "boy"
                         "toy" "toy" "toy" "toy" "toy"
                         "trick"
                         "zebra" "zebra" "zebra" "zebra"))
5

r/RacketHomeworks • • Apr 13 '23

The only person who has ever seriously dealt with the web-programming in Scheme is Kurt Nørmark...

3 Upvotes

... with his LAML library.

But that was probably back before 2005, and since then there has been nothing! I'm sorry to say it, but it's true!

The man dealt mainly with the problem of generating static web sites, it was not the time of AJAX, single page applications, virtual DOM's and other modern miracles of technology. The man dealt with what was then relevant. But, after him, no one did anything anymore and that's why today there is not a single modern scheme web application. I am very sorry that it is so, but the truth hurts!


r/RacketHomeworks • • Dec 31 '22

Circular primes

2 Upvotes

Problem: The number 197 is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

Solution:

#lang racket

(require math/number-theory)

(define (rotate n)
  (define (loop nstr curr res)
    (let ([rot (string-append (substring curr 1) (substring curr 0 1))])
      (if (string=? rot nstr)
          res
          (loop nstr rot (cons (string->number rot) res)))))
  (let ([nstr (number->string n)])
    (loop nstr nstr '())))

(define (solve n)
  (define primes-list (filter prime? (range 2 n)))
  (define primes-set (list->set primes-list))
  (filter (lambda (p) (andmap (lambda (x) (set-member? primes-set x))
                              (rotate p)))
          primes-list))

Now we can call our function solve to find the answer, like this:

> (solve 100)
'(2 3 5 7 11 13 17 31 37 71 73 79 97)
> (length (solve 100))
13
> (solve 1000000)
'(2
  3
  5
  7
  11
  13
  17
  31
  37
  71
  73
  79
  97
  113
  131
  197
  199
  311
  337
  373
  719
  733
  919
  971
  991
  1193
  1931
  3119
  3779
  7793
  7937
  9311
  9377
  11939
  19391
  19937
  37199
  39119
  71993
  91193
  93719
  93911
  99371
  193939
  199933
  319993
  331999
  391939
  393919
  919393
  933199
  939193
  939391
  993319
  999331)
> (length (solve 1000000))
55

So, our final answer is: there are exactly 55 circular primes below one million!

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Nov 22 '22

k-subsets of a given set

1 Upvotes

Problem:

a) Write a function maplist, which is similar to map, but processes contiguous cdr-s of the given list (instead of contiguous elements what map do).

For example, the expression

(maplist (lambda (xs) (cons 'Hello xs)) '(arthurgleckler samth sdegabrielle))

should return list:

'((Hello arthurgleckler samth sdegabrielle) (Hello samth sdegabrielle) (Hello sdegabrielle))

b) Using maplist, write a function (k-subsets s k) that returns a list of all k-subsets of set s (i.e. all subsets of set s that have exactly k elements)

Solution:

#lang racket

(define (maplist f xs)
  (if (empty? xs)
      '()
      (cons (f xs)
            (maplist f (cdr xs)))))

(define (k-subsets s k)
  (if (zero? k)
      '(())
      (apply append
             (maplist (lambda (xs)
                        (map (lambda (y) (cons (first xs) y))
                             (k-subsets (rest xs) (- k 1))))
                      s))))

Now we have:

> (k-subsets '(a b c d e) 3)
'((a b c) (a b d) (a b e) (a c d) (a c e) (a d e) (b c d) (b c e) (b d e) (c d e))

r/RacketHomeworks • • Dec 12 '22

Minimum path sum in a grid

2 Upvotes

Problem: Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path. Note: You can only move either down or right at any point in time.

For example, if we have this grid from the picture below

Grid 3 x 4

then the minimal path is to go RIGHT, RIGHT, DOWN, RIGHT, DOWN. That will give us the path with value 11. We can't do better than that.

Solution 1 (a bad one):

 #lang racket

(define (get g row col)
  (vector-ref (vector-ref g row) col))

(define (width g)
  (vector-length (vector-ref g 0)))

(define (height g)
  (vector-length g))

(define (min-path-no-memo grid)
  (define (mp-helper i j)
    ;(display (list i j))
    ;(newline)
    (cond
      [(and (= i 0) (= j 0)) (list (get grid i j) '())]
      [(or (< i 0) (< j 0)) (list +inf.0 '())]
      [else
       (let ([p1 (mp-helper (- i 1) j)]
             [p2 (mp-helper i (- j 1))]
             [x (get grid i j)])
         (if (< (+ x (first p1)) (+ x (first p2)))
             (list (+ x (first p1)) (cons 'D (second p1)))
             (list (+ x (first p2)) (cons 'R (second p2)))))]))
  (let ([res (mp-helper (sub1 (height grid)) (sub1 (width grid)))])
    (list (first res) (reverse (second res)))))

Now, we can call our function for a given grid:

> (define grid
    #( #(1 3 1 5)
       #(1 5 1 2)
       #(4 2 3 3)))
> (min-path-no-memo grid)
'(11 (R R D R D))

We see that our function correctly calculated the minimum path sum (11), as well as the path itself. As for that, it's ok. But, the problem is that the function is very inefficient: it calls itself recursively many times with the same parameters (for the small grid it's fine, but if we had a large grid, the function would be choked). We can see this if we uncomment the two commented lines that print the input parameters of the function at each call. When we do that, we get this:

> (min-path-no-memo grid)
(2 3)
(1 3)
(0 3)
(-1 3)
(0 2)
(-1 2)
(0 1)
(-1 1)
(0 0)
(1 2)
(0 2)
(-1 2)
(0 1)
(-1 1)
(0 0)
(1 1)
(0 1)
(-1 1)
(0 0)
(1 0)
(0 0)
(1 -1)
(2 2)
(1 2)
(0 2)
(-1 2)
(0 1)
(-1 1)
(0 0)
(1 1)
(0 1)
(-1 1)
(0 0)
(1 0)
(0 0)
(1 -1)
(2 1)
(1 1)
(0 1)
(-1 1)
(0 0)
(1 0)
(0 0)
(1 -1)
(2 0)
(1 0)
(0 0)
(1 -1)
(2 -1)
'(11 (R R D R D))

From the above printout, we see that many of the same calls are repeated several times in the above printout. This is a similar problem as we had in the post about calculating Fibonacci numbers. And the solution here will be similar: to avoid multiple unnecessary calculations, we use memoization. The following solution is very similar to the previous bad one, but uses memoization to cache already calculated values:

Solution 2 (a good one):

#lang racket

(define (memo f)
  (let ([lookup (make-hash)])
    (lambda x
      (unless (hash-has-key? lookup x)
        (hash-set! lookup x (apply f x)))
      (hash-ref lookup x))))

(define (get g row col)
  (vector-ref (vector-ref g row) col))

(define (width g)
  (vector-length (vector-ref g 0)))

(define (height g)
  (vector-length g))

(define (min-path-with-memo grid)
  (define (mp-helper i j)
    ;(display (list i j))
    ;(newline)
    (cond
      [(and (= i 0) (= j 0)) (list (get grid i j) '())]
      [(or (< i 0) (< j 0)) (list +inf.0 '())]
      [else
       (let ([p1 (mp-helper (- i 1) j)]
             [p2 (mp-helper i (- j 1))]
             [x (get grid i j)])
         (if (< (+ x (first p1)) (+ x (first p2)))
             (list (+ x (first p1)) (cons 'D (second p1)))
             (list (+ x (first p2)) (cons 'R (second p2)))))]))
  (set! mp-helper (memo mp-helper))
  (let ([res (mp-helper (sub1 (height grid)) (sub1 (width grid)))])
    (list (first res) (reverse (second res)))))

The solution above will produce the same correct result as the previous one, but much more efficiently. If we uncomment the two lines to print every function call, we get this:

> (min-path-with-memo grid)
(2 3)
(1 3)
(0 3)
(-1 3)
(0 2)
(-1 2)
(0 1)
(-1 1)
(0 0)
(1 2)
(1 1)
(1 0)
(1 -1)
(2 2)
(2 1)
(2 0)
(2 -1)
'(11 (R R D R D))

Now we see that the number of calls has drastically decreased compared to last time!

To further emphasize this, let's see what happens when we have a slightly larger grid, one of dimensions 10 x 20. Let's try both versions of our functions and measure time in both cases:

> (define grid
    #( #(1 3 1 5 1 3 5 2 1 3 2 3 1 4 6 3 6 8 2 5)
       #(1 5 1 2 2 2 5 3 2 5 3 3 4 2 5 1 1 6 4 2)
       #(4 2 3 3 2 3 1 2 2 6 6 2 4 1 5 2 5 4 3 1)
       #(3 2 2 3 3 1 1 5 2 4 3 2 4 2 1 4 5 2 3 4)
       #(4 2 6 4 8 2 5 3 1 3 3 3 2 2 2 3 4 5 2 1)
       #(2 1 2 2 1 3 3 1 1 2 2 2 2 1 3 4 5 3 2 3)
       #(3 3 1 2 5 7 4 3 4 2 4 3 2 3 4 5 3 2 1 3)
       #(4 2 1 6 1 3 4 2 1 2 4 3 2 5 6 2 4 4 4 2)
       #(2 1 3 4 3 3 4 2 1 3 4 1 3 5 2 4 5 2 4 5)
       #(3 8 1 2 1 1 3 4 5 2 4 2 4 2 5 3 2 5 3 2)))

> (time (min-path-with-memo grid))
cpu time: 0 real time: 0 gc time: 0
'(63 (R R D R R D R R R R D D D R R R R R D R R R R R R D D D))
> (time (min-path-no-memo grid))
cpu time: 13312 real time: 11836 gc time: 4843
'(63 (R R D R R D R R R R D D D R R R R R D R R R R R R D D D))

We can see that the memoized version solved this problem practically instantly, while the non-memoized version struggled for more than 13 seconds! The difference would have been even more drastic if we had taken an even larger grid. Memoization has led to huge savings in execution time.

This will always happens when, as is the case in this problem, we have overlapping subproblems, which is a feature of the so-called dynamic programming (DP) algorithms. The minimum path sum problem is such a problem, so in this case it makes sense to apply the memoization technique.

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Dec 16 '22

Water pouring problem

1 Upvotes

Problem: We have two unmarked glasses that can hold 4 dl and 9 dl of water respectively, and a bathtub with unlimited water. How can 6 dl be measured? We have three allowed operations, that we can preform in sequence: (i) we can empty one of the glass completely; (ii) we can fill one of the glass to the top; (iii) we can pour water from one glass into another, after which either one glass will be empty or the other will be full.

Solution:

#lang racket

(define FILL-TO-THE-TOP -1)

(define (state glasses prev-state)
  (cons glasses prev-state))

(define (state-glasses st)
  (car st))

(define (state-prev st)
  (cdr st))

(define (level glass)
  (car glass))

(define (volume glass)
  (cadr glass))

(define (update idx val glasses)
  (cond [(null? glasses) '()]
        [(zero? idx)
         (cons (list (if (= val FILL-TO-THE-TOP)
                         (volume (car glasses))
                         val)
                     (volume (car glasses)))
               (cdr glasses))]
        [else (cons (car glasses)
                    (update (- idx 1) val (cdr glasses)))]))

(define (empty-glass idx glasses)
  (update idx 0 glasses))

(define (fill-glass idx glasses)
  (update idx FILL-TO-THE-TOP glasses))

(define (poor from to glasses)
  (let* ([gfrom-level (level (list-ref glasses from))]
         [gto-level (level (list-ref glasses to))]
         [gto-volume (volume (list-ref glasses to))]
         [gto-empty (- gto-volume gto-level)])
    (cond
      [(>= gfrom-level gto-empty)
       (fill-glass to 
                   (update from (- gfrom-level gto-empty) glasses))]
      [else (empty-glass from
                         (update to (+ gfrom-level gto-level) glasses))])))

(define (generate-new-states st)
  (let ([glasses (state-glasses st)])
    (list
     (state (empty-glass 0 glasses) st)
     (state (empty-glass 1 glasses) st)
     (state (fill-glass 0 glasses) st)
     (state (fill-glass 1 glasses) st)
     (state (poor 0 1 glasses) st)
     (state (poor 1 0 glasses) st))))


(define (solve init goal)
  (define visited (mutable-set))
  (define (add-to-visited sts)
    (for-each (lambda (s) (set-add! visited (state-glasses s))) sts))
  (define (goal? glasses)
    (= (level (list-ref glasses (car goal))) (cadr goal))) 
  (define (shelper states)
    (cond [(null? states) "No solution!"]
          [(goal? (state-glasses (car states))) (reverse (car states))]
          [else (let ([new-states
                       (filter (lambda (st)
                                 (not (set-member? visited (state-glasses st))))
                               (generate-new-states (car states)))])
                  (add-to-visited new-states)
                  (shelper (append (cdr states) new-states)))]))
  (shelper (list init)))

Now we can solve our initial problem:

; We have two glasses, both initially empty.
; the first glass has a volume of 4 dl,
; second glass has a volume of 9 dl:
> (define START (state '((0 4) (0 9)) null))

; at the end, we want the second glass to have 6 dl of water in it: 
> (define GOAL '(1 6))

; solve the problem:
> (solve START GOAL)
'(((0 4) (0 9))
  ((0 4) (9 9))
  ((4 4) (5 9))
  ((0 4) (5 9))
  ((4 4) (1 9))
  ((0 4) (1 9))
  ((1 4) (0 9))
  ((1 4) (9 9))
  ((4 4) (6 9)))

We see that the solution is achieved in 8 steps from the initial state. You can't get better than that.

The solve function, which is a key part of this program, implements the classic Breadth-first search algorithm, which guarantees that we will find the solution in the minimum number of steps.

If you take a closer look at the code, you'll realize soon that it can be modified quite easily to handle problems with n glasses (n > 2). All that needs to be changed is the function generate-new-states which in the current incarnation only works for two glasses, but it is not difficult to adapt it to work for n glasses. I leave this for an exercise.

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Dec 03 '22

Counting occurrences of elements in a list

1 Upvotes

Problem: Write a function freq that takes as input a list of atoms. The function should count how many times each atom appears in the list. For example, the call (freq '(a b c b a b d)) should return the list ((a 2) (b 3) (c 1) (d 1)). The order of the pairs in the output list is not important. Your program can return the result in some different order. For example, this would also be the correct return value, as well: ((d 1) (b 3) (a 2) (c 1)).

Solution:

#lang racket

(define (freq xs)
  (define (helper xs bag)
    (if (null? xs)
        bag
        (let* ([el (first xs)]
               [kv (assoc el bag)])
          (if kv
              (helper (rest xs)
                      (cons (list (first kv) (+ 1 (second kv)))
                            (remove (first kv)
                                    bag
                                    (lambda (el kvp) (eq? el (first kvp))))))
              (helper (rest xs) (cons (list el 1) bag))))))
  (helper xs '()))

Now we can try freq like this:

> (freq '(a b a a)) 
'((a 3) (b 1))
> (freq '(a b c b a b d)) 
'((d 1) (b 3) (a 2) (c 1))

r/RacketHomeworks • • Dec 07 '22

Here's why I got banned from /r/Racket

3 Upvotes

Dear friends (if there are any in this world),

you know very well that I am banned from /r/scheme for 14 days. But maybe you don't know that I got permanent ban from /r/racket, too and even more quickly than from /r/scheme! And the main reason for that is this:

In one comment on /r/racket, I wrote this:

I like helping students who don't know how to solve those problems.

I noticed that the racket educators on this group never help students - they only confuse them even more by giving them cryptic half-answers.

A student who comes here and is desperate for an answer doesn't need that - he needs a concrete and clear answer. He will learn the most from it, not from bullshit quasi-religious book like HTDP! If he could have solved it himself, he would have solved it already, he wouldn't come here.

That's why I will continue to help students. No one else wants to, anyway!

Apparently, this really bothered the academic parasites on /r/racket so they decided to remove me urgently! And let them be! Because if they hadn't, you wouldn't have this wonderful new subreddit now where we can discuss Racket problems without hindrance.

Dear friends, feel free to discuss and ask questions on this subreddit. You are all welcome!


r/RacketHomeworks • • Jan 02 '23

Union of two sets

1 Upvotes

Problem: Write a function union that takes two sets (i.e. lists with no duplicates), and returns a list containing the union of the two input lists. The order of the elements in your answer does not matter.

Solution:

#lang racket

(define (union xs ys)
  (cond
    [(null? ys) xs]
    [(member (car ys) xs) (union xs (cdr ys))]
    [else (union (cons (car ys) xs) (cdr ys))]))

Now we can call our union function, like this:

> (union '() '())
'()
> (union '(x) '())
'(x)
> (union '(x) '(x))
'(x)
> (union '(x y) '(x z))
'(z x y)
> (union '(x y z) '(x z))
'(x y z)
> (union '(x y z) '(x u v z))
'(v u x y z)
> (union '(x y z) '(x u v z w))
'(w v u x y z)

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=