Racket try :D

hw3.rkt

#lang racket

(require racket/match)

(provide (all-defined-out))

(define (list-nth xs n)
  (if (= n 0)
      (car xs)
      (list-nth (cdr xs) (- n 1))))

;задача 1
(define (list-nth-mod xs n)
  (match* (xs n)
    [((? null?) _)     (error "list-nth-mod: empty list")]
    [(_ (? negative?)) (error "list-nth-mod: negative number")]
    [(_ _) (let* ([l (length xs)]
                  [i (remainder n l)])
             (list-nth xs i))]))

(define (stream->list xs)
   (let ([c (xs)])
     (if (null? c)
         null
         (let ([h (car c)]
               [t (cdr c)])
           (cons h (stream->list t))))))

(define empty-stream
  (λ () null))

;(stream->list empty-stream)

(define (stream-once x)
  (λ () (cons x empty-stream)))

;(stream->list (stream-once 1))

(define (stream-cons x xs)
  (λ () (cons x xs)))

;(stream->list (stream-cons 1 (stream-once 2)))

(define (stream x . xs)
  (if (null? xs)
      (stream-once x)
      (stream-cons x (apply stream xs))))

;(stream->list (stream 1 2 3 4))

(define (stream-empty? xs)
  (null? (xs)))

;(stream-empty? empty-stream)
;(stream-empty? (stream-once 1))

(define (stream-first xs)
  (if (stream-empty? xs)
      (error "stream-first: stream is empty")
      (car (xs))))

;(stream-first (stream 1 2 3))

(define (stream-rest xs)
  (if (stream-empty? xs)
      (error "stream-rest stream is empty")
      (cdr (xs))))

;(stream->list (stream-rest (stream 1 2 3 4)))

(define (stream-take n xs)
  (if (or (= n 0) (stream-empty? xs))
      empty-stream
      (stream-cons (stream-first xs) (stream-take (- n 1) (stream-rest xs)))))

;(stream->list (stream-take 2 (stream 1 2 3 4)))

(define (stream-skip n xs)
  (cond [(stream-empty? xs) empty-stream]
        [(= n 0) xs]
        [#t (stream-skip (- n 1) (stream-rest xs))]))

;(stream->list (stream-skip 2 (stream 1 2 3 4)))

(define (stream-unfold f s)
  (λ ()
    (let ([news (f s)])
      (cons news (stream-unfold f news)))))

;(stream->list (stream-take 10 (stream-unfold (λ (x) (+ x 1)) 0)))

;задача 2
(define (stream-for-n-steps s n)
  (stream->list (stream-take n s)))

;(stream-for-n-steps (stream 1 2 3) 2)

;задача 3
(define (stream-map s f)
  (let loop ([s s])
    (if (stream-empty? s)
        empty-stream
        (λ () (cons (f (stream-first s)) (loop (stream-rest s)))))))

;(stream->list (stream-map (stream 1 2 3) (λ (x) (+ x 1))))

;задача 4
(define (combine-streams s1 s2 f)
  (match* (s1 s2)
    [((? stream-empty? s1) _) (stream-map s2 f)]
    [(_ (? stream-empty? s2)) (stream-map s1 f)]
    [(_ _)
     (λ () (cons (f (stream-first s1) (stream-first s2))
                  (combine-streams (stream-rest s1) (stream-rest s2) f)))]))

;(stream->list (combine-streams (stream 1 2 3 4) (stream 1 2 3) +))

;задача 5
(define (skip-first-n s n)
  (stream-skip n s))

;(stream->list (skip-first-n (stream 1 2 3 4) 2))

(define nats
  (stream-unfold (λ (x) (+ x 1)) 0))

;(stream->list (stream-take 10 nats))

;задача 6 а
(define funny-number-stream
  (stream-map nats
              (λ (x)
                (if (= 0 (remainder x 5))
                    (* -1 x)
                    x))))

;(stream->list (stream-take 10 funny-number-stream))

;задача 6 б
(define (squares s)
  (stream-map s (λ (x) (* x x))))

;(stream->list (stream-take 10 (squares nats)))

(define (taylor-elem x n)
  (/ (* (expt -1 (- n 1)) (expt x n)) n))

;задача 7
(define (taylor x)
  (define (infinite-sum n)
    (λ () (cons (taylor-elem x n) (infinite-sum (+ n 1)))))
  (infinite-sum 1))

;(stream->list (stream-take 5 (taylor 5)))

(define (list->inf-stream xs)
  (define (iter temp-xs)
    (λ ()
      (if (null? temp-xs)
          ((iter xs))
          (cons (car temp-xs) (iter (cdr temp-xs))))))
  (iter xs))

;(stream->list (stream-take 10 (list->inf-stream (list 1 2 3))))

;задача 8
(define (cycle-lists xs ys)
  (let ([xs (list->inf-stream xs)]
        [ys (list->inf-stream ys)])
    (combine-streams xs ys cons)))

;(stream->list (stream-take 10 (cycle-lists (list 1 2 3) (list "a" "b" "c" "d"))))

(define fib-cache
  (vector-append (vector 1 1 2 3) (make-vector 97)))

(define trib-cache
  (vector-append (vector 1 1 2 4) (make-vector 97)))

(for ([i (in-range 4 101)])
  (let ([f1 (vector-ref fib-cache  (- i 1))]
        [f2 (vector-ref fib-cache  (- i 2))]
        [t1 (vector-ref trib-cache (- i 1))]
        [t2 (vector-ref trib-cache (- i 2))]
        [t3 (vector-ref trib-cache (- i 3))])
    (vector-set! fib-cache  i (+ f1 f2))
    (vector-set! trib-cache i (+ t1 t2 t3))))

;задача 9
(define (stairs n)
  (vector-ref trib-cache n))

(define stairs2-cache (make-hash))

;задача 10
(define (stairs2 n k)  
  (cond [(<= k 0) (vector-ref fib-cache  n)]
        [(>= k (floor (/ n 3))) (vector-ref trib-cache n)]
        [#t (hash-ref! stairs2-cache (cons n k)
                       (λ () (+ (stairs2 (- n 1) k)
                                (stairs2 (- n 2) k)
                                (stairs2 (- n 3) (- k 1)))))]))

;(time (stairs2 40 5))