Racket-Homework 1 Solved

Questions
Define the following functions, all of which consume five characters and return a string.The function append5 – consumes 5 characters and returns the concatenation of them. For example, (append5 #\a #\b #\c #\d
#\e) would return "abcde". Here is another example, written in a form of a test that you can use: 

(test (append5 #\e #\d #\c #\b #\a) = "edcba")

The function permute3 – consumes 3 characters and returns a list of strings the concatenation of them in any possible ordering (you may assume all of them are distinct). Important: make sure to declare the most precise type for the returned value of your function. For example, if you know you are using a list of two naturals, then, (List Natural Natural) is more precise than (Listof Any).
Here is an example, written in a form of a test that you can use. 

(test (permute3 #\a #\b #\c) = 

          '("abc" "acb" "bac" "bca" "cab" "cba"))

 

Reminder:
Remember that lists are defined inductively as either: 

An empty list — null
A cons pair (sometimes called a “cons cell”) of any head value and a list as its tail — (cons x y)
A “Listof T” would be similar, except that it will use the type T (which needs to be defined by you, say, Symbol, Natural, or Number) instead of

“any”. 

 

With this in mind, define a recursive function count-3lists that consumes a list of lists (where the type of the elements in the inner lists may be any type) and returns the number of inner lists (within the wrapping list) that contain exactly 3 elements.
 

For example, written in a form of a test that you can use: 

(test (count-3lists '((1 3 4) (() (1 2 3)) ("tt" "Three" 7) (2 4 6 8) (1 2 3))) = 3)

Define a function count-3lists-tail that works the same as count-3lists, but now you need to use tail-recursion.
 

You can use the same example (only here the name of the function is count-3lists-tail):

(test (count-3lists-tail '((1 3 4) (() (1 2 3)) ("tt" "Three" 7) (2 4 6 8) (1 2 3))) = 3)

Write an additional function count-3listsRec that is similar to the above count-3lists, however counts the number of lists of length 3 recursively (i.e., on all levels of nesting).
 

For example, written in a form of a test that you can use: 

(test (count-3listsRec '((1 3 4) (() (1 2 3)) ("tt" "Three" 7) (2 4 6 8) (1 2 3))) = 4)

 

In this question we will implement a keyed-stack data structure. In this data structure you will need to define a new type called Each element in the stack will be keyed (indexed) with a symbol. In the following the operations that you are required to implement are detailed below, together with some guidance.Implement the empty stack EmptyKS – this should be a variant of the data type (constructor).
Implement the push operation Push – this too should be a variant of the data type. The push operation should take as input a symbol (key), a string (value), and an existing keyed-stack and return an extended keystack in the natural way – see examples below.
Implement the search operation search-stack – the search operation should take as input a symbol (key) and a keyed-stack and return the first (LIFO, last in first out) value that is keyed accordingly – see examples below. If the key does not appear in the original stack, it should return a #f value (make sure the returned type of the function supports this; use the strictest type possible for the returned type).
Implement the pop operation pop-stack – the pop operation should take as input a keyed-stack and return the keyed-stack without its first (keyed) value – see examples below. If the original stack was empty, it should return a #f value (make sure the returned type of the function supports this; use the strictest type possible for the returned type).
 For example, written in a form of a test that you can use: 

(test (EmptyKS) = (EmptyKS))

(test (Push 'b "B" (Push 'a "A" (EmptyKS))) = 

      (Push 'b "B" (Push 'a "A" (EmptyKS))))

(test (Push 'a "AAA" (Push 'b "B" (Push 'a "A"  (EmptyKS)))) = (Push 'a "AAA" (Push 'b "B" (Push 'a "A" (EmptyKS)))))

(test (search-stack 'a (Push 'a "AAA" (Push 'b "B" (Push 'a "A" (EmptyKS))))) = "AAA")

(test (search-stack 'c (Push 'a "AAA" (Push 'b "B" (Push 'a

"A" (EmptyKS))))) = #f)

(test (pop-stack (Push 'a "AAA" (Push 'b "B" (Push 'a "A" (EmptyKS))))) = (Push 'b "B" (Push 'a "A" (EmptyKS)))) 

(test (pop-stack (EmptyKS)) = #f)
 

In this question you are given full code together with tests for the presented functions. All you are required to do is to add the appropriate comments for each of the functions. These comments should describe what the function takes as input, what it outputs, what its purpose is, and how it operates. Do not forget to also add your personal remarks on the process in which you personally came to realize the above. You should copy the following code into your .rkt file, and add the comment therein.
 

(: is-odd? : Natural - Boolean)

;; << Add your comments here ;; << Add your comments here
(define (is-odd? x)   (if (zero? x)       false

      (is-even? (- x 1))))

 

(: is-even? : Natural - Boolean)

;; << Add your comments here ;; << Add your comments here
(define (is-even? x)   (if (zero? x)       true

      (is-odd? (- x 1))))

 

;; tests --- is-odd?/is-even?

(test (not (is-odd? 12)))

(test (is-even? 12))

(test (not (is-odd? 0)))

(test (is-even? 0))

(test (is-odd? 1))

(test (not (is-even? 1)))

 

(: every? : (All (A) (A - Boolean) (Listof A) - Boolean)) ;; See explanation about the All syntax at the end of the file…

;; << Add your comments here ;; << Add your comments here
 (define (every? pred lst)

  (or (null? lst)

      (and (pred (first lst))

           (every? pred (rest lst)))))

 

 

;; An example for the usefulness of this polymorphic function

(: all-even? :   (Listof Natural) - Boolean)

;; << Add your comments here ;; << Add your comments here
 (define (all-even? lst)

  (every? is-even? lst))

 

 

;; tests

(test (all-even? null))

(test (all-even? (list 0)))

(test (all-even? (list 2 4 6 8)))

(test (not (all-even? (list 1 3 5 7))))

(test (not (all-even? (list 1))))

(test (not (all-even? (list 2 4 1 6))))

 

(: every2? : (All (A B) (A - Boolean) (B - Boolean) (Listof A) (Listof B) - Boolean))

;; << Add your comments here ;; << Add your comments here
 (define (every2? pred1 pred2  lst1 lst2)

  (or (null? lst1) ;; both lists assumed to be of same length

      (and (pred1 (first lst1))

           (pred2 (first lst2))

           (every2? pred1 pred2 (rest lst1) (rest lst2)))))

 

syntax


(All (a ...) t) (All (a ... a ooo) t)

is a parameterization of type t, with type variables v .... If t is a function type constructed with infix -, the outer pair of parentheses around the function type may be omitted.

Examples:

(: list-length : (All (A) (Listof A) - Natural))

(define (list-length lst)

    (if (null? lst)

        0

          (add1 (list-length (cdr lst)))))

(list-length (list 1 2 3))

- : Integer [more precisely: Nonnegative-Integer]

3  

In the above example, all elements in the list argument must be of the same (polymorphic) type.