---
# System prepended metadata

title: MP wykład 2 (II tercja)
tags: [MP]

---

###### 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:

```plait!
(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ć:

```plait!
(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ą.

```plait
(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?

```racket
(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

```plait
(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ć?

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

Albo lepiej:

```plait
(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