A bonus Erlang Thursday for everyone.

Giving the Dallas/Fort Worth Erlang User group presentation last week, we had a couple of people new to Erlang make it to our meeting, and the question was raised:

Do lists have any smarts around knowing their length, or does it have to run through all the items to calculate the length?

I was 99% sure that Erlang has to run through the list every time, since it uses linked lists style data structures for it’s list, but wasn’t sure if there might be something smart in the implementation that I wasn’t aware of to speed up that functionality.

In putting together the regularly scheduled Erlang Thursday post for today, I realized I should have busted out timer:tc to demonstrate the behavior of erlang:length/1 by showing how long it takes to get the length of different lists.

So in honor of that question, and as a reminder to review it at the next user group meeting, I am documenting the behavior here. And remember, that the first item in the result tuple is the time in microseconds the operation took.

timer:tc(erlang, length, [lists:seq(1, 10)]).
{2,10}
timer:tc(erlang, length, [lists:seq(1, 1000)]).
{5,1000}
timer:tc(erlang, length, [lists:seq(1, 10000)]).
{41,10000}
timer:tc(erlang, length, [lists:seq(1, 100000)]).
{134,100000}
timer:tc(erlang, length, [lists:seq(1, 1000000)]).
{1918,1000000}
timer:tc(erlang, length, [lists:seq(1, 10000000)]).
{25139,10000000}
timer:tc(erlang, length, [lists:seq(1, 100000000)]).
{1368691,100000000}

After about 1000 items in a linked list, we start growing lineraly in the time it takes to count the items, so if it is not doing an actual traversal of all the items, it has the same scale of doing so as far as the order of operations (Big-O) goes.

–Proctor

Today’s Erlang Thursday looks some more at that ordsets module and covers ordsets:intersection/2.

ordsets:intersection/2 takes two ordered sets and returns a new ordered set that is the intersection of the two ordered sets provided. For those who don’t have a background wth set theory, all a set intersection is is the set of items that all the sets we are intersecting have in common.

OrderedSet1 = ordsets:from_list([1, 2, 1, 3, 2, 4, 4, 9]).
[1,2,3,4,9]
OrderedSet2 = ordsets:from_list([1, 3, 5, 7, 9]).
[1,3,5,7,9]
ordsets:intersection(OrderedSet1, OrderedSet2).
[1,3,9]
ordsets:intersection(OrderedSet2, OrderedSet1).
[1,3,9]

Because ordsets:intersection/2 looks for the common elements in the ordered sets, it is commutative, and as we see above, we get the same result regardless of which order we pass in the two ordered sets as arguments.

If there are no items in common, the returned result is an empty ordered set (really an empty list, but see last week’s post on ordsets:union/2 on the dangers of just using a list as a ordered set).

Evens = ordsets:from_list(lists:seq(2, 20, 2)).
[2,4,6,8,10,12,14,16,18,20]
Odds = ordsets:from_list(lists:seq(1, 20, 2)).
[1,3,5,7,9,11,13,15,17,19]
ordsets:intersection(OrderedSet2, ordsets:new()).
[]
ordsets:intersection(Evens, Odds).
[]

Erlang also provides ordsets:intersection/1, that takes a list of ordered sets as its argument, and returns the intersection of all the ordered sets in that list.

OrderedSet3 = ordsets:from_list([1, 1, 2, 3, 5, 8]).
[1,2,3,5,8]
ordsets:intersection([Evens, Odds, OrderedSet1]).
[]
ordsets:intersection([Odds, OrderedSet2, OrderedSet1]).
[1,3,9]
ordsets:intersection([Evens, OrderedSet1, OrderedSet3]).
[2]
ordsets:intersection([Odds, OrderedSet1, OrderedSet3]).
[1,3]

–Proctor

Today’s Erlang Thursday is on ordsets:union/2.

ordsets:union/2 takes two ordered sets and returns an merged ordered set of the arguments.

