{"id":540,"date":"2011-04-18T19:12:24","date_gmt":"2011-04-18T18:12:24","guid":{"rendered":"http:\/\/trigonakis.com\/blog\/?p=540"},"modified":"2014-05-15T11:27:01","modified_gmt":"2014-05-15T10:27:01","slug":"introduction-to-erlang-list-lists-module","status":"publish","type":"post","link":"http:\/\/trigonakis.com\/blog\/2011\/04\/18\/introduction-to-erlang-list-lists-module\/","title":{"rendered":"Introduction to Erlang : List &#038; lists Module"},"content":{"rendered":"<div class=\"seriesmeta\">This entry is part 12 of 16 in the series <a href=\"http:\/\/trigonakis.com\/blog\/series\/introduction-to-erlang\/\" class=\"series-57\" title=\"Introduction to Erlang\">Introduction to Erlang<\/a><\/div><h3>List<\/h3>\n<p>List is the the most important data type in Erlang, as in every (?) functional programming language. We have seen and used lists in almost every previous post. In this post, I will briefly present the &#8220;theory&#8221; of lists and then present the Erlang&#8217;s <code>lists<\/code> module and its most important functions.<\/p>\n<h4>Definition<\/h4>\n<p>A list can be recursively defined as the construct that<\/p>\n<ul>\n<li>either is the empty list (denoted as <code>[]<\/code> in Erlang),<\/li>\n<li>or is a cosntruct that its first element is a term (called <i>head<\/i>) and what remains if the head is removed is a list (called <i>tail<\/i>)<\/li>\n<li>\n<\/li>\n<\/ul>\n<p>In Erlang a list of <code>N<\/code> elements has the <code>[Element1, Element2, ..., ElementN]<\/code> format (<code>N<\/code> is called the <i>length<\/i> of the list). So, <code>[]<\/code> is the empty list, <code>[1], [{a}]<\/code> are 1-element lists, <code>[1, 2], [a, {b, c}]<\/code> are 2-elements lists, etc. As we will see in a while, the format <code>[Element1, Element2, ..., ElementN]<\/code> is a shorthand for the <code>[Element1 | [Element2 | ... | [ElementN | []] ... ]<\/code> representation.<br \/>\n<!--more--><\/p>\n<h4>Decomposing &amp; Pattern Matching<\/h4>\n<p>An empty list pattern matches with <code>[]<\/code>.<\/p>\n<pre lang=\"erlang\">\r\n1> Empty = [].\r\n[]\r\n2> Empty == [].\r\ntrue\r\n3> Empty = []. \r\n[]\r\n4> NotEmpty = [1].\r\n[1]\r\n5> Empty == NotEmpty.\r\nfalse\r\n6> Empty = NotEmpty.\r\n** exception error: no match of right hand side value [1]\r\n<\/pre>\n<p>A non-empty list pattern matches with <code>[Head | Tail]<\/code>.<\/p>\n<pre lang=\"erlang\">\r\n1> [Head | Tail] = [1, 2, 3, 4]. \r\n[1,2,3,4]\r\n2> Head. \r\n1\r\n3> Tail.\r\n[2,3,4]\r\n4> [Head1 | Tail1] = Tail.\r\n[2,3,4]\r\n5> Head1.\r\n2\r\n6> Tail1.\r\n[3,4]\r\n7> [Head2 | Tail2] = [].\r\n** exception error: no match of right hand side value []\r\n<\/pre>\n<h5>Normal Representation<\/h5>\n<p>As mentioned before, the format <code>[Element1, Element2, ..., ElementN]<\/code> is a shorthand for the <code>[Element1 | [Element2 | ... | [ElementN | []] ... ]<\/code> representation.<\/p>\n<p>For example the list <code>[1, 2, 3]<\/code> is a shorthand for the <code>[1 | [2 | 3 | []]]<\/code>, that is the normal representation of a list.<\/p>\n<p>What we saw can be used for decomposing <\/p>\n<pre lang=\"erlang\">\r\n1> [A | [B |[C | D]]] = [1, 2, 3].\r\n[1,2,3]\r\n2> A.\r\n1\r\n3> B. \r\n2\r\n4> C.\r\n3\r\n5> D.\r\n[]\r\n<\/pre>\n<p>and composing<\/p>\n<pre lang=\"erlang\">\r\n1> List = [2,3].\r\n[2,3]\r\n2> List1 = [1 | List]. \r\n[1,2,3]\r\n3> List2 = [-1 | [0 | List1]]. \r\n[-1,0,1,2,3]\r\n4> List3 = [[-3, -2] | List2].\r\n[[-3,-2],-1,0,1,2,3] % the head is just 1 element \r\n<\/pre>\n<p>lists. Of course, since it is more readable and easier to write, the shorthand representation is usually used:<\/p>\n<pre lang=\"erlang\">\r\n1> [A, B, C] = [1, 2, 3].\r\n[1,2,3]\r\n2> [A, B, C, D] = [1, 2, 3]. % does not match cause\r\n% the left-hand side matches a 4-elements list\r\n** exception error: no match of right hand side value [1,2,3]\r\n3> [A, B, C | D] = [1, 2, 3].\r\n[1,2,3]\r\n4> D.\r\n[]\r\n5> [-3, -2 | [-1, 0 | [1 | [2,3]]]].  \r\n[-3,-2,-1,0,1,2,3]\r\n<\/pre>\n<h5>List Parsing<\/h5>\n<p>The pattern matching we saw before can be used in a function in order to parse the list<\/p>\n<pre lang=\"erlang\">\r\nparse([]) ->\r\n    % parsed the whole list\r\n    parsed.\r\nparse([Head | Tail]) ->\r\n    % do whatever with the current element Head\r\n    parse(Tail).\r\n<\/pre>\n<h4>Concatenation<\/h4>\n<p>Two lists can be concatenated using <code>++<\/code><\/p>\n<pre lang=\"erlang\">\r\n1> L1 = [1, 2], L2 = [3, 4, 5].\r\n[3,4,5]\r\n2> L1 ++ L2.\r\n[1,2,3,4,5]\r\n3> L1 ++ L2 ++ L1.\r\n[1,2,3,4,5,1,2]\r\n4> Mirror = fun(List) -> List ++ lists:reverse(List) end.\r\n#Fun<erl_eval .6.13229925>\r\n5> Mirror([a, b, {c}]).\r\n[a,b,{c},{c},b,a]\r\n<\/pre>\n<h4>Difference<\/h4>\n<p>You can take the difference of two lists (the left-hand side one without the element of the right-hand side) using the <code>--<\/code> operator<\/p>\n<pre lang=\"erlang\">\r\n1> [1, 2, 3] -- [1, 2, 3].\r\n[]\r\n2> [1, 2, 3] -- [1, 3].   \r\n[2]\r\n3> [1, 2, 3] -- [1, 3, 3].\r\n[2]\r\n4> [1, 3, 2, 3] -- [1, 3, 3].\r\n[2]\r\n5> [3, 1, 3, 2, 3] -- [1, 3, 3].\r\n[2,3]\r\n6> [1, 2, 3] -- [a, b].         \r\n[1,2,3]\r\n7> Delete = fun(List, Element) -> List -- [Element] end.\r\n#Fun<erl_eval .12.113037538>\r\n8> Delete([1,2,3,4,1], 1).\r\n[2,3,4,1]\r\n<\/pre>\n<h3>Module lists<\/h3>\n<p>The <code>lists<\/code> module defines some commonly used list processing functions. This module is extremely useful, so it is a good idea to &#8220;remember&#8221; what functions it provides. You can find <code>lists<\/code>&#8216;s module documentation <a href=\"http:\/\/erlang.org\/doc\/man\/lists.html\" target=\"_new\">here<\/a>.<\/p>\n<h4>all\/2<\/h4>\n<p>Called as <code>all(Pred, List)<\/code>. Returns true if <code>Pred(Element)<\/code> returns true for all lists&#8217; elements.<\/p>\n<pre lang=\"erlang\">\r\n1> L = [2, 4, 6, 8],          \r\n1> F = fun(X) -> X rem 2 == 0 end,\r\n1> lists:all(F, L).\r\ntrue\r\n2> f().                           \r\nok\r\n3> L = [2, 4, 5, 8],              \r\n3> F = fun(X) -> X rem 2 == 0 end,\r\n3> lists:all(F, L).               \r\nfalse\r\n<\/pre>\n<h4>any\/2<\/h4>\n<p>Like <code>all\/2<\/code> but returns true if any of the elements returns true for the predicate function.<\/p>\n<h4>append\/1|2<\/h4>\n<p>Concatenates the lists to one.<\/p>\n<pre lang=\"erlang\">\r\n4> lists:append([[1, 2], [3], [4, 5]]).\r\n[1,2,3,4,5]\r\n5> lists:append([1, 2], [3, 4]).       \r\n[1,2,3,4]\r\n<\/pre>\n<p>Notice that the operator <code>++<\/code> and the function <code>append\/2<\/code> are the same. <\/p>\n<h4>concat\/1<\/h4>\n<p>Accepts a list of items (atom, integer, float, string) and returns the concatenation of their textual representation as a list.<\/p>\n<pre lang=\"erlang\">\r\n9> lists:concat([\"ab\", '.', 1]).     \r\n\"ab.1\"\r\n<\/pre>\n<h4>delete\/2<\/h4>\n<p>Deletes an element from the list (first occurrence, if any).<\/p>\n<pre lang=\"erlang\">\r\n10> lists:delete(a, [d, a, d, a, d]).\r\n[d,d,a,d]\r\n<\/pre>\n<h4>filter\/2<\/h4>\n<p>Called as <code>filter(Pred, List)<\/code>. Returns a list containing only the elements that return true for the <code>Pred<\/code>.<\/p>\n<pre lang=\"erlang\">\r\n11> Gt10 = fun(X) -> X > 10 end, lists:filter(Gt10, [1, 2, 22, 3, 44, 5, 66]).\r\n[22,44,66]\r\n12> L = [1, a, b, 2, c, 3.0, d, {4}]. \r\n[1,a,b,2,c,3.0,d,{4}]\r\n13> lists:filter(fun(X) -> is_number(X) end, L).\r\n[1,2,3.0]\r\n<\/pre>\n<h4>flatten\/1<\/h4>\n<p>Returns a flattened (no element is a list) version of the input list.<\/p>\n<pre lang=\"erlang\">\r\n12> lists:flatten([1, [2], [3, 4, [5, [6, 7]]], [[[[8]]]]]).\r\n[1,2,3,4,5,6,7,8]\r\n<\/pre>\n<h4>key*** functions<\/h4>\n<p>There are several functions which their name starts with the word <code>key<\/code>. They are all used to process lists of tuples.<\/p>\n<pre lang=\"erlang\">\r\n15> Kl = [{a, k1, a}, {b, k2, b}, {c, k3, c}, {e, k5, e}].\r\n[{a,k1,a},{b,k2,b},{c,k3,c},{e,k5,e}]\r\n16> lists:keydelete(k3, 2, Kl).                           \r\n[{a,k1,a},{b,k2,b},{e,k5,e}]\r\n17> lists:keysearch(k3, 2, Kl).\r\n{value,{c,k3,c}}\r\n18> lists:keysearch(k4, 2, Kl). \r\nfalse\r\n19> lists:keyreplace(k3, 2, Kl, {new, tuple}).\r\n[{a,k1,a},{b,k2,b},{new,tuple},{e,k5,e}]\r\n<\/pre>\n<h4>last\/1<\/h4>\n<p>Returns the last element of the list.<\/p>\n<pre lang=\"erlang\">\r\n20> lists:last([1, 2, 3]).\r\n3\r\n<\/pre>\n<h4>map\/2<\/h4>\n<p>Called as <code>map(Fun, List)<\/code>. Applies function <code>Fun<\/code> to every item of the list and returns the resulting list.<\/p>\n<pre lang=\"erlang\">\r\n21> lists:map(fun(I) -> 2 * I end, [1, 2, 3]).\r\n[2,4,6]\r\n<\/pre>\n<h4>max\/1, min\/1<\/h4>\n<p>Returns the maximum \/ minimum of the list.<\/p>\n<h4>member\/2<\/h4>\n<p>Return true if the given element exists in the list else returns false.<\/p>\n<pre lang=\"erlang\">\r\n22> lists:member(4, [1, 2, 3, 4, 5]).\r\ntrue\r\n23> lists:member(14, [1, 2, 3, 4, 5]).\r\nfalse\r\n<\/pre>\n<h4>nth\/2<\/h4>\n<p>Called as <code>nth(N, List)<\/code>. Return the <code>N<\/code>th element of the <code>List<\/code>. The head of the list is element 1.<\/p>\n<pre lang=\"erlang\">\r\n24> lists:nth(3, [{1}, {2}, {three}, {}, {s, i, x}]).\r\n{three}\r\n<\/pre>\n<h4>partition\/2<\/h4>\n<p>Partitions a list to two according to if the elements satisfy or not a given predicate.<\/p>\n<pre lang=\"erlang\">\r\n3> L = [1, a, b, 2, c, 3.0, d, {4}].              \r\n[1,a,b,2,c,3.0,d,{4}]\r\n4> {Satisfy, Not} = lists:partition(fun(X) -> is_number(X) end, L).   \r\n{[1,2,3.0],[a,b,c,d,{4}]}\r\n5> Satisfy.\r\n[1,2,3.0]\r\n<\/pre>\n<h4>prefix\/2<\/h4>\n<p>Returns true if the first list is a prefix of the second, else false.<\/p>\n<pre lang=\"erlang\">\r\n7> lists:prefix([a, b, c], [a, b, c, d, e]).\r\ntrue\r\n8> lists:prefix([a, b, c], [a, b, cc, d, e]).\r\nfalse\r\n<\/pre>\n<h4>reverse\/1|2<\/h4>\n<p>Returns the reverse of a list.<\/p>\n<pre lang=\"erlang\">\r\n9> lists:reverse([a, b, c, d]).\r\n[d,c,b,a]\r\n% reverse \/ append\r\n10> lists:reverse([a, b, c, d], [1, 2, 3]).\r\n[d,c,b,a,1,2,3]\r\n<\/pre>\n<h4>seq\/2|3<\/h4>\n<p>Called as <code>seq(From, To [, Increment])<\/code>. Returns the sequence of integers starting from <code>From<\/code> and containing the integers <code>From + 1, From + 2, ...<\/code> up to <code>To<\/code> or the integers <code>From + 1*Increment, From + 2*Increment, ...<\/code> up to <code>To<\/code> if it is called as <code>seq\/3<\/code>.<\/p>\n<pre lang=\"erlang\">\r\n16> lists:seq(1, 7).   \r\n[1,2,3,4,5,6,7]\r\n17> lists:seq(1, 8, 3).\r\n[1,4,7]\r\n<\/pre>\n<h4>sort\/1|2<\/h4>\n<p>Sorts a list to increasing order or according to a given function.<\/p>\n<pre lang=\"erlang\">\r\n24> L = [3, 1, 2, 5, 4].        \r\n[3,1,2,5,4]\r\n25> lists:sort(L).              \r\n[1,2,3,4,5]\r\n26> Gt = fun(I, J) -> I > J end.\r\n#Fun<erl_eval .12.113037538>\r\n27> lists:sort(Gt, L).          \r\n[5,4,3,2,1]\r\n<\/erl_eval><\/pre>\n<h4>split\/2<\/h4>\n<p>Called as <code>split(N, List1)<\/code>. Splits the list into two; the first having the <code>N<\/code> first elements and the second the remaining ones.<\/p>\n<pre lang=\"erlang\">\r\n1> lists:split(3, [1, 2, 3, a, b]).\r\n{[1,2,3],[a,b]}\r\n<\/pre>\n<h4>sublist\/2|3<\/h4>\n<p>Returns a sublist of a list.<\/p>\n<pre lang=\"erlang\">       \r\n2> L = [1, 2, 3, 4, 5, 6].\r\n[1,2,3,4,5,6]\r\n3> lists:sublist(L, 3).\r\n[1,2,3]\r\n4> lists:sublist(L, 2, 4).\r\n[2,3,4,5]\r\n5> lists:sublist(L, 11).  \r\n[1,2,3,4,5,6]\r\n<\/pre>\n<h4>subtract\/2<\/h4>\n<p>Returns the first list without the elements contained in the second list. Equivalent to the operator <code>--<\/code>.<\/p>\n<pre lang=\"erlang\">\r\n8> lists:subtract(\"vasilis\", \"ai\").\r\n\"vslis\"\r\n9> \"vasilis\" -- \"ai\".              \r\n\"vslis\"\r\n<\/pre>\n<h4>suffix\/2<\/h4>\n<p>Returns true if the first is a suffix of the second, else returns false.<\/p>\n<pre lang=\"erlang\">\r\n10> lists:suffix([3, 4], [a, b, 1, 2, 3, 4]).\r\ntrue\r\n11> lists:suffix([3, 4], [a, b, 1, 2, 33, 4]).\r\nfalse\r\n<\/pre>\n<h4>sum\/1<\/h4>\n<p>Returns the sum of the elements of a list containing numbers.<\/p>\n<pre lang=\"erlang\">\r\n12> lists:sum([1, 2.2, 3]).\r\n6.2\r\n<\/pre>\n<h4>u*** functions<\/h4>\n<p>There are several function which their name starts with <code>u<\/code> and the results they return contain no duplicates.<\/p>\n<pre lang=\"erlang\">\r\n14> lists:usort([5, 3, 2, 3, 2, 1, 4, 5]).\r\n[1,2,3,4,5]\r\n<\/pre>\n<h3>Next<\/h3>\n<p>Next post will be about <strong>list comprehension<\/strong>.<\/p>\n","protected":false},"excerpt":{"rendered":"<div class=\"seriesmeta\">This entry is part 12 of 16 in the series <a href=\"http:\/\/trigonakis.com\/blog\/series\/introduction-to-erlang\/\" class=\"series-57\" title=\"Introduction to Erlang\">Introduction to Erlang<\/a><\/div><p>List List is the the most important data type in Erlang, as in every (?) functional programming language. We have seen and used lists in almost every previous post. In this post, I will briefly present the &#8220;theory&#8221; of lists and then present the Erlang&#8217;s lists module and its most important functions. Definition A list [&hellip;]<\/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-8I","_links":{"self":[{"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/posts\/540"}],"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=540"}],"version-history":[{"count":8,"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/posts\/540\/revisions"}],"predecessor-version":[{"id":801,"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/posts\/540\/revisions\/801"}],"wp:attachment":[{"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/media?parent=540"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/categories?post=540"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/tags?post=540"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}