Списъци и потоци

от valo

Публикувано четвъртък, 30 март 2017, 00:29

Един от най-често ползваните типове в Еликсир е списъкът и затова е важно да можем да работим ефективно с него. В езика има доста инструменти за работа със списъци и потоци (списъци, които се генерират при поискване) и е много важно да знаем как да работим ефективно с тях. Нека да видим как става това.

Head & tail на списъци

Един списък може да се представи рекурсивно като главата на списъка (head), в която е стойността на първия му елемент и указател към следващия елемент. Така можете да си представите списъците като кутийки, в които има стойност и всяка кутийка е свързана към следващия елемент в списъка. Единствено последният елемент няма връзка към следващ елемент:

+-+-+   +-+-+   +-+-+   +-+-+   +-+-+   
|1| |-->|2| |-->|3| |-->|4| |-->|5| |
+-+-+   +-+-+   +-+-+   +-+-+   +-+-+

Това е списъкът [1,2,3,4,5] и както се вижда главата му съдържа 1 и сочи към следващият елемент, който съдържа 2 и има указател към следващият елемент, който е 3 и т.н. Само последният елемент, който съдържа 5, няма указател към следващ елемент, т.е. това е краят на списъка.

В Еликсир подобна зависимост може да се запише така:

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

Тук използваме специален оператор - | за да опишем каква е стойността на елемента и какъв е остатъкът от списъка, т.е. горният ред казва: главата на списъка съдържа 1 и сочи към остатъка на списъка: [2 | [3 | [4 | [5 | []]]]], който е списък с глава, която съдържа 2 и сочи към остатъка на списъка: [3 | [4 | [5 | []]]] и т.н. Последният елемент е [5 | []], който съдържа 5 и сочи към остатък, който е празен списък, което маркира края на данните.

Друг начин за да се опише горната структура е: [head | tail], където head е стойността на главата на списъка, а tail е остатъка. Това е и синтаксиса, ако искаме да pattern match-ваме списъци:

[a | b] = [1,2,3]
IO.puts a # 1
IO.puts inspect(b) # [2, 3]

Горното няма да работи ако списъкът е празен:

[a | b] = [] # ** (MatchError) no match of right hand side value: []

Рекурсивно обхождане на списък

Горната дефиниция ни дава възможност да пишем функции, които работят със списъци. Нека например напишем функция, която връща дължината на списък:

defmodule ListUtils do
  def length([]), do: 0
  def length([_head | tail]), do: 1 + length(tail)
end

Имаме 2 дефиниции:

  • Когато списъкът е празен, знаем че неговата дължина е 0.
  • Ако списъкът не е празен, то можем да го разделим на глава и остатък и дължината му ще бъде 1 + дължината на остатъка.

Например ако извикаме горната функция за един списък, то операциите които ще се извършат са:

ListUtils.length(["cat", "dog", "fish", "horse"])
= 1 + ListUtils.length(["dog", "fish", "horse"])
= 1 + 1 + ListUtils.length(["fish", "horse"])
= 1 + 1 + 1 + ListUtils.length(["horse"])
= 1 + 1 + 1 + 1 + ListUtils.length([])
= 1 + 1 + 1 + 1 + 0
= 4

Както виждаме много елегантно успяваме да дефинираме рекурсивно обработката на списъка, като различаваме 2 случая - когато списъкът е празен и когато не е. Това е много често използван шаблон при обработването на списъци.

Рекурсивно изграждане на списък

Аналогично можем и рекурсивно да изграждаме списъци, като ги дефинираме като “глава” и “остатък”:

a = [2,3]
b = [1 | a] # => [1, 2, 3]
c = [1 | []] # => [1]

Нека напишем функция, която повдига всички елементи от един списък на квадрат:

defmodule Square do
  def of([]), do: []
  def of([head | tail]), do: [head * head | of(tail)]
end

Square.of([1,2,3,4,5]) # => [1,4,9,16,25]