SetA = ordsets:from_list([1, 1, 2, 3, 5]).
% [1,2,3,5]
SetB = ordsets:new().
% []
SetC = ordsets:from_list([3, 1, 4, 1, 5, 9]).
% [1,3,4,5,9]
SetD = ordsets:from_list([a, b, c, d, e]).
% [a,b,c,d,e]
UnionAB = ordsets:union(SetA, SetB).
% [1,2,3,5]
UnionAC = ordsets:union(SetA, SetC).
% [1,2,3,4,5,9]

And because a string in Erlang is just a list of characters, we can also create ordered sets from strings, and then get a union of the unique characters that are in two strings.

ordsets:from_list("Kermit").
% "Keimrt"
ordsets:from_list([75, 101, 114, 109, 105, 116]).
% "Keimrt"
ordsets:from_list("Mississippi").
% "Mips"
ordsets:union(ordsets:from_list("Kermit"), ordsets:from_list("Mississippi")).
% "KMeimprst"

The ordsets modules also contains ordsets:union/1, which takes a list of ordered sets and returns the union of all the ordered sets in the list.

UnionAC = ordsets:union([SetA, SetC]).
% [1,2,3,4,5,9]
UnionABC = ordsets:union([SetB, SetC, SetA]).
% [1,2,3,4,5,9]
UnionABCD = ordsets:union([SetB, SetC, SetA, SetD]).
% [1,2,3,4,5,9,a,b,c,d,e]
UnionCD = ordsets:union([SetC, SetD]).
% [1,3,4,5,9,a,b,c,d,e]

WARNING: While the representation for an ordered set is just a list, if you pass a list to ordsets:union/2 you will not get what you expect, as it expects the items in each “ordered set” to actually be ordered and a set.

ordsets:union([1, 2, 3], [a, b, c]).
% [1,2,3,a,b,c]
ordsets:union([1, 1, 2, 3, 1, 2], [a, b, c]).
% [1,1,2,3,1,2,a,b,c]
ordsets:union([1, 1, 2, 3, 1, 2], [1, a, b, c]).
% [1,1,2,3,1,2,a,b,c]
ordsets:union([1, 1, 2, 3, 1, 2], [1, a, b, c, 1]).
% [1,1,2,3,1,2,a,b,c,1]

–Proctor

Today’s Erlang Thursday covers queue:out/1 from the queue module’s Original API.

queue:out/1 is one of my all time Queue fuctions, or methods, that I have seen, and that is across all the languages and libraries that I have encountered.

“What makes it so great?”, I can hear you asking.

That would be it’s combination of tuples, tagged tuples, immutability, forgivingness, and the fact that after seeing the result, it makes me wish more Queue implementations had an API like this.

First there have been many times in my past where either myself, or someone else, has forgotten to do a check to see if a queue is empty before trying to pop the first item from it, and that mistake has resulted in a not-so-nice runtime error.

queue:out/1 on the other hand, doesn’t trigger an error when you try to call it on an empty queue. Rather it returns a tagged tuple telling you that the queue you tried to call out on was empty, and the empty queue.

queue:out(queue:new()).
% {empty,{[],[]}} 

If we do pass in a non-empty queue, queue:out/1 returns a two tuple, with the first element being a tagged tuple that tells us we got a value out and the HEAD of the original queue, and for the second element, we get a new queue with the result of removing the first item.

Queue = queue:from_list([a, b, c, d]).
% {[d],[a,b,c]}
queue:out(Queue).
% {{value,a},{[d],[b,c]}}
Queue.
% {[d],[a,b,c]}
{{value, Head}, NewQueue} = queue:out(Queue).
% {{value,a},{[d],[b,c]}}
Queue.
% {[d],[a,b,c]}
Head.
% a
NewQueue.
% {[d],[b,c]}
queue:head(NewQueue).
% b

