{"id":555,"date":"2011-04-22T11:55:51","date_gmt":"2011-04-22T10:55:51","guid":{"rendered":"http:\/\/trigonakis.com\/blog\/?p=555"},"modified":"2011-04-22T17:47:20","modified_gmt":"2011-04-22T16:47:20","slug":"introduction-to-erlang-list-comprehension","status":"publish","type":"post","link":"http:\/\/trigonakis.com\/blog\/2011\/04\/22\/introduction-to-erlang-list-comprehension\/","title":{"rendered":"Introduction to Erlang : List Comprehension"},"content":{"rendered":"
This entry is part 13 of 16 in the series Introduction to Erlang<\/a><\/div>

List Comprehension<\/h3>\n

Do you remember the lists:map\/2<\/code> and lists:filter\/2<\/code> functions from the previous post? If not, consult the Lists & lists Module<\/a> post. lists:map(Function, List)<\/code> returns a new list that results from List<\/code> after applying the Function<\/code> to each element. lists:filter(Predicate, List)<\/code> returns a list that contains only the elements of List<\/code> for which the call to Predicate<\/code> returns true.<\/p>\n

Both the aforementioned operations are commonly used, as well as their combination; map & filter<\/strong> (does it remind you map & reduce<\/i>?). Erlang provides this combined functionality using the list comprehension<\/strong> construct.<\/p>\n

Format<\/h4>\n

A list comprehension look like the following:<\/p>\n

\r\n[Expression || Generators1, Guards1, Generators2, ...]\r\n<\/pre>\n
Generators<\/h5>\n
As their name suggests, generators<\/i> create the data used in the filter-map operations. A generator has the Pattern <- Data<\/code> format, where Data<\/code> is a list or an expression that results to a list and Pattern<\/code> is a pattern used to match with the elements of the list. This pattern can be used to disassembly elements. For example, two valid generators are I <- lists:seq(1, 10)<\/code> and {X, Y} <- [{'A', 'Excellent'}, {'B', 'Good'}, {'C', 'Fair'}]<\/code>.<\/p>\n
Expression<\/h5>\n
The expression<\/i> specifies the elements of the result. For example, [I || I <- [1, 2, 3]]<\/code> returns the input list element as is.<\/p>\n
Guards<\/h5>\n
Guards<\/i> are expressions that return either true<\/code> or false<\/code>, the same as the guards we have seen in the previous posts. They apply to the variables that are on the left of the guard and the ones that are accessible due to the scope where the comprehension runs. For example, I <- [1, 2, 3, 4], I rem 2 == 0<\/code> is a valid generator - guard combination (the result should be obvious; only the even numbers \"pass\" the guard's test).
\n<\/p>\n
Lists Examples<\/h4>\n
Following the same template with the previous posts, I will first show some examples that implement some list functions. Most of them already exist in the lists<\/code> module. As I did in the past, I will add these functions to the module called mlists<\/code>.<\/p>\n
map\/2<\/h5>\n
Called as map(Function, List)<\/code>. The resulting list contains the elements of the input list after applied to the input function.<\/p>\n
\r\n% Generator : the items of the list provided\r\n% Guard : no guard expression, all items are kept\r\n% Expression : the item from the generator after applied\r\n%              to the Function\r\nmap(Function, List) ->\r\n    [Function(I) || I <- List].\r\n\r\n% example\r\n2> mlists:map(fun(I) -> 2 * I end, [1, 2, 3, 4]).\r\n[2,4,6,8]\r\n<\/pre>\n
filter\/2<\/h5>\n
Called as filter(Predicate, List)<\/code>. Keeps the elements for which the call to Predicate<\/code> returns true.<\/p>\n
\r\n% Generator : the items of the list provided\r\n% Guard : the item should return true when applied to the Pred\r\n% Expression: keep the elements of the list that \"pass\" the\r\n%             guard test, as they are\r\nfilter(Pred, List) ->\r\n    [I || I <- List, Pred(I)].\r\n\r\n% example\r\n6> mlists:filter(fun(I) -> is_atom(I) end, [1, a, 2, b, 3.0, \"d\"]).\r\n[a,b]\r\n<\/pre>\n
deleteall\/2<\/h5>\n
Deletes all occurrences of an Element from the list.<\/p>\n
\r\n% Generator : the items of the list provided\r\n% Guard : the item should not be equal (both value and type)\r\n%         with the Elem\r\n% Expression: keep the elements of the list that \"pass\" the\r\n%             guard test, as they are\r\ndeleteall(Elem, List) ->\r\n    [I || I <- List, I =\/= Elem].\r\n\r\n% example\r\n2> mlists:deleteall(3, [1, 2, 3, 4, 3, 2, 1]).\r\n[1,2,4,2,1]\r\n<\/pre>\n
partition\/2<\/h5>\n
Partition a list into two, according to if the elements satisfy or not a given predicate.<\/p>\n
\r\npartition(Pred, List) ->\r\n    {[I || I <- List, Pred(I)],\r\n     [I || I <- List, not(Pred(I))]}.\r\n\r\n% an alternative implementation\r\npartition2(Pred, List) ->\r\n    Sat = filter(Pred, List),\r\n    {Sat, List -- Sat}.\r\n\r\n% example\r\n10> mlists:partition(fun(I) -> is_atom(I) end, [1, a, 2, b, 3.0]).\r\n{[a,b],[1,2,3.0]}\r\n<\/pre>\n
replicated\/2<\/h5>\n
Called as replicated(Item, Times)<\/code>. Creates a list of Item<\/code>s of length Times<\/code>.<\/p>\n
\r\n% Generator : only used for fixing the length\r\n% Expression : a fixed item\r\nreplicated(Item, Times) ->\r\n    [Item || _ <- lists:seq(1, Times)].\r\n\r\n% example\r\n14> mlists:replicated(':-)', 10).\r\n[':-)',':-)',':-)',':-)',':-)',':-)',':-)',':-)',':-)',\r\n ':-)']\r\n<\/pre>\n
replicate_items\/2<\/h5>\n
Called as replicate_items(Times, List)<\/code>. Replicates each elements of the list Times<\/code> times.<\/p>\n
\r\nreplicate_items(Times, List) ->\r\n    mlists:flatten([[Item || _ <- lists:seq(1, Times)] || Item <- List]).\r\n\r\n% same as\r\n% replicate_items(Times, List) ->\r\n%    mlists:flatten([replicated(Item, Times) || Item <- List]).\r\n\r\n% example\r\n5> mlists:replicate_items(3, [a, b, c]). \r\n[a,a,a,b,b,b,c,c,c]\r\n<\/pre>\n
member\/2<\/h5>\n
Returns true<\/code> if an element is a member of the list, else returns false<\/code>.<\/p>\n
\r\nmember(Elem, List) ->\r\n    [] \/= [ok || I <- List, I == Elem].\r\n\r\n% example\r\n1> mlists:member(a, [3, 2, 1, a, x, z]).\r\ntrue\r\n2> mlists:member(a, [3, 2, 1, aa, x, z]).\r\nfalse\r\n<\/pre>\n
member_times\/2<\/h5>\n
Returns the number of occurences of an element in a list.<\/p>\n
\r\nmember_times(Elem, List) ->\r\n    length([ok || I <- List, I == Elem]).\r\n\r\n% example\r\n5> mlists:member_times(a, [1, a, 2, 3, b, a, c]).\r\n2\r\n6> mlists:member_times(a, [1, a, 2, 3, b, c]).   \r\n1\r\n7> mlists:member_times(a, [1, 2, 3, b, c]).   \r\n0\r\n<\/pre>\n
intersection\/2<\/h5>\n
Called as intersection(List1, List2)<\/code>. Returns the List1<\/code> without the elements that are exist in List2<\/code>.<\/p>\n
\r\nintersection(List1, List2) ->\r\n    [I || I <- List1, not(mlists:member(List2))].\r\n\r\n% example\r\n9> mlists:intersection([1, 2, 3, 4, 3, 2, 1], [2, 4]).\r\n[1,3,3,1]\r\n<\/pre>\n
quicksort\/1<\/h5>\n
This is the famous Quicksort implementation that is often used to show the power and compactness of Erlang.<\/p>\n
\r\nqsort([]) ->\r\n    [];\r\nqsort([Pivot | List]) ->\r\n    qsort([I || I <- List, I < Pivot]) \r\n    ++ \r\n    [Pivot | qsort([I || I <- List, I >= Pivot])].\r\n\r\n% example\r\n2> mlists:qsort([7, 1, 3, 9, 1, 2, 0, 4, 6, 5]).\r\n[0,1,1,2,3,4,5,6,7,9]\r\n<\/pre>\n
Other Examples<\/h4>\n
Eratosthenes' Sieve<\/h5>\n
Sieve of Eratosthenes<\/i> is an algorithm for calculating the primes up to a given integer. In a nutshell, given an integer N<\/code> the algorithm works as following:<\/p>\n
    \n
  1. Generate the list that contains the integers 2, 3, 4 ... N<\/code>.<\/li>\n
  2. Remove the first element E<\/code> and add it to the list with the found primes.<\/li>\n
  3. Remove all the multiplies of E<\/code> from the remaining list since they cannot be a prime.<\/li>\n
  4. If the resulting list is empty, the algorithm finished, else, go to step two with the resulting list as input.<\/li>\n<\/ol>\n
    For more details on the algorithm go to Wikipedia<\/a>.<\/p>\n
    \r\nsieve(N) when is_integer(N) ->\r\n    calc(lists:seq(2, N)).\r\n\r\ncalc([]) ->\r\n    [];\r\ncalc([Prime | Rest]) ->\r\n    [Prime | calc([N || N <- Rest, N rem Prime \/= 0])].\r\n\r\n% example\r\n4> erat:sieve(120).\r\n[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,\r\n 79,83,89,97,101,103,107,109|...]\r\n<\/pre>\n
    As you can see, the definition of the algorithm in Erlang is shorter and more clear than the textual one :-). Just to note that the algorithm that I described is actually the Euler's sieve<\/i> and not the Eratosthenes one. Euler's sieve is an \"optimized\" version of the Eratosthenes' algorithm.<\/p>\n
    Multiple Generators<\/h5>\n
    Now I will present some examples with multiple generators.<\/p>\n
    \r\n% think of this example as a for loop with an inner for loop\r\n% the J <- [...] would be the inner for loop\r\n1> [{I, J} || I <- [1, 2, 3], J <- [a, b, c]].\r\n[{1,a},{1,b},{1,c},{2,a},{2,b},{2,c},{3,a},{3,b},{3,c}]\r\n\r\n% duplicate list\r\n2> [I || _ <- [a, a], I <- [1, 2, 3]].\r\n[1,2,3,1,2,3]\r\n\r\n% duplicate elements \r\n3> [I || I <- [1, 2, 3], J <- [a, a]].\r\n[1,1,2,2,3,3]\r\n\r\n% discard elements and duplicate the others\r\n4> Discard = [2, 4].                                                                         \r\n[2,4]\r\n5> [I || I <- [1, 2, 3, 4, 5, 6], not(lists:member(I, Discard)), _ <- [a, a]].            \r\n[1,1,3,3,5,5,6,6]\r\n\r\n% subsequences\r\n8> [[I || I <- lists:seq(1, J)] || J <- lists:seq(1, 10)].\r\n[[1],\r\n [1,2],\r\n [1,2,3],\r\n [1,2,3,4],\r\n [1,2,3,4,5],\r\n [1,2,3,4,5,6],\r\n [1,2,3,4,5,6,7],\r\n [1,2,3,4,5,6,7,8],\r\n [1,2,3,4,5,6,7,8,9],\r\n [1,2,3,4,5,6,7,8,9,10]]\r\n<\/pre>\n
    Next<\/h3>\n
    Next post will be about creating processes<\/strong> in Erlang.<\/p>\n","protected":false},"excerpt":{"rendered":"
    This entry is part 13 of 16 in the series Introduction to Erlang<\/a><\/div>
    List Comprehension Do you remember the lists:map\/2 and lists:filter\/2 functions from the previous post? If not, consult the Lists & lists Module post. lists:map(Function, List) returns a new list that results from List after applying the Function to each element. lists:filter(Predicate, List) returns a list that contains only the elements of List for which the […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"jetpack_publicize_message":"","jetpack_is_tweetstorm":false,"jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[40,51,28],"tags":[26,65,42],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p1ouW6-8X","_links":{"self":[{"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/posts\/555"}],"collection":[{"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/comments?post=555"}],"version-history":[{"count":18,"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/posts\/555\/revisions"}],"predecessor-version":[{"id":571,"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/posts\/555\/revisions\/571"}],"wp:attachment":[{"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/media?parent=555"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/categories?post=555"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/tags?post=555"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}