Логиката е следната:

  • Списъкът на квадрати на празен списък е празен списък.
  • Списъкът на квадрати на не-празен списък е списъка от квадрата на първия елемент и списъка от квадрати на остатъка.

Така рекурсивно можем да изграждаме списъци от други списъци.

Може би сами се досещате, че ако имаме един списък и направим два нови списъка, използвайки първия за остатък, то ние ще преизползваме паметта на основния списък:

а = [1,2,3,4,5,6]
b = [0 | a]
c = [-1 | a]

Вътрешно при представянето на b и на c не се прави копие на a, a се използва указател към a, което е много ефективно от към памет, но има trade-off-а, че за да остановим дължината на списъка, то трябва да го обходим.

В този контекст, винаги се опитвайте да добавяте елементи към началото на един списък, тъй като така не се създават копия на списъка. Например не правете така:

defmodule Fib do
  def bad_of(n) do
    bad_fib(n, 0, 1, [])
  end

  defp bad_fib(0, _current, _next, seq), do: seq

  defp bad_fib(n, current, next, seq) do
    bad_fib(n - 1, next, current + next, seq ++ [current])
  end
end

При горната имплементация ще се генерира копие на списъка seq когато се направи seq + [current]. Това се дължи на неизменимоста на данните в Еликсир и тъй като няма как да променим последният елемент на списъка да сочи към нов елемент, се налага да се направи копие на списъка. По-оптимиалният вариант е следния:

defmodule Fib do
  def of(n) do
    fib(n, 0, 1, [])
  end

  defp fib(0, _current, _next, seq), do: seq |> Enum.reverse

  defp fib(n, current, next, seq) do
    fib(n - 1, next, current + next, [current | seq])
  end
end

Тук няма да имаме нито едно копиране докато изграждаме списъка и накрая просто се налага да го обърнем.

Имплементация на map

Нека да видим как бихме имплементирали стандартния за функционалните езици map, използвайки горните похвати. Нека припомним, че map е функция, която приема списък и функция с един аргумент и връща нов списък с резултата от извикването на функцията върху всеки елемент от списъка:

defmodule ListUtils do
  def map([], _func), do: []
  def map([head | tail], func), do: [func.(head) | map(tail, func)]
end

ListUtils.map([1,2,3,4,5], fn x -> x * x end) # => [1,4,9,16,25]

Както виждате горната функция е обобщение на това, което направихме по-горе при рекурсивното изграждане на списъците. Затова и тази операция е стандартна във функционалното програмиране и е включена в стандартната библиотека чрез функцията Enum.map/2.

Имплементация на reduce

Друга интересна операция и обобщение на това което правихме при смятането на дължината на списъка е reduce. Това е функция, която приема списък, начална стойност - акумулатор и функция и извиква функцията с аргументи акумулатора и всеки елемент от списъка. Функцията трябва да върне новата стойност на акумулатора:

defmodule ListUtils do
  def reduce([], acc, _func), do: acc
  def reduce([head | tail], acc, func), do: reduce(tail, func.(head, acc), func)
end

ListUtils.reduce(["cat", "dog", "horse"], 0, fn _head, acc -> 1 + acc end) # => 3

Това което ще се случи при горното извикване е следното:

add_one = fn _head, acc -> 1 + acc end
ListUtils.reduce(["cat", "dog", "horse"], 0, add_one)
= ListUtils.reduce(["dog", "horse"], 1, add_one)
= ListUtils.reduce(["horse"], 2, add_one)
= ListUtils.reduce([], 3, add_one)
= 3

Интересното е, че всичко това са стандартни примери за код където имаме нужда от някакъв променящ се state и за да избегнем писането на цикли използваме рекурсия. Приемуществото на рекурсията, е че имаме много добра дефиниция кое е състоянието, което се прехвърля межу отделните итерации - аргументите на функцията. Няма как да използваме състояние (state), което е извън тези аргументи. Това прави кода ни по-четим, по-модулен и по-лесен за промяна.