When dealing with the abstract notion of a queue across any language, the concept of a “pop” does two things, returns the top item of the queue, and modifies the queue to have that item removed.

Since Erlang queues are immutable, after you think about it for a few minutes, it starts to make sense that queue:out/1 handles both those behaviors of “pop” by returning both the item removed from the queue, and the new state of the queue with that item removed.

Erlang’s queue module also provides a function queue:out_r/1 which behaves the same as queue:out/1 except it operates off the last item in the queue, instead of the first item.

queue:out_r(queue:from_list([a, b, c, d])).
% {{value,d},{[c][/c],[a,b]}}
queue:out_r(queue:new()).
% {empty,{[],[]}}

I hope you found queue:out/1 as handy and as nice I have,

–Proctor

Today’s Erlang Thursday is on queue:split/2 from the queue modules Original API.

queue:split/2 takes two arguments. The first argument being a integer N from 0 to X, where X is number of items in the queue, and the second argument is the queue that we wish to split. The return value is a two-tuple with a the first item being a queue of the first N items, and the second item in the tuple is a queue of the rest of the items.

QueueOne = queue:from_list([a, 1, b, 2, c, 3, 4]).
% {[4,3,c],[a,1,b,2]}
queue:split(4, QueueOne).
% {{[2],[a,1,b]},{[4,3],[c][/c]}}
queue:split(0, QueueOne).
% {{[],[]},{[4,3,c],[a,1,b,2]}}
queue:split(1, QueueOne).
% {{[],[a]},{[4,3,c],[1,b,2]}}
queue:split(7, QueueOne).
% {{[4,3,c],[a,1,b,2]},{[],[]}}
queue:split(15, QueueOne).
% ** exception error: bad argument
%      in function  queue:split/2
%         called as queue:split(15,{[4,3,c],[a,1,b,2]})
{SplitFirst, SplitSecond} = queue:split(3, QueueOne).
% {{[b,1],[a]},{[4,3,c],[2]}}
SplitFirst.
% {[b,1],[a]}
SplitSecond.
% {[4,3,c],[2]}
queue:peek(SplitFirst).
% {value,a}
queue:peek(SplitSecond).
% {value,2}

Erlang also provides a queue:join/2 function that takes two queues, and returns a new queue, with the queue that was passed as the second argument appended to the queue passed in as the first argument.

queue:join(SplitFirst, SplitSecond).
% {[4,3,c],[a,1,b,2]}
queue:join(SplitSecond, SplitFirst).
% {[b,1],[2,c,3,4,a]}
queue:join(queue:new(), SplitFirst).
% {[b,1],[a]}
queue:join(queue:new(), queue:new()).
% {[],[]}

–Proctor

For today’s Erlang Thursday we continue looking at the queue module and look at queue:peek/1 from the Extended API.

queue:peek/1 takes a queue as it’s argument and returns either the atom empty if the queue is empty, or {value, Item} where Item is the item at the head of the queue.

QueueOne = queue:from_list([1, 2, 3, 4, 5]).
% {[5,4],[1,2,3]}
queue:peek(QueueOne).
% {value,1}
QueueOne.
% {[5,4],[1,2,3]}
EmptyQueue = queue:new().
% {[],[]}
queue:peek(EmptyQueue).
% empty

queue:peek/1 does not modify the existing queue at all either, so we can call it once as seen above, or multiple times as below, and the queue we peeked at doesn’t change.

QueueTwo = queue:from_list([a, b, c, d, e, f]).
% {[f,e],[a,b,c,d]}
queue:peek(QueueTwo).
% {value,a}
queue:peek(QueueTwo).
% {value,a}
queue:peek(QueueTwo).
% {value,a}
QueueTwo.
% {[f,e],[a,b,c,d]}

And unlike we saw in the previous Erlang Thursday on queue:head/1, we can safely peek at an empty queue instead of getting an exception.

