YPP1:assoc.scm [Ci.bule]

assoc.scm

#!/usr/bin/env racket
#lang racket/base

viz assoc

assoc ¹⁾

(define (collate l) ;vlastne upravene cons-assoc, reseni na urovni lekce 6
  (foldl
    (lambda (e t)
      (if (exists (lambda (x) (equal? e (car x))) t)
        ;existuje, najdeme a inkrementujeme
        (map
          (lambda (x)
            (if (equal? e (car x))
              (cons e (+ 1 (cdr x)));inkrementujeme
              x))
          t)
        ;nenasli, novy par
        (cons (cons e 1) t)))
    '();term/kontext bude alist
    l))
(collate '(1  2 2  3 3 3)) ;=>((1 . 1) (2 . 2) (3 . 3))
(exit)

(sort lst

       less-than?        
       [ #:key extract-key        
       #:cache-keys? cache-keys?])   →   list?

       lst : list?
       less-than? : (any/c any/c . -> . any/c)
       extract-key : (any/c . -> . any/c) = (lambda (x) x)
       cache-keys? : boolean? = #f

(sort '(1 2 4 3) <)
(sort '(1 2 4 3) >)
(sort '((b . 2) (a . 1) (c . 3)) (lambda (x y) (< (cdr x) (cdr y))))

prida nebo aktualizuje key val

(define (cons-assoc-iter key val assoc)
  (if (null? assoc)
    (list (cons key val))
    (foldl ;'rychlejsi' nez foldr, ale dela reverse!
      (lambda (e t)
        (if (equal? key (car e))
          (cons (cons key val) t) ;#vymenime
          (cons-assoc-iter key val (cons e t))));#kopirujeme a hledame dal
      '()
      assoc)))
 
'(cons-assoc-iter k v al)
(cons-assoc-iter 1 1 '())
(cons-assoc-iter 1 2 '((1 . 1)))
(cons-assoc-iter 2 2 '((1 . 1)))
 
 
 ; vim: syntax=racket

¹⁾

k1 . v1) (k2 . v2) …) operace: (cons-assoc key val assoc) nastav nebo pridej assoc pole (assoc-key assoc key) hledej; racket: (assoc key alist) (assoc-del assoc key) zrus klic v rnrs je alist jako ((k v) (k v) …) racket: (assoc key alist) → (key …) ;equal? racket: (assv key alist) → (key …) ;eqv? racket: (assq key alist) → (key …) ;eq? (exists pred list) (forall pred list)

'(exists pomoci akumulace, foldl:)
(define (exists p l)
  (foldl
    (lambda (e t)
      (if t ;uz nasli, vracej porad #t
        t
        (p e)))
    #f
    l))
 
(exists (lambda (x) (= x 1)) '(1 2 3))
(exists even? '(1 2 3))
(exists even? '(1 5 3))

pomoci iterace lze jen and a or, viz L9

'(exists pomoci iterace:)
(define (exists-iter p l)
  (cond
    ((null? l) #f) ;prazdny seznam, nebo jsme na konci
    ((p (car l)) #t);nasli
    (else (exists-iter p (cdr l)))))
 
(exists-iter (lambda (x) (= x 1)) '(1 2 3))
(exists-iter even? '(1 2 3))
(exists-iter even? '(1 5 3))

pouzit exists str159, existuje? premapovat, jinak pridat (define (cons-assoc key val assoc) assoc) ;todo pomoci fold, iterace? sel by exist-iter inline jako letrec? NOTE: Lekce 6 jeste nezná akumulace, fold

(define (cons-assoc key val assoc)
  (if (exists (lambda (x) (equal? key (car x))) assoc)
    ;existuje, najdeme a pre-map-ujeme
    (map
      (lambda (x)
        (if (equal? key (car x))
          (cons key val)
          x))
      assoc)
    ;nenasli, novy par
    (cons (cons key val) assoc)))
 
(define al (cons-assoc 'a 1 '()))
(cons-assoc 'a 2 al)
(cons-assoc 'b 3 al);porad dva prvky!!! nemuze modifikovat al!!!
(cons-assoc 'c 4 al);takze nabalovat se to muze rekurzi, fold-rem apod!
(cons-assoc 'c 4 al)
(cons-assoc 'd 5 '((d . 5)))

(collate: '(1 1 2 2 3 3 3) ⇒ ((1 . 1) (2 . 2) (3 . 3

bule.cz wiki

2014/2015

2015/2016

assoc.scm