Операцията reduce, също както map, е основна при работата със списъци в един функнционален език и затова е включена в стандартната библиотека под името Enum.reduce и също Enumerable протоколът реално изисква да бъде имплементирана единствено функцията reduce за една структура за да може всички функции от Enum модула да се използват с нея. Повече информация на https://hexdocs.pm/elixir/Enum.html#reduce/3 и https://hexdocs.pm/elixir/Enumerable.html.

Сложни шаблони със списъци

Понякога ни се налага да работим със по-сложни структури от списъци, като например списъци от кортежи или списъци от map-ове или списъци от списъци. Elixir поддържа вложени шаблони, което ни позволява да пишем сложни логики по много експресивен начин. Например, нека имаме списък от измервания на метерологични станции. Всяко измерване е списък със следните елементи [temperature_in_c, pressure_in_hpa, wind_direction]. Как бихме написали функция, която обръща температурата от целзии във фаренхайт:

defmodule Meteo do
  def to_fahrenheit([]), do: []
  def to_fahrenheit([[temperature_in_c, pressure_in_hpa, wind_direction] | tail]) do
    [
      [celcius_to_fahrenheit(temperature_in_c), pressure_in_hpa, wind_direction] |
      to_fahrenheit(tail)
    ]
  end

  defp celcius_to_fahrenheit(celcius) do
    celcius * 1.8 + 32
  end
end

Meteo.to_fahrenheit([[0, 1013, "SE"], [15, 1010, "N"], [-5, 10115, "NW"]])
# => [[32.0, 1013, "SE"], [59, 1010, "N"], [23.0, 10115, "NW"]]

Аналогично ако променим структурата на Map, може да напишем горната логика така:

defmodule Meteo do
  def to_fahrenheit([]), do: []
  def to_fahrenheit([%{temperature: temp} = head | tail]) do
    [
      %{head | temperature: celcius_to_fahrenheit(temp)} |
      to_fahrenheit(tail)
    ]
  end

  defp celcius_to_fahrenheit(celcius) do
    celcius * 1.8 + 32
  end
end

Meteo.to_fahrenheit([
  %{temperature: 0, pressure: 1013, wind: "SE"},
  %{temperature: 15, pressure: 1010, wind: "N"},
  %{temperature: -5, pressure: 1015, wind: "NW"}
])
# => [%{pressure: 1013, temperature: 32.0, wind: "SE"},
#     %{pressure: 1010, temperature: 59.0, wind: "N"},
#     %{pressure: 1015, temperature: 23.0, wind: "NW"}]

Горният пример е особенно красив, тъй като можете да видите как обработваме всеки елемент от Map-а, като изваждаме стойностите, които ни трябват още при дефинирането на аргументите. Така ще си осигурим, че ако някой ни подаде невалидни данни, то програмата ни ще хвърли грешка веднага, щом стигне до невалидните данни:

Meteo.to_fahrenheit([
  %{temperature: 0, pressure: 1013, wind: "SE"},
  %{pressure: 1010, wind: "N"},
  %{temperature: -5, pressure: 1015, wind: "NW"}
])
# ** (FunctionClauseError) no function clause matching in Meteo.to_fahrenheit/1
#     iex:63: Meteo.to_fahrenheit([%{pressure: 1010, wind: "N"}, %{pressure: 1015, temperature: -5, wind: "NW"}])
#     iex:67: Meteo.to_fahrenheit/1

Както можете да видите от горната грешка, дори можем да разберем какви точно са грешните данни.

Модула Enum

В стандартната библиотека на Elixir има модул, който е предназначен за работа с колекции (типове, които могат да се обхождат и по-формално казано: имплементират Enumerable протокола). Това ще е един от модулите, които ще използвате най-много, така че можете да разгледате неговата документация: https://hexdocs.pm/elixir/Enum.html.

Нека разгледаме няколко примера. Ето как бихме повдигнали колекция от числа на квадрат:

Enum.map([1,2,3,4,5], fn x -> x * x end) # => [1, 4, 9, 16, 25]

Ето как бихме могли да преброим броя елементи в един списък чрез Enum.reduce, което е копие на това което имплементирахме по-горе:

