Elixir #08 – Listy i Rekurencja

Wczoraj było o tym czym jest rekurencja oraz na czym polega optymalizacja rekurencji ogonowej. Dziś popatrzmy na to z poziomu Elixir z kilku powodów:

1. Elixir jest językiem funkcyjnym
2. Zmienne są niezmienne/stałe, raz przypisane nie ulegną zmianie
3. Normalne pętle w Elixir nie istnieją
4. Wszystkie operacje na listach i te które mają zostać powtórzone są rekurencyjne

Na początku zacznijmy od list, bo to jest ciekawy byt, z którego będziemy dość często korzystać.

Listy

Lista to nie jest to samo co lista w C#, bardziej bym powiedział, że lista w Elixir to linked list (po pl lista jednokierunkowa). Czyli, zapis:

[1, 2, 3, 4, 5]

Jest dzielony na head i tail. head to pierwsza wartość, tail, to cała raszta. Z Patter Matching wiemy, że możemy to wyciągnąć dzięki wzorcowi [head | tail]:

[head | tail] = [1, 2, 3, 4,5]
> head: 1
> tail: [2, 3, 4, 5]

Albo za pomocą funkcji wbudowanych hd i tl:

list = [1, 2, 3, 4, 5]

# get head
hd(list)

# get tail
tl(list)

Możemy też trochę powariować ze wzorcami jak chcemy:

[head1 | [head2 | [head3 | [head4 | [ head5 | tail]]]]] = [1,2,3,4,5]

Gdzie tail będzie równy pustej liście ([]).

Czyli ogólnie zapis naszej listy z początku, jest równoważny zapisowi:

[1 | [2 | [3 | [4 | [5 | [ ] ] ] ] ] ]

Posiadanie list jako listy jednokierunkowej daje nam liniową złożoność w przechodzeniu przez listę jak i wykonywaniu jakichkolwiek operacji na liście. To znaczy, jak chcemy dostać się do 5 elementu, musimy przejść przez wszystkie 4 wcześniejsze. Aktualizacja zaś listy jest tylko wtedy wydajna kiedy dodajemy element na jej początek:

[0 | list]

Jeżeli zaś próbujemy dodać element na koniec, to już nie będzie to takie proste. Gdyż by go dodać na koniec, musielibyśmy przejść przez wszystkie elementy. Zapis:

[list | 0]

Nie zrobi tego co możemy przypuszczać, że powinno się stać. Wręcz przeciwnie da nam to coś dziwnego. Byt który jest listą: is_list zwróci true, ale którego do listy zakwalifikować się nie da (jest to tak zwana improper list). Już lepszym (i poprawnym) zapisem będzie:

[list | [0]]

To spowoduje, że head będzie miał wartość całej naszej poprzedniej listy, zaś tail będzie 0:

[[1, 2, 3, 4, 5], 0]

A raczej chcielibyśmy uzyskać wynik:

[1, 2, 3, 4, 5, 0]

Niestety, to nie takie łatwe :)

Dobra, to tyle na temat list, wiemy mniej więcej jak są reprezentowane, na jakiej zasadzie one działają. Możemy już w domyślić się, z czym możemy mieć problemy. Do niektórych z nich dojedziemy pewnie kolejnej sekcji.

Rekurencja

Elixir ma taką metodę length – ma on na celu zwrócenie liczby elementów w tablicy. Im większa tablica tym dłużej zwrócenie wartości będzie trwało. Zróbmy jednak sobie mały test, załóżmy, że funkcja length nie istnieje. Że twróca Elixir miał jakieś otępienie i stwierdził, że NIGDY ale to PRZENIGDY nie będziemy mieć konieczności zliczania elementów. Okazało się też, że się sromotnie pomylił bo właśnie jest nam ona teraz potrzebna. Macie pomysł jak to zrobić?

W C# byśmy pewnie zrobili pętle foreach albo while. for odpada, bo byśmy musieli znać jej długość. Dla przykładu, w C# byśmy to tak rozwiązali (jedna w wielu dróg, bez extension methods):

var x = new List<int> { 1, 2, 3, 4};

var i = 0;

foreach(var z in x) { i++; }

Prosto i prawie zgrabnie. Niestety, w Elixir nie mamy pętli. Ok istnieje for ale to nie o to chodzi. Do tego Elixir jest językiem którego wartości nie ulegają zmianie. A to znaczy, że nie możemy sobie dodawać i++. A więc jak to możemy rozwiązać?

Za pomocą rekurencji i akumulatora:

defmodule ListLen do
  # empty list case
  def len([]), do: 0
  def len([], acc), do: acc

  def len([_|tail]), do: len(tail, 1)
  def len([_ | tail], acc) do
    len(tail, acc + 1)
  end