queue:head(EmptyQueue).
% ** exception error: empty
%      in function  queue:head/1
%         called as queue:head({[],[]})
queue:peek(EmptyQueue).
% empty

Erlang’s queue module also contains queue:peek_r/1 which will peek at the element at the rear of the queue.

queue:peek_r(EmptyQueue).
% empty
queue:peek_r(QueueOne).
% {value,5}
queue:peek_r(QueueOne).
% {value,5}
queue:peek_r(QueueOne).
% {value,5}
queue:peek_r(QueueTwo).
% {value,f}
QueueTwo.
% {[f,e],[a,b,c,d]}
QueueOne.
% {[5,4],[1,2,3]}
EmptyQueue.
% {[],[]}

–Proctor

In today’s Erlang Thursday we continue with the queue module’s Okasaki API, and look at queue:tail/1.

queue:tail/1 takes a non-empty queue as its argument, and returns a new queue with the first element removed.

Queue = queue:from_list([1, 2, 3, 4, 5]).
% {[5,4],[1,2,3]}
Tail = queue:tail(Queue).
% {[5,4],[2,3]}
Queue.
% {[5,4],[1,2,3]}
queue:head(Tail).
% 2
queue:to_list(Tail).
% [2,3,4,5]

We can see above that calling queue:tail/1 is not a destructive operation as might happen in other languages, and does indeed leave the original queue intact.

As part of the Okasaki API, which treats a queue as a double ended, queue:tail/1 has a counterpart function queue:liat/1 which will return a new queue with last item removed. queue:liat/1 also has an alias in the Okasaki API of queue:init/1.

queue:liat(Queue).
% {[4],[1,2,3]}
queue:init(Queue).
% {[4],[1,2,3]}
Queue.
% {[5,4],[1,2,3]}

Note that the Erlang documentation also shows that there is an alias queue:lait/1 which it points out should not be used because it is a misspelling.

And because we want to try to break things and see what we can learn, let’s try to call the different tail functions we have covered so far with an empty queue to see what happens.

EmptyQueue = queue:new().
% {[],[]}
queue:tail(EmptyQueue).
% ** exception error: empty
%      in function  queue:drop/1
%         called as queue:drop({[],[]})
queue:liat(EmptyQueue).
% ** exception error: empty
%      in function  queue:drop_r/1
%         called as queue:drop_r({[],[]})
queue:init(EmptyQueue).
% ** exception error: empty
%      in function  queue:drop_r/1
%         called as queue:drop_r({[],[]})

Looks like we get exception errors in queue:drop/1 and queue:drop_r/1 when we call queue:tail/1 and queue:liat/1 respectively.

And when we look at the behavior of queue:drop/1 and queue:drop_r/1 with a queue with items in it, it looks like queue:tail/1 is just an alias for queue:drop/1, and queue:liat/1 and queue:init/1 are just aliases for queue:drop_r/1.

queue:drop(Queue).
% {[5,4],[2,3]}
queue:drop_r(Queue).
{[4],[1,2,3]}

–Proctor

Today’s Erlang Thursday continues to dig into the Okasaki API of Erlang’s queue module, and take a look at queue:head/1.

queue:head/1 takes a queue as it’s first argument, and returns the first item in the queue.

Queue = queue:from_list([1, 2, 3, 4, 5]).
% {[5,4],[1,2,3]}
queue:head(Queue).
% 1
Queue.
% {[5,4],[1,2,3]}

As we can see in the example above, queue:head/1 function does not modify the original queue at all, but just returns the first item.

Because queue:head/1 only returns the value found at the head of the queue, and not a tagged tuple, it raises an error if we try to get the head item from an empty queue.

EmptyQueue = queue:new().
% {[],[]}
queue:head(EmptyQueue).
%** exception error: empty
%     in function  queue:head/1
%        called as queue:head({[],[]})

