Paradygmaty programowania/Ćwiczenia 12: Programowanie funkcyjne w Haskellu III

From Studia Informatyczne

Spis treści

Zadanie 1

Napisać definicję leniwego operatora alternatywy na liczbach całkowitych, nie korzystając ze standardowego operatora ||.

Wskazówka:

Można użyć dopasowywania do wzorca lub odpowiedniej kaskady wyrażeń warunkowych.

 nibyalt :: Integer -> Integer -> Integer
 nibyalt 0 y = y
 nibyalt x y = 1

Zauważmy, że powyższa definicja jest prosta, ale ma dwa drobne mankamenty: wykorzystuje konkretną kolejność dopasowywania (od góry do dołu) oraz zwraca wartość różną od 1, jeśli x = 0 i y ≠ 1. Definicja z kaskadą wyrażeń warunkowych jest za to obszerniejsza:

 nibyalt :: Integer -> Integer -> Integer
 nibyalt x y = if x /= 0 then 1 else if y /= 0 then 1 else 0

Zadanie 2

Zapisać za pomocą wyrażeń z kwalifikatorem listę trójek pitagorejskich (czyli liczb naturalnych x, y, z takich, że x^2 + y^2 = z^2) z ustalonego zakresu. Chodzi zatem o funkcję o sygnaturze:

 trójkipit :: Integer -> [(Integer, Integer, Integer)]

Dla danego n powinna ona stworzyć listę wszystkich trójek pitagorejskich, których elementy należą do przedziału [1...n].

Wskazówka:

Najprościej jest stworzyć najpierw funkcję, która wygeneruje listę trójek z podanego zakresu, a potem odfiltrować z nich tylko trójki pitagorejskie. A więc np.

 trójki :: Integer -> [(Integer, Integer, Integer)]
 trójki n = [(x,y,z) | x<-[1..n], y<-[1..n], z<-[1..n]]
 
 pit :: (Integer, Integer, Integer) -> Bool
 pit (x, y, z) = (x*x + y*y == z*z)
 
 trójkipit :: Integer -> [(Integer, Integer, Integer)]
 trójkipit = (filter pit) . trójki

Oczywiście można zawrzeć cały program w jednej funkcji.

Zadanie 3

Jak zmienić program z poprzedniego zadania, by nie wypisywał niepotrzebnie podobnych trójek, np. (3, 4, 5) i (4, 3, 5)?

Wskazówka:

Wystarczy zmienić definicję funkcji trójki tak, by generowała tylko trójki spełniające warunek x ≤ y ≤ z. Można to zrobić tak:

 trójki :: Integer -> [(Integer, Integer, Integer)]
 trójki n = [(x,y,z) | x<-[1..n], y<-[x..n], z<-[y..n]]

Zadanie 4

Napisać funkcję lsilnia, która dla danego n ≥ 1 wygeneruje listę silni liczb od 1 do n. Przykładowo, wywołanie lsilnia 4 ma dać listę [1, 2, 6, 24]. Jak zrobić to efektywnie?

Wskazówka:

Oczywiście należy unikać liczenia silnia dla każdej liczby od początku. Można więc tak jak poniżej, z tym że trzeba wówczas na końcu odwrócić wytworzoną listę.

 lsilnia :: Integer -> [Integer]
 lsilnia 1 = [1]
 lsilnia (n+1) = ((n+1)*y) : y : ys where (y:ys) = lsilnia n

Zadanie 5*

Zdefiniować operator >> za pomocą >>=.

Wskazówka:

Wywołania p >> q oraz p >>= q oznaczają, że wywołujemy p i q w takiej właśnie kolejności. Dla operatora >>= ta zależność czasowa bierze się stąd, że q wywoływane jest z wartością wyliczoną przez p. Chcąc zdefiniować >>, musimy oprzeć się na tej samej zależności, lecz zignorować wyliczoną przez p wartość.

 (>>) :: IO a -> IO b -> IO b
 p >> q = p >>= f where f x = q

Zadanie 6

Co się stanie przy poniższych wywołaniach? Sprawdź...

 getChar >>= return
 return ’a’ >>= putChar

Wskazówka:

Można powiedzieć, że return zamienia wartość typu a na IO a, zaś >>= — na odwrót.