###### tags: `MP`
# MP wykład 2 (II tercja)

## Co wcześciej:
1. Indukcja strukturalna => względem jakiejś struktury do:
- dowodzenia poprawności programów
- uczyliśmy się żeby pisać czytelny, zrozumiały kod???

## Listy

Wcześniej robiliśmy:

(define (my-map f xs)
 (if (empty? xs) empty 
     (cons (f first xs) (my-map f (rest xs)))))

Problem jest taki, że taki program jest narażony na dużo błędów a system typów nie pomoże (jeśli się zapętlimy to i tak zostanie otypowana). Można zrobić:

(define (my-map f xs)
 (type-case (Listof 'a) xs
 	[empty empty]
	[(cons x xs) (cons (f x) (my-map f xs))]))

To daje nam:
1. czytelniejszy kod
2. łatwiejsze unikanie błędów

Jak mamy dwie zmienne o tej samej nazwie, to nie możemy się odwołać do starej wartości, więc nie jesteśmy w stanie przypadkiem się zapętlić.

W type-case:
1. kolejność nie ma znaczenia (w plaicie)
2. jak zapomnimy o jakimś to jest zgłaszany błąd

W trzeciej tercji to nam się przyda, np. gdy będziemy chcieli dodać nową rzecz do naszego języka programowania, bo plait nam powie gdzie trzeba ten przypadek rozważyć.

W Lispie programy to lista, w której mogą być pozagnieżdżane inne listy, dlatego są te wszystkie nawiasy i generalnie racket i plait wyglądają jak wyglądają.

(define-type (Tree 'a)
 (leaf)
 (node [l : (Tree 'a)] [elem: 'a] [r : (Tree 'a)]))
 
(define (insert x t)
 (type-case (Tree 'a) t
  [(leaf) (node (leaf) x (leaf))]
  [(node l y r)
    (if < x y)
		(node (insert x l) y r)
		(node l y (insert x r))]))

Jak to by wyglądało w Rackecie?

(struct leaf () #:transparent)
(struct node (l elem r) #:transparent)

(define (insert x t)
 (match t 
 	[(leaf) (node (leaf) x (leaf))]
	[(node l y r)
    (if < x y)
		(node (insert x l) y r)
		(node l y (insert x r))]))

Tutaj te l, y, r mogą być np parametrami wzorców, np. zamiast l może być (leaf), oczywiście tylko w Rackecie.

## Zaimplementujmy kolejki

(define-type (Queue 'a)
 (queue (f : Listof 'a) (r : Listof 'a)))
 
(define (queue-empty)
  (queue empty empty))
  
(define (push q x)
 (type-case (Queue 'a) q
   [(queue f r) (queue f (cons x r))]))
   
(define (pop q)
 (type-case (Queue 'a) q
   [(queue f r) ...]))
   
(define (is-empty? q)
  (type-case (Queue 'a) q
   [(queue f r) (null? f)] ;mamy niezmiennik że f jest puste
   ;tylko gdy cała lista jest pusta
   
...

Tutaj bawimy się i generalnie robimy to samo co robiliśmy na zadaniu takim samym na liście.

### Jak można to poprawić?

(define-type (Queue 'a)
 (empty-queue)
 (queue (f : ('a * Listof 'a)) (r : (a' * Listof 'a))))

Albo lepiej:

(define-type (Queue 'a)
 (empty-queue)
 (queue (h : 'a ) (f : Listof 'a) (r : Listof 'a)))

Przerobiliśmy kod, coś to dało, ale "być może nie było to potrzebne". Udało się wyrazić niezmiennik w typach, więc mamy pewność, że będzie zachowany. Wada jest taka, że kod jest znacznie dłuższy.

#### Na 3 godzinie nie byłam