To be safe, and not get the error raised on an empty queue, the queue module also defines a function queue:is_empty/1 that you can use to check if a queue is empty.

queue:is_empty(EmptyQueue).
% true

Like queue:cons/2, and other functions of the Okasaki API, there is also a function queue:daeh (head backwards), to get the last item from the queue, as well as an alias for queue:daeh/1 of queue:last/1.

queue:daeh(Queue).
% 5
queue:last(Queue).
% 5

Both queue:daeh/1 and queue:last/1 also raise an error of empty if you call them with an empty queue as the argument.

queue:daeh(EmptyQueue).
% ** exception error: empty
%      in function  queue:get_r/1
%         called as queue:get_r({[],[]})
queue:last(EmptyQueue).
% ** exception error: empty
%      in function  queue:get_r/1
%         called as queue:get_r({[],[]})

And if we look at the error that is raised on queue:daeh/1 and queue:last/1, we see that the error is coming from queue:get_r/1 from the Extended API. If we look at the behavior of queue:get_r/1 it looks like queue:tail/1 and queue:daeh/1 are indeed just aliases for queue:get_r/1.

queue:get_r(Queue).
% 5
queue:get_r(EmptyQueue).
% ** exception error: empty
%      in function  queue:get_r/1
%         called as queue:get_r({[],[]})
queue:get_r(Queue).
% 5
Queue.
% {[5,4],[1,2,3]}

–Proctor

Today’s Erlang Thursday digs a little into the queue module, and we cover queue:cons/2 from the Okasaki API.

queue:cons/2 takes a item and a queue, and will return a new queue with the item at the head of the queue.

queue:cons(7, queue:new()).
% {[],[7]}
queue:cons(3, queue:cons(7, queue:new())).
% {[7],[3]}
queue:cons(nil, queue:new()).
% {[],[nil]}
queue:cons(5, queue:from_list([7, 9, 13, 21])).
% {[21],[5,7,9,13]}

If we try to pass a list in to queue:cons/2, we see that it does want a queue, and will not do an implicit conversion of a list to a queue.

queue:cons(5, [1, 2, 3, 4]).
% ** exception error: bad argument
%      in function  queue:in_r/2
%         called as queue:in_r(5,[1,2,3,4])

As the queue is setup to be a double ended queue, the Okasaki API also provides a counter function queue:snoc/2, that adds an item to the tail of the queue passed in. Note that the argument order is swapped between queue:snoc/2 and queue:cons/2; queue:snoc/2 takes the queue as the first argument, and the item to add at the tail as the second argument.

queue:snoc(queue:new(), 5).
% {[5],[]}
queue:snoc(queue:from_list([7]), 5).
% {[5],[7]}
queue:snoc(queue:snoc(queue:new(), 7), 5).
% {[5],[7]}
queue:snoc(queue:from_list([7, 9, 13, 21]), 5).
% {[5,21],[7,9,13]}

–Proctor

Today’s Erlang Thursday is filelib:is_file/1.

filelib:is_file/1 takes a string representing a filename, and returns a true or false depending on if the name refers to a file or directory.

This can be useful if you are having to read from a configuration file and need to ensure that the file or directory exists before trying to process it, so that you can give a nice error message before quitting, instead of just causing a system error to be raised.

filelib:is_file("foo").
% false
filelib:is_file("junk").
% true
filelib:is_file("tmp").
% true
filelib:is_file("tempmp").
% false
filelib:is_file("temp").
% true
filelib:is_file("/usr/local/bin").
% true
filelib:is_file("/usr/local/var").
% true
filelib:is_file("/usr/local/vars").
% false
filelib:is_file(".").
% true
filelib:is_file("..").
% true

filelib:is_file/1 can also take a atom, or even a deeplist(), representing the filename as well.

filelib:is_file(foo).
% false
filelib:is_file(junk).
% true
filelib:is_file(["/usr", ['/local', '/bin']]).
% true

–Proctor