Haskell. Plac ćwiczeń dla uczonych

Bezpłatny fragment

Haskell i myślenie funkcyjne

O co w tym wszystkim chodzi

Szybkie ćwiczenie

Typy danych są niedrogie

Dopasowywanie do wzorców

Rekurencja, sterowanie i funkcje wyższego rzędu

Inne własności

Haskell w praktyce

Po jednym kroku

Generowanie kandydatów

Filtrowanie słownikowe

Wyszukiwanie wszerz

Użycie wyszukiwania

Wydajność i optymalizacja

Przypisy

HASKELL I MYŚLENIE FUNKCYJNE

AUTOR – Paul Callaghan

Jak myślą programiści funkcyjni? Moim celem jest pokazać fragment stylu programowania oraz sposób myślenia doświadczonych programistów funkcyjnych, aby można było zobaczyć, dlaczego tak się pasjonujemy tym, co robimy. Kilka z tych pomysłów dobrze objaśniono w książkach i moim zdaniem są kluczowe do uchwycenia języka funkcji i produktywnego korzystania z niego w prawdziwych aplikacjach.

Większość tego, o czym piszę, odnosi się do języka Haskell, choć wiele idei dotyczy także innych języków funkcyjnych.

O co w tym wszystkim chodzi

Najważniejsza idea nowoczesnego programowania funkcyjnego brzmi:

Chodzi o dane.

Programiści funkcyjni na pierwszym miejscu stawiają dane. Zaczynamy myśleć o tym, z jakimi rodzajami danych mamy problem w danej dziedzinie i jakie przekształcenia chcemy na nich wykonać. Gdy uchwycimy ten aspekt, zaczynamy tworzyć struktury danych i pisać kod do wykonywania przekształceń.

Programowanie funkcyjne to nie tylko kodowanie za pomocą czystych funkcji. Nowoczesne języki funkcyjne dotyczą tworzenia jeszcze lepszych narzędzi, które wspomagają styl programowania stawiający dane na pierwszym miejscu. Chodzi o zapewnienie łatwiejszych sposobów określania silnych typów danych, manipulowania nimi na wysokim poziomie, podziału na części i ponownego łączenia. To wszystko powinno być robione na odpowiednim poziomie bezpieczeństwa i wielokrotnego stosowania, bez zbyt wielkiego obciążenia składniowego lub szczegółów implementacyjnych zapychających kod.

Ponieważ do tego są one zaprojektowane, pamiętanie o tym, aby dane stawiać na pierwszym miejscu, jest kluczowe, jeśli chcemy dobrze używać tych narzędzi. Przyjęcie w pełni imperatywnego podejścia w języku funkcyjnym nie kończy się dobrze. Te narzędzia nie są zaprojektowane do takiej pracy.

Kto używał potoków w powłokach uniksowych? Te bardzo dobre wprowadzenie do myślenia funkcyjnego i warto powędrować po świecie Uniksa przed przejściem do Haskella.

Przypuśćmy na przykład, że chcemy wybrać trzy najbardziej pamięciożerne procesy będące własnością użytkowników, których nazwy logowania zaczynają się od „foo”. Nie ma magicznego polecenia Uniksa, które to zrobi, ale łatwo można je zbudować, składając mniejsze fragmenty. Jest to kluczowa idea Uniksa, który dostarcza małe narzędzia do wykonywania kroków na danych, a także sposób na sklejenie tych kroków ze sobą. Pozostawię czytelnikom szczegóły tego przykładu, ale zapewne można wykorzystać ps do otrzymania listy procesów, grep do wybrania pasujących wierszy, sort dla konkretnej kolumny i wreszcie head w celu pobrania kilku pierwszych wierszy.

Inny przykład – jak policzyć, ile procesów uruchomionych przez użytkowników Freda i Joe wykorzystuje więcej niż 100 MB pamięci wirtualnej? Możemy potrzebować wc do policzenia wierszy oraz awk (lub perl, lub ruby) do filtrowania liczbowego. Szczegóły nie są istotne.

Ważne jest, aby zauważyć, jakich danych używamy (wiersze, każdy z określonymi polami) oraz jak przekształcamy dane w potoku kroków wykonywanych po kolei. Popatrzmy na kod – zwykle dość jasno pokazuje, co robi.

Szybkie ćwiczenie

Zobaczmy, ile uda się zrozumieć z Haskella, po prostu rozpatrując nieformalne podręczne rozwiązanie, a potem oglądając odpowiadający mu kod. Jest to rozwiązanie związane z „myśleniem danymi”, ale zapewne całkiem inne niż podejście do problemu, jakie obserwowaliśmy wcześniej. Bez dzielenia modulo lub instrukcji if otrzymamy „Funkcyjny Fizz Buzz”.

Zadanie jest takie: wyświetlamy Fizz co trzeci krok, a Buzz co piąty.

Cykle czasem nachodzą na siebie. Popatrzmy na nie.

threes = cycle ["", "", "Fizz"]

fives = cycle ["", "", "", "", "Buzz"]

cycle jest zdefiniowany jak niżej (prawdziwa definicja z biblioteki jest bardziej wydajna, ale mniej czytelna):

cycle xs = xs ++ cycle xs -- SIMPLE version of lib

Tak więc threes wyświetla ["","","Fizz","","","Fizz",... ] aż do jego zatrzymania, i podobnie działa fives. Następnie chcemy połączyć oba strumienie w jeden – zdarza się to często, więc mamy do tego funkcję biblioteczną. zipWith łączy elementy w pary i wykorzystuje pewne działania do powiązania każdej pary:

zipWith g [a,b,c,...] [d,e,f, ...] ===>

      (computes to) [g a d, g b e, g c f, ...]

eg zipWith max [1,2,3] [2,2,2] ===> [2,2,3]

eg zipWith (*) [1,2,3] [2,2,2] ===> [2,4,6]

Wyobraźmy sobie suwaki w ubraniach. O to właśnie chodzi przy łączeniu dwóch strumieni. Działa to także dla nieskończonych strumieni (a dlaczego by nie?).

fizzbuzz = zipWith (++) threes fives

(++) to konkatenacja łańcuchów, potem po prostu pokazujemy listę wierszy na ekranie. Naciskamy ^C, gdy nam się znudzi.

main = putStr (unlines fizzbuzz)

Jeśli chcemy, aby zamiast spacji między Fizz a Buzz wyświetlały się liczby, możemy dołączyć do suwaka kolejną listę, która zawiera liczby od 1 do nieskończoności, a potem dodawać liczbę, w miejscach, w których łańcuch inaczej byłby pusty.

Jest to więc krótki fragment kodu, który niewątpliwie działa, złożony z małych kawałków i sklejony razem w prosty sposób (pomyślmy o potokach Uniksa), przy czym nie musimy się martwić o pętle, podziały, zmienne, ograniczenie pamięci.

To nie jest jednorazowa sztuczka. Programowanie w języku Haskell tak właśnie wygląda.