DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Refcards Trend Reports Events Over 2 million developers have joined DZone. Join Today! Thanks for visiting DZone today,
Edit Profile Manage Email Subscriptions Moderation Admin Console How to Post to DZone Article Submission Guidelines
View Profile
Sign Out
Refcards
Trend Reports
Events
Zones
Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Partner Zones AWS Cloud
by AWS Developer Relations
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Partner Zones
AWS Cloud
by AWS Developer Relations
The Latest "Software Integration: The Intersection of APIs, Microservices, and Cloud-Based Systems" Trend Report
Get the report
  1. DZone
  2. Coding
  3. Languages
  4. Erlang: list comprehensions

Erlang: list comprehensions

Giorgio Sironi user avatar by
Giorgio Sironi
·
Jan. 23, 13 · Interview
Like (0)
Save
Tweet
Share
11.70K Views

Join the DZone community and get the full member experience.

Join For Free

 List comprehensions are one of Erlang's most powerful tools: learn how you can write quicksort in two lines in a famous example, and more on how to read and write list comprehensions in Erlang's syntax.

Higher-order functions

This kind of functions, which work over lists, can be easily reimplemented with list comprehensions, and can serve as an example here.

As you may remember, map/2 takes a list and a function, and applies the function to all the elements of the list. You can implement map like this:

map_test() ->
  ?assertEqual([1, 4, 9], [X*X || X <- [1, 2, 3]]).

The syntax literally means X*X (the square/1 function) for all the X taken from the list [1, 2, 3].

In the same way, it's possible to reimplement filter/2, by adding a condition at the end of the expression:

filter_test() ->
  ?assertEqual([42, 5], [X || X <- [-1, 42, -2, 5], X > 0]).

Of course you can put the concepts together and map to square/1 the result of a filter:

filter_map_test() ->
  ?assertEqual([1, 4], [X*X || X <- [-1, 42, -2, 5], X < 0]).

So Erlang has a language syntax for list-related functions, after providing them as library functions.

You have the choice to combinate these operations in a single expression, or to apply them in a series of calls. The first solution has concision on its side; the second has flexibility as you have visibility on the intermediate results and can apply the functions one at a time.

Raising the difficulty

Erlang's assignment sugar is usually available also inside list comprehensions.  Thus pattern matching is something you can do in the generator of such an expression:

pattern_matching_test() ->
  % This represents a^2, b^3, c^5
  Monomia = [{a, 2}, {b, 3}, {a, 5}],
  ?assertEqual([2, 5], [Exponent || {Letter, Exponent} <- Monomia, Letter == a]).


You can even write more than one generator, so that they will be applied in sequence, in a cartesian product:

two_nested_generators_test() ->
  Letters = [a, b],
  Numbers = [1, 2],
  Expected = [{a, 1}, {a, 2}, {b, 1}, {b, 2}],
  ?assertEqual(Expected, [{Letter, Exponent} || Letter <- Letters, Exponent <- Numbers]).

Every time a Letter is extracted from the list, the Exponent generator is run so that each Exponent is assigned to each of the Letter instances.

With this in mind, we can look at the next, example, the unroll/1 function, which takes a the elements of nested lists and put them all together in a single, unidimensional list:

unroll_test() ->
  ListOfLists = [[1, 2], [3, 4, 5]],
  ?assertEqual([1, 2, 3, 4, 5], [X || SingleList <- ListOfLists, X <- SingleList]).


The key feature is that we can use the output of previous generators inside the next ones. So, for every SingleList we run a generator that extracts each element of the nested list.

Quicksort

Erlang's list comprehensions can be a mild form of metaprogramming: they compress logic in new constructs. The logic of what you would write as for() cycles in an imperative language is exposed here in a generator, so that you can write the interesting part (what to extract) in the shortest possible form, associating a list to a variable representing its element.

quicksort/1 is a very famous example of the power of list comprehensions: the quicksort algorithm implemented in two lines of Erlang code.

Here is a test for quicksort/1, which orders the elements of a list:

quicksort_test() ->
  Unsorted = [3, 1, 2, 5, 4],
  ?assertEqual([1, 2, 3, 4, 5], qsort(Unsorted)).

The first line is the base case of recursion:

qsort([]) -> [];

The second line is a bit longer, but you should be able to read it by now:

qsort([X|Xs]) ->
  qsort([Y || Y <- Xs, Y =< X]) ++ [X] ++ qsort([Y || Y <- Xs, Y > X]).

In English, this would be read as take a list and break it into an head X and tail Xs. Return a list composed of three sublists:

  1. the list of all Y from the tail Xs such that Y is less than or equal to X, ordered by qsort/1.
  2. the list containing just X.
  3. the list of all Y from the tail Xs such that Y is greater than X, ordere dby qsort/1.

X is what is called the pivot in this implementation: the element that we keep fixed while moving the other elements of the list before or after it.

Note that quicksort/1 can be implemented so easily because it is a recursive algorithm, and as such it plays very well with Erlang. Probably mergesort/1 would be more difficult and take longer to write, but list comprehensions can be helpful in that case too.

Erlang (programming language)

Opinions expressed by DZone contributors are their own.

Popular on DZone

  • HTTP vs Messaging for Microservices Communications
  • REST vs. Messaging for Microservices
  • Full Lifecycle API Management Is Dead
  • The 5 Books You Absolutely Must Read as an Engineering Manager

Comments

Partner Resources

X

ABOUT US

  • About DZone
  • Send feedback
  • Careers
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 600 Park Offices Drive
  • Suite 300
  • Durham, NC 27709
  • support@dzone.com
  • +1 (919) 678-0300

Let's be friends: