Paradygmaty programowania/Ćwiczenia 11: Programowanie funkcyjne w Haskellu II

Zadanie 1

Zdefiniować odejmowanie dla typu Nat w dwóch wariantach: zupełnym i częściowym. W pierwszym odjęcie większej liczby od mniejszej ma dawać zero. W drugim wartość taka ma być nie zdefiniowana. Co się stanie, jeśli spróbujemy jednak odjąć większą liczbę od mniejszej?

Wskazówka:

Odejmowanie częściowe może wyglądać tak:

 odjNat :: (Nat, Nat) -> Nat
 odjNat (x, Zero) = x
 odjNat (Nast x, Nast y) = odjNat (x, y)

Jeśli spróbujemy odjąć większą liczbę od mniejszej, to Haskell zgłosi błąd polegający na niemożności dopasowania wyrażenia do wzorca — prędzej czy później w toku rekurencji pojawi się bowiem wyrażenie odjNat (Zero, Nast ...), które nie pasuje do żadnego przypadku z definicji. Żeby zdefiniować odejmowanie zupełne, wystarczy dołożyć trzeci przypadek:

 odjNat (Zero, x) = Zero

Zadanie 2

Zdefiniować silnię jako stosowną aplikację funkcji rekdef.

Wskazówka:

Spróbujmy stworzyć ciąg par, w których pierwszy element to kolejne liczby naturalne, a drugi to kolejne silnie. A zatem można tak:

 silnia :: Integer -> Integer
 silnia = snd . rekdef g (0, 1)
   where g (x, y) = (x + 1, (x + 1)*y)

Zauważmy, że stosujemy tu ponownie technikę „łączenia w pary”.

Zadanie 3*

Poniższa funkcja ma sprawdzać, czy podana lista jest pusta. Dlaczego definicja ta jest niepoprawna?

 pusta1 :: [a] -> Bool
 pusta1 x = (x == [])

Wskazówka:

Konieczna jest klauzula ograniczająca typ a do klasy Eq, by Haskell zgodził się na użycie operatora ==, określonego przecież dla typów z klasy Eq. Sygnatura powinna zatem wyglądać tak:

 pusta1 :: Eq a => [a] -> Bool

Zadanie 4

Rozważmy zatem inny wariant sprawdzania pustości listy. Wykorzystajmy funkcję, która wylicza długość listy:

 pusta2 :: [a] -> Bool
 pusta2 x = (dl x == 0)

Ta definicja jest poprawna, ma jednak poważną wadę. Jaką? Jak ją wyeliminować, tzn. jak napisać dobrą funkcję sprawdzającą pustość listy?

Wskazówka:

Sprawdzenie pustości listy jest tu poprzedzone wyliczeniem jej długości — a to przecież jest strata czasu. Co gorsza, takie sprawdzenie nie zadziała dla list nieskończonych, np. [1..]. Dobra funkcja może wyglądać jak poniżej; nie czynimy tu żadnych założeń o typie a, ani nie liczymy długości listy.

 pusta3 :: [a] -> Bool
 pusta3 [] = True
 pusta3 (_:_) = False

Zadanie 5

Napisać funkcję, która zwraca ostatni element niepustej listy. Funkcja powinna działać dla list dowolnego typu, bez jakichkolwiek dodatkowych założeń.

Wskazówka:

Problem jest taki sam, jak w zadaniu 3. Trzeba zatem wystrzegać się operatora ==.

Zadanie 6

Zdefiniować funkcję połącz, która połączy listę list w jedną listę. Przykładowo, połącz [[1, 2], [3, 4, 5], [6]] ma dać wynik [1, 2, 3, 4, 5, 6].

Wskazówka:

To jest proste:

 połącz :: a -> [a]
 połącz [] = []
 połącz (x:xs) = x ++ połącz xs

Zadanie 7

Przy funkcji połącz zdefiniowanej tak jak w poprzednim zadaniu, które wywołania są poprawne?

• połącz [[[]]]
• połącz [[1, 2], [], [3]]
• połącz [[[1, 2]], [], 3]
• połącz [[[1, 2]], [[]], 3]
• połącz [[], [[]], [[[]]]]
• połącz [[1], 2, [[[3]]]]

Wskazówka:

Wszystkie z wyjątkiem ostatniego. We wszystkich bowiem przypadkach poza ostatnim Haskell jest w stanie dobrać taki typ a, żeby uzyskać zgodny z sygnaturą typ parametru a. Przykładowo, w dwóch środkowych wywołaniach a to [Integer]. Pouczające jest obejrzenie wyników wszystkich tych wywołań...