Enum.reduce(["cat", "dog", "horse"], 0, fn _head, acc -> 1 + acc end) # => 3

Има още много функции в този модул, така че разгледайте документацията. Ще намерите много полезни неща там.

Comprehensions

Elixir предоставя съкратен синтаксис за извършване на map и filter върху колекция, тъй като много често се налага да се използват тези операции. Например ако искаме да повдигнем елементите на една колекция на квадрат и да филтрираме резултата можем да направим следното:

[1,2,3,4,5]
|> Enum.filter(fn x -> x < 4 end)
|> Enum.map(fn x -> x * x end)
# => [1, 4, 9]

Горният пример може да се имплементира така:

for x <- [1,2,3,4,5], x < 4, do: x * x
# => [1, 4, 9]

Можем да имаме по няколко генератора за един comprehension:

for x <- [1,2], y <- [3,4], do: {x, y}
# => [{1, 3}, {1, 4}, {2, 3}, {2, 4}]

Както виждате блокът в дясно ще се изпълни за всяка една двойка или формално казано - с декартовото произведение на двете колекции.

В примерите до сега comprehension-ите връщат колекцията след като се изпълни филтъра и после map-а. Това може да се промени със параметъра into, където можем да подадем нещо което имплементира Collectable протокола, в което ще се съхрани резултата от comprehension-а. Например можем да изградим Map:

for x <- ~w{ cat dog elephant mammut }, into: %{}, do: {x, String.length(x)}
# => %{"cat" => 3, "dog" => 3, "elephant" => 8, "mammut" => 6}

Можем да подадем съществуваща структура и тя ще бъде допълнена:

for x <- ~w{ cat dog elephant mammut }, into: %{"fish" => 4}, do: {x, String.length(x)}
# => %{"cat" => 3, "dog" => 3, "elephant" => 8, "fish" => 4, "mammut" => 6}

Потоци

Ако погледнете документацията на модула Stream ще видите, че той съдържа много подобни функции като модула Enum. Реално потоците са enumerables, които се генерират при поискване (така наречените lazy enumerables). Например, ако изпълним този код:

1..10_000_000
|> Enum.map(&(&1 + 1))
|> Enum.take(5)
# => [2, 3, 4, 5, 6]

Той ще отнеме няколко секунди да се изпълни, тъй като първо ще се изчисли целия Enum.map върху 10 милиона числа и после ще се вземат първите 5 от тях. Много по-ефективна имплементация би била:

1..10_000_000
|> Stream.map(&(&1 + 1))
|> Enum.take(5)
# => [2, 3, 4, 5, 6]

Ако тествате горния пример ще видите, че той се изпълнява мигновенно. Това е защото Stream.map, няма да обработи цялата колекция от 10 милиона числа, а ще върне “поток”, от който можем да вземаме числа и той ще извършва сметките когато поискаме число. Това което прави потоците изключително мощни, е че можем да ги компизираме и така да описваме последователност от операции, като те ще се изпълнят така, че да не зареждаме цялата колекция в паметта, а обработваме елементите един по един при поискване.

Друг пример е при работата с файлове. Ако например искаме да намерим най-дългата линия в един файл, един от начините е да направим следният:

File.read!("binaries.md") # Прочитаме файла
|> String.split("\n") # Превръщаме го във списък от редове
|> Enum.max_by(&String.length/1) # Намираме най-дългият ред

Това би било много неефективно ако файлът е голям, защото първо ще прочете целият файл в паметта, после ще генерира много дълъг списък от редовете във файла. По-ефективно би било да се ползват потоци:

File.open!("binaries.md", [:utf8]) # Отваряме файла
|> IO.stream(:line) # Създаваме поток от редовете му
|> Enum.max_by(&String.length/1) # Намираме най-дългият ред

Така файлът ще се обработва ред по ред, вместо да се чете целият в паметта. За горния пример има и съкратена версия:

File.stream!("binaries.md")
|> Enum.max_by(&String.length/1)

