poniedziałek, 5 listopada 2012

Listy w Scali

Ostatnimi czasy biorę intensywnie udział w kursie programowania funkcyjnego w Scali na portalu Coursera.org. Generalnie kiedyś się zraziłem do tego języka, gdyż jakiś tutorial i aktualnie używana przeze mnie wersja środowiska, powodowała, że przekopiowane przykłady nie działały. Teraz jest już trochę lepiej, aczkolwiek IDE do Scali dalej kuleją.

Na sam kurs zapisałem się zachęcony przez kolegę z pracy – fana Scali. Pomyślałem, że skoro nie będę robił tego sam, a będzie wsparcie w razie czego, to warto się zaangażować. I rzeczywiście jeszcze kilka znajomych robi ten kurs. Ostatnio nawet organizuję cykliczne spotkania w pracy, podczas których prezentujemy i porównujemy nasz kod. Oczywiście omawiamy stare zadania, które są już po deadline, aby nie łamać Honor Code. Jeśli macie taką możliwość, to zachęcam do organizowania podobnych aktywności u siebie.

Czy uczestnictwo w takim kursie coś daje? Nawet jeśli Scala nie trafi do powszechnego użytku, to na pewno uczestnictwo w kursie pomaga w zrozumieniu paradygmatu funkcyjnego i wynikającego z niego konsekwencji. Horyzonty się poszerzają, co ostatnio pomogło mi w lepszym zrozumieniu Java Scripta na darmowym kursie we Wrocławiu. Więcej o tym szkoleniu w innym wpisie.

Dla mnie wielką satysfakcją jest moment, kiedy dostaję olśnienia i nagle całkiem odmiennie patrzę na coś, co używam na co dzień. Podczas tego kursu był już taki moment, podczas rozwiązywania zadań z drugiego tygodnia. Należało wówczas zaimplementować zbiór (Set). Zadanie niby proste, ale nie gdy w kodzie mamy coś takiego:
type Set = Int => Boolean 
Długo nie mogłem zrozumieć, o co chodzi. Czytałem wątki na forum kursu, szukałem w Necie... W końcu zrozumiałem, że w tym przypadku Set został zdefiniowany, jako funkcja przyjmująca wartość liczbową, a zwracająca informację, czy dana liczba należy do zbioru, czy nie. Całkiem odmienne spojrzenie, na coś co zawsze było pudełkiem przechowującym elementy. Jak widać, można inaczej. Co prawda sprawia to parę problemów (możliwy zakres elementów), ale wyjście po za tą ramę było dla mnie niesamowite.

Dobra, koniec tych przemyśleń, czas na konkrety. Listy towarzyszą uczestnikom kursu już od samego początku. Zostały one jednak dokładniej przedstawione, dopiero podczas piątego tygodnia.

Listy w Scali są niezmienne. Co prawda istnieje alternatywna implementacja: MutableList, ale chodzi o to aby używać niezmienników. Wiadomo dlaczego. Nie oznacza to jednak, że jak wrzucimy element do listy (a ściślej mówiąc stworzymy listę zawierającą dany element), to nie możemy zmienić stanu tegoż obiektu. Owszem możemy. W Javie było by to tak:
class Person {
    private final String name;
    public int variable = 0;

    public Person(String name, int variable) {
        this.name = name;
        this.variable = variable;
    }

    public void change() {
        variable = variable + 42;
    }
}

public class Main {

    public static void main(String[] args) {
        List list = new ArrayList();
        list.add(new Person("Jan", 0));
        List immutableList = Collections.unmodifiableList(list);
        System.out.println(immutableList.get(0).variable);
        immutableList.get(0).change();
        System.out.println(immutableList.get(0).variable);
    }
} 

W Scali można analogicznie:
class Person(name: String, var variable: Int) {
  def change() {
    variable = variable + 42
  }
}

object Main {

  def main(args: Array[String]) {

    val person = new Person("name", 0)
    val list = List(person)
    println(list(0).variable)
    list(0).change()
    println(list(0).variable)
  }
} 

Tworzenie list w Skali mocno różni się od list w Javie. Z racji ich nie zmienności, musimy ich zwartość zdefiniować w momencie tworzenia.
val person = new Person("name", 0)
val list = List(person) 

Warto przy tej okazji zobaczyć, do czego będzie w tym momencie ewaluowane wywołanie List(person). Otóż List w Scali to:
  • abstakcyjna klasa List
  • objekt List
Klasa i objekt jednocześnie? Prawie. W Scali słówko kluczowe object oznacza definicję singletona. Po prostu ten wzorzec został wbudowany w język. Z praktycznego punktu widzenia, oznacza to, że możemy mieć tylko jedną instancję tegoż obiektu. Nie trzeba więc używać słówka new w tym przypadku.