end

Jak widać nie jest to takie proste. Trzeba obsłużyć sytuacje kiedy podajemy pustą listę ([]), kiedy nasza rekurencja uderza w pusty tail, jak i dać miejsca wejścia bez podawania accumulatora. Ten akumulator zaś jest niezbędny do tego by w ogóle cokolwiek policzyć. A wszystko przez naturę niezmienności języka.

Czasami jednak należy posłużyć się pewnym trickiem by sobie życie ułatwić. Dla przykładu jak można wstawić element na koniec listy? Można wykorzystać na przykład operator łączenia list ++:

[1,2,3] ++ [4,5]

Jednak to powoduje wywołanie funkcje Kernel.++/2, która z zapisu Erlang w zapisie Elixir wygląda następująco:

def append([head | tail], newTail), do: [ head | append(tail, newTail)]

def append([], newTail), do: newTail

Więc nie jest to takie dobre. Przechodzimy przez wszystkie elementy i tak naprawdę tworzymy nową listę od podstaw na bazie istniejącej. Zamiast tego, możemy trzymać odwrotną kolejność elementów i odwracać ją kiedy jest nam to potrzebne.

list = [0 | list ]
list = [1 | list ]

Enum.reverse(list)

Dzięki czemu wkładanie zawsze mamy szybkie, jedynie przechodzenie po wszystkich elementach będzie miał narzut czasowy. Jeszcze jedno, to nie jest tak, że my cały czas zmieniamy wartość list. Nie, my tylko bindujemy aktualną wartość do aliasu zwanego list. To nie jest to samo co przypisanie i nadpisanie wartości w pamięci. Raczej list wskazuje teraz na inną przestrzeń pamięci. Koniec.

No dobra, to do czego rekurencja nam się przydaje w elixir? No, nie licząc, że do wszystkiego ;) to wtedy kiedy:

• Chcemy wykonać coś w pętli – skończonej lub nie (pamiętajcie, że rekurencja ogonowa tutaj może działać i działać w nieskończoność, coś w stylu while(true)).
• Chcemy przeanalizować listę i zwrócić jakąś wartość – na przykład sumowanie, średnia, zliczanie.
• Chcemy zamienić listę A na listę B, albo inaczej mówiac z mapować.

Teraz, istniej taki moduł jak Enum w elixir, który nam te sprawy ogólnie załatwia – daje możliwość wprowadzenia lambdy itp. Jednak czasami – nawet dość często, chcemy by nasz kod wyglądał pięknie (no ja lubię). Wtedy odwołania do Enum nie koniecznie będą pasować. Zaś będziemy wstanie pewne rzeczy wyciągnąć przed nawias. Albo po prostu nasze mapowanie lub analiza będzie na tyle skomplikowana, że łatwiej ją będzie napisać jako moduł z rekurencją niż jako lambda. Ciekawy i fajny przykład rozbicia brzydkiej metody na ładną z rekurencją można znaleźć u Roba na blogu.

Ale, by pokazać jeszcze jedną fajną rzecz w elixir o której nie wspominałem a idealnie się nadaje do rekurencji :) Wczoraj było tyle o Fibonacci, że aż weźcie i zróbice sobie na komputerze fib od 92. Powinniście dostać 7540113804746346429. A teraz zróbcie to dla 93… ;) no właśnie, potrzebujemy innego typu danych ;)

A teraz sprawdźcie sobie to dla:

defmodule Fib do

  def fib(n) do
    fib(n, 1, 0)
  end

  defp fib(0, _, result), do: result

  defp fib(n, next, result), do: fib(n - 1, next + result, next)

end

:) fajnie nie? :) dlatego też tak ważne tutaj jest rekurencji i jej optymalizacja ogonowa.

Podsumowanie

Zaczynam chyba mieć podstawy opanowane. Widzę, że zaczyna mi brakować wiedzy na temat API. Jeszcze są dwa może trzy tematy które chciałbym poruszyć zanim wejdę w pisanie aplikacji. Przynajmniej na razie są to dwa, trzy tematy. To może ulec zmianie. Ale dzisiaj zamknęliśmy bardzo ważny rozdział w elixir, dzięki czemu wiemy:

• Listy w elixir są jednokierunkowe
• Dane są niezmienne
• Rekurencja jest wykorzystywana nawet do najprostszych zadań typu pętla
• Elixir wykorzystuje bignum – więc good luck w szkukaniu maxa :)

Sądzę, że to dość sporo jak na jeden raz. Dużo różnych aspektów było poruszanych. Część z nich można zagłębić bardziej – do czego zachęcam. A tym czasem, do przeczytania o elixir za tydzień :)