Ето един друг пример където искаме да преброим броят думи в голям файл, в случая английският превод на Война и Мир, който е 3.2МБ текстов файл:

defmodule WarAndPiece do
  def number_of_words_with_enum do
    # Можете да свалите файла със:
    # curl http://www.gutenberg.org/files/2600/2600-0.txt > war_and_piece.txt
    File.read!("war_and_piece.txt")
    |> String.split
    |> length
  end

  def number_of_words_with_stream do
    File.stream!("war_and_piece.txt")
    |> Stream.flat_map(&String.split/1)
    |> Enum.reduce(0, fn _, acc -> acc + 1 end)
  end
end

:timer.tc(WarAndPiece, :number_of_words_with_enum, [])
# => {1561933, 566309}
:timer.tc(WarAndPiece, :number_of_words_with_stream, [])
# => {833594, 566309}

Както виждате успяваме да свалим времето за изпълнение на половина само чрез използването на поток, вместо да четем и обработваме всички данни в паметта. Потоците са мощен инструмент, който трябва да можем да използваме. В повечето случай можем да обработваме данните си като колекции, но има случаи където потоците са по-удачни.

Безкрайни потоци

Нещо, което е уникално за потоците е че те могат да са безкрайни. Видяхме, че потоците връщат стойности само при поискване (lazy enumerables) и това прави възможно да създаваме потоци, които връщат безкраен брой елементи. Например можем да генерираме безкрайна редица от единици:

Stream.cycle([1])
|> Enum.take(10)
# => [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Можем да използваме функцията Stream.unfold за да генерираме поток, в който всяка следваща стойност зависи от предната. Например, можем да направим поток, който генерира безкрайната редица на Фибоначи:

Stream.unfold({0, 1}, fn {a, b} -> {a, {b, a + b}} end) |> Enum.take(10)
# => [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Stream.cycle може да е много полезен ако генерирате HTML и искате да направите редове на таблица, които да имат алтерниращи класове:

defmodule RenderTable do
  def render(list) do
    [
      "<table>\n",
      "  <tr>\n",
      "    <th>Items</th>\n",
      "  </tr>\n",
      render_list(list),
      "</table>"
    ]
  end

  defp render_list(list) do
    Stream.cycle(["odd", "even"])
    |> Enum.zip(list)
    |> Enum.map(&render_item/1)
  end

  defp render_item({class, item}) do
    [
      "<tr>\n",
      "  <td class=\"", class, "\">\n",
      "    ", item, "\n",
      "  </td>\n",
      "</tr>\n"
    ]
  end
end

IO.puts RenderTable.render(~w/milk butter bread/)
# <table>
#   <tr>
#     <th>Items</th>
#   </tr>
# <tr>
#   <td class="odd">
#     milk
#   </td>
# </tr>
# <tr>
#   <td class="even">
#     butter
#   </td>
# </tr>
# <tr>
#   <td class="odd">
#     bread
#   </td>
# </tr>
# </table>

Обърнете внимание как вместо да правим интерполация на низовете, генерираме списъци от низове. Това намалява копирането на памет, което виртуалната машина трябва да направи и прави генерирането на HTML-а ни по-бързо. Това е широко използвана техника във Phoenix Framework и дори има специално име: IOList. Интересна продробност, е че IOList може да съдържа и вложени списъци и няма нужда да се прави flatten ако рекурсивно генерираме данните, които трябва да се отпечатаме или изпратиме по сокет. Повече информация можете да прочетете тук. Друга интересна статия по темите IOList, потоци и ефективност (има сравнение с Ruby), може да проетете тук.

Безкрайните потоци могат да се използват и за други неща, като например да дефинираме ресурси с тях. Ресурсите имат 3 фази:

  • Инициализация
  • Генериране
  • Почистване

Така например ако искаме да прочетем един файл, то трябва да го отворим, да прочетем всички данни от него и накрая да го затворим. Рагледайте документацията на Stream.resource за повече подробности и пример: https://hexdocs.pm/elixir/Stream.html#resource/3.

Категоризирано като Програма
Маркирано като elixir, lists, streams