Z drugiej strony, możemy przecież wywołać naszego singletona wielokrotnie z różnymi argumentami.
val list = List(person)
val list2 = List(person)
Jakby podejrzeć adresy w pamięci, to się okaże, że nie wskazują one tego samego miejsca. Co się więc dzieje? Jeśli chcemy skorzystać z dobrodziejstwa niepisania new, należy w naszym object’cie zdefiniować metodę apply() zwracającą żądaną instancję. Oczywiście metoda ta może przyjmować argumenty i zwraca żądaną instancję. Pełni wiec to bardziej rolę Fabryki niż singletonu. Jak to jest zdefiniowane dla listy? a no tak:
override def apply[A](xs: A*): List[A] = xs.toList 
Czyli na naszych argumentach (typu WrappedArray) zostanie wywołana metoda toList() i zadnie będzie gdzieś tam daleko delegowane...

No dobra, a jakiego typu listę otrzymamy? Patrząc na List.scala to można zobaczyć, że są dwie klasy rozszerzające tą Listę:
  • case object Nil extends List[Nothing]
  • final case class ::[B](...) extends List[B]

Pierwsza konkretna implementacja to element końcowy listy, za którym nic już nie ma. Natomiast dwukropek dwukropek, to nazwa klasy! Trochę się zszokowałem, gdy to zobaczyłem – rozumiem nazwać tak metodę, ale klasę? Jak widać można. Klasa ta tak naprawdę skleja głowę z ogonem. Implementacja jest bardzo prosta:
final case class ::[B](private var hd: B, private[scala] var tl: List[B]) extends List[B] {
  override def head : B = hd
  override def tail : List[B] = tl
  override def isEmpty: Boolean = false 

A samego operatora używamy zazwyczaj w bardziej czytelnej formie
val person = new Person("name", 0)
val person2 = new Person("name2", 0)
val list = List(person2)
val list2 = person :: list 

A jak za pomocą :: utworzyć jednoelementową listę? Należy skorzystać ze wspomnianego już Nil’a:
val list3 = person :: Nil 
Analogicznie jak :: działa +: Ten drugi operator (a właściwie metoda) dodatkowo tworzy kopię bazowej listy. Możemy również dodawać elementy na końcu listy, ale raczej nie jest to optymalne. W tym celu używamy :+. Przykład:
scala> val text = List("Ala", "ma")
text: List[java.lang.String] = List(Ala, ma)

scala> val text2 = text :+ "kota"
text2: List[java.lang.String] = List(Ala, ma, kota) 

Można również sklejać listy. Do tego używamy potrójnego dwukropka ::: Przykład:
scala> val numbers = List(4, 6, -3, 1)
numbers: List[Int] = List(4, 6, -3, 1)

scala> val numbers2 = List(2, 3)
numbers2: List[Int] = List(2, 3)

scala> val numbers3 = numbers2 ::: numbers
numbers3: List[Int] = List(2, 3, 4, 6, -3, 1) 

Operator ten dokleja nowe elementy na początku istniejącej listy. Podobnie działa dwuplus ++, który dodatkowo tworzy kopię Listy:
scala> val numbers4 = numbers2 ++ numbers
numbers4: List[Int] = List(2, 3, 4, 6, -3, 1) 

Nie wiem jak by to można było na przykładzie przedstawić (a debugować mi się nie chce), po prostu musimy ufać dokumentacji.

Uff przebrnęliśmy szczęśliwie przez te ‘śmieszne’ operatory. Muszę przyznać, że dla początkującego adepta Scali, są te operatory trochę niejasne i mylące, dlatego warto poświęcić im chwilę. Istnieje jeszcze kilka metod produkujących listy:
xs.reverse - zwraca odwróconą listę
xs updated (n, x) - zwraca listę zawierającą to samo co xs, ale w miejscu o indeksie n wstawia x’a
xs.toList – metoda dostępna w wielu innych typach

Co jeszcze ciekawego mamy w listach w Scali?

Mamy 3 fundamentalne operacje:
head – zwraca pierwszy element
tail – zwraca wszystko poza pierwszym elementem
isEmpty – zwraca true dla :: i false dla Nil

Ponadto lista zawiera sporo innych już mniej wydajnych operacji (last, init, take…), jak i takie które znamy dobrze z Javy (contains, indexOf…).

Scala udostępnia nam trochę więcej operacji na listach, niż mamy to w czystej Javie. I tak na przykład przekształcenie listy w listę zawierającą inne elementy. W Javie zazwyczaj piszemy petlę:
List<String> names = new ArrayList<String>();
for (Person person : persons) {
    names.add(person.getName());
} 

W Scali można to wykonać prościej za pomocą map():
val names = persons map (p => p.getName) 

Czyli dla każdego elementu p z listy persons wywołaj getName i zwróć to wszystko opakowane w listę i zapisz w names. Czy jest to czytelniejsze? Jak się pamięta co robi metoda map() i jeśli jest się w stanie sobie wyobrazić co oznacza p, to tak. O ile jak czytam własny kod to jestem w stanie przeanalizować co się dzieje, ale jak bym miał to zrobić z czyimś kodem, to bym się pewnie musiał dłużej zastanawiać, o co kaman.

Tą, jakże krótką i zwięzłą definicję, można jeszcze zapisać na kilka sposobów:
val names = persons map (p => p getName)
val names = persons map (_.getName)
val names = persons map (_ getName) 

Następną przydatną operacją jest filtrowanie, czyli pobranie podzbioru listy. W Javie to by było jakoś tak:
List<Person> personsStartsWithJ = new ArrayList<Person>();
for (Person person : persons) {
    if(person.getName().startsWith("J")) {
        personsStartsWithJ.add(person);
    }
} 

W Scali można to zapisać na jeden ze sposobów:
val personsStartsWithJ = persons filter(p => p.getName.startsWith("J"))
val personsStartsWithJ = persons filter(_.getName.startsWith("J")) 

Dodatkowo mamy metodę filterNot(), która zwraca elementy niespełniające podanego warunku. Można również wykonać te dwie operacje (filter i filterNot) jednocześnie:
val personsPart = persons partition(_.getName.startsWith("J"))
println(personsPart._1)
println(personsPart._2) 

Przykładowy efekt działania:
List(Person(Jan))
List(Person(Stefan), Person(Emil), Person(Dominik)) 

Czyli bardzo sensowne użycie tuple’a, pomagające zwrócić dwa wyniki z metody. Nie kojarzę żadnych standarowych metod z Javy zwracających dwa wyniki. Tak wiem że SRP, ale jak akurat potrzebujemy obydwie listy, to dwukrotna iteracja może rzutować na performance. W Javie trzeba to na piechotę robić:
List<Person> personsStartsWithJ = new ArrayList<Person>();
List<Person> personsNotStartsWithJ = new ArrayList<Person>();
for (Person person : persons) {
    if(person.getName().startsWith("J")) {
        personsStartsWithJ.add(person);
    } else {
        personsNotStartsWithJ.add(person);
    }
} 

To na razie chyba tyle co chciałem przedstawić, zapisać, zapamiętać i podzielić się tym z Wami na temat Scali. Czas wrócić do oglądania kolejnych wykładów...

6 komentarzy:

  1. Rzeczywiście, techniki programowania funkcyjnego warte są poznania, nawet, jeśli pozostaniemy w świecie imperatywno/obiektowym. Polecam klasyczne lektury, takie jak Structure and Interpretation of Computer Programs, która w USA jest bazą wykształcenia informatycznego. Było polskie wydanie, obecnie trudno dostępne. Po angielsku dostępne w sieci. Bardzo poszerza horyzonty !

    OdpowiedzUsuń
    Odpowiedzi
    1. Czytałem fragmenty Structure and Interpretation of Computer Programs. Książka jest polecana w tym kursie i pomogła mi jedno ze wcześniejszych zadań rozwiązać. Postaram się do niej wrócić w międzyczasie.

      Usuń
  2. Z innej beczki, czy biorąc udział w takim kursie na Coursera (albo innym Audacity) można na tym skorzystać, jeśli robi się go samodzielnie? Rozumiem, że spotykacie się w grupie osób, która uczestniczy w kursie, i jakby co, to możecie wymienić się wątpliwościami albo wrażeniami. A czy w razie czego jest możliwość zadawania pytań prowadzącym taki kurs? Chcę rozpocząć inny na tej samej platformie, ale nie mając możliwości konfrontacji wrażeń w jakiejś większej grupie zastanawiam się czy to ma sens.

    OdpowiedzUsuń
    Odpowiedzi
    1. Oczywiście, że można skorzystać. Kurs ten bardzo motywuje do działania, bo są terminy, których należy się trzymać i jak się człowiek spóźnia, to dostaje mniej punktów. Na Courserze jest forum, gdzie można było zadawać pytania, na które odpowiadali między innymi osoby związane z prowadzącym (w tym przypadku studenci - wolontariusze). Dzięki temu udało mi się uzyskać opisywane "olśnienie". Najlpiej jakbyś jakiś znajomych namówił na kurs to i motywacja będzie większa. Jak nie, to zawsze pozostaje forum, blog, twitter i stackoverflow.

      Usuń
  3. Dzięki za odpowiedź. Takie forum to chyba idealne miejsce do pytań różnych, a jeśli odpowiadający są związani z prowadzącym, to znaczy, że jest to na normalnych warunkach amerykańskich. Świetne wieści, bo akurat zachęcić znajomych na zapisanie się na kurs "Introduction to Statistics" z prof. z Princeton może być problemem... :)

    OdpowiedzUsuń
    Odpowiedzi
    1. Co masz na myśli mówiąc o warunkach amaerykańskich? To dobrze, czy źle? Forum to forum, każdy może się wypowiadac, zarówno uczestnicy kursu, jak i jego organizatorzy, którzy wyjaśniają niejasne kwestie.

      Usuń