Celem tego laboratorium jest przećwiczenie operacji na listach.
Środkiem do tego celu będą operacje na wielomianach symbolicznych.
Wielomiany reprezentujemy jako listę współczynników (typu float) od końca,
np. lista [3.; 5.; 7.] oznacza wielomian \(7x^2 + 5x + 3\).
Zanim przystąpimy do dalszego ciągu należy zdecydować, czy lista może być pusta, czy może kończyć się zerem itp.
Po podjęciu decyzji należy ją zapisać w komentarzu do definicji typu oraz się jej trzymać, tzn.:
Należy zaimplementować następujące rzeczy:
type wielomian = ...
val oblicz : wielomian -> float -> float
(** [oblicz w x] oblicza wartość wielomianu [w] w punkcie [x] *)
val suma : wielomian -> wielomian -> wielomian
(** Suma wielomianów *)
val iloczyn : wielomian -> wielomian -> wielomian
(** Iloczyn wielomianów *)
val pochodna : wielomian -> wielomian
(** Pochodna wielomianu *)
val stopien : wielomian -> int
(** Zwraca stopień wielomianu (czyli najwyższą potęgę argumentu, przy której wykładnik jest różny od 0.) *)
val calka : wielomian -> wielomian
(** Calka wielomianu. [calka w] ma wyraz wolny równy 0. *)
Dobrze by było napisać też kilka generatorów większych wielomianów, np. jed n zwraca
\(x^n + x^{n-1} + \dots + 1\), jed_zer n zwraca \(x^{2n} + x^{2n-2} + \dots + x^2 + 1\) itp.
Należy zwrócić uwagę na złożoność operacji oraz czy implementacja jest ogonowa, czy nie
(o ile ma to wpływ na złożoność pamięciową) i zapisać te spostrzeżenia w komentarzu.
Wielomiany rzadkie, jak sama nazwa wskazuje, mają tylko niektóre współczynniki różne od zera, np. \(x^{1000} + 5x^{50} + 2x^{10} + 1\).
Ponieważ szkoda byłoby miejsca na przechowywanie takich wielomianów w sposób przedstawiony powyżej, będziemy reprezentować
je jako listę par (wykładnik,współczynnik) posortowaną wg rosnących wykładników.
Nasz przykładowy wielomian reprezentowany będzie przez [(0,1.); (10,2.); (50,5.); (1000;1.)].
Dla tej reprezentacji należy zaimplementować osobny zestaw narzędzi, składający się z definicji typu:
type rzadki = ...
i tych samych funkcji co powyżej, przy czym do wszystkich nazw należy dołączyć sufiks _rz (np. oblicz_rz),
a we wszystkich typach należy zastąpić wielomian przez rzadki.
W tym zadaniu również należy najpierw zastanowić się, czy (niektóre) współczynniki mogą być równe 0., jak
reprezentowany jest wielomian stale równy zero itp.
Należy zaimplementować funkcje konwertujące wielomiany zwykłe na rzadkie i z powrotem:
val rozrzedz : wielomian -> rzadki
(** Konwertuje wielomian do postaci rzadkiej usuwając wszystkie współczynniki równe 0. *)
val zagesc : rzadki -> wielomian
(** Kowertuje wielomian do postaci zwyklej dodajac (o ile trzeba) wyrazy o współczynnikach równych 0. *)
Do powyższych zestawów funkcji operujących na wielomianach dopisać funkcję przybliżającą miejsca zerowe wielomianu
(funkcja ta powinna zwracać listę wartości typu float).
Wskazówka: jak mają się miejsca zerowe wielomianu do miejsc zerowych jego pochodnej?