Core Elixir: List.foldl/3 and List.foldr/3

Before Elixir, I never dealt with folding functions. Now, I have a foldl and a foldr function to wrap my head around. It seemed so simple at first, but I had to bend my mind around this one for a couple of reasons. Let’s try to walk through these two functions and see what we can learn.

Digging Not Too Deep

Before we go too far with this, let’s jump to the end: List.foldl and List.foldr are wrappers for Erlang functions :lists.foldl and :lists.foldr. Elixir rearranges the parameter order and that’s it.

I mention this now because the Erlang documentation helps out with explaining these functions shortly.

What Are We Folding Here?

List.foldl takes three arguments: a list, an accumulator, and a function. The accumulator doubles as your starting point.

A fold is basically a reduction. It takes a list, processes every item of it through a function, and returns a single value.

In fact, the Elixir Enum.reduce/3 function is also a wrapper for Erlang’s :lists.foldl/3 function.

List.foldl/3 applies the function to each element in the list, from left to right. Let me repeat it so it doesn’t get too confusing: foldl runs from left to right.

It’s a bit confusing in the Elixir documention, which says that the foldl function

Folds (reduces) the given list to the left with a function.

To my mind, that would mean it runs right to left. The Erlang documentation defines foldr as being “Like foldl/3, but the list is traversed from right to left.”

I think the Erlang docs use the preposition better.

I’ve read other explanations of the two folds that rely on the “from” preposition to explain it better: foldl works from the left, while foldr works its way from the right.

Does It Matter?

A lot of the times, it won’t matter whether you go from the left or from the right. If you’re just summing up or even multiplying together the values in the list, for example, you’ll get the same answer either way. You may remember the “commutative property” from your childhood. That applies here.

On the other hand, when order counts, there’s a big difference between left and right. Take subtraction, for one easy example that’s also used in the Elixir docs:

  • 1-2-3-4 is -8.
  • 4-3-2-1 is a mere -2.

Fold statements are a little more complex than that, though, as they can use the accumulator value to start at a different place, or even in the calculations along the way. Once you try to do something like f(x) -> x - acc, you have a new kettle of fish.

Also keep in mind that the accumulator is mandatory in your fold statements in Erlang and, thus, Elixir. You don’t need to use it, but you must include it.

Start the accumulator at 0 and let’s foldl the list of the first four numbers and see where we go:

x  - acc = new_acc
------------------
1  - 0   = 1
2  - 1   = 1
3  - 1   = 2
4  - 2   = 2

Reverse that and let’s subtract from the right with foldr:

x - acc = new_acc
-----------------
4 - 0   = 4
3 - 4   = -1
2 - -1  = 3
1 - 3   = -2

At each step of the way, reduce keeps track of which item on the list it’s at, and what the value of the accumulator is.

The reduce function itself can be a complicated piece of machinery, and it’s one that powers much of Enum. Someday, I hope to get around to figuring out how it works in graphic detail.

When in doubt, foldl

Why? It’s tail recursive. This makes sense. You’re iterating over a list. How many times have we seen now that lists work best when processed from left to right? I suspect it has something to do with that. And if it doesn’t — well, it’s an easy way to remember it, at least.

For more detail on this, check out this HaskellWiki article.

Heavier Reading

This whitepaper was a pretty interesting-looking appreciation of using a fold over recursion:

…we show that even though the pattern of recursion encapsulated by fold is simple, in a language with tuples and functions as first-class values the fold operator has greater expressive power than might first be expected.

Not that I understand a word of it.

If you have any comments, questions, complaints, criticisms, or corrections, catch me on Twitter, @AugieDB. Or make a pull request on Github! That Twitter handle and Github ID is the same as my GMail account, if you want to deal with it more quietly. I want these articles to be factually correct and will update them as necessary.

(15)

Nostalgia Coding

I came across this wonderful page tonight that has PDF versions of the classic books from the 80s written to teach kids how to code using sample games. The code was mostly the same across the Commodore, Atari, and other computers of the time.

I had a few books like this growing up, and can remember having a couple of these specifically, at one point or another. (Maybe a library loan?)

This is the first block of Commodore 64 BASIC I’ve looked at in a while, and I almost laugh when I see some of this stuff and how we used to do things. (And some things were so close to how we do them today, with only minor differences.) For example:

  1. Line numbers.
  2. GOSUB to line numbers instead of subroutine names. (I don’t remember this at all, but typing “GOS” and holding the shift key down for that last letter was a shorter version of “GOSUB” that worked. Wow.)
  3. Variable names where the sigil ($) came after the variable name, not before.
  4. Tests of equality with a single equal sign instead of double. (This is a mistake that still catches programmers today.)
  5. Separating commands on a single line with a colon instead of a semi-colon.
  6. The IF statements! My goodness, the IF statements! I’m looking at one program where 115 lines in a row are IF statements. Functionally, I believe they’re IF THEN ELSE, but there was no ELSE keyword, so you wound up checking them all, anyway.
  7. Looks like all variables are globals, and most are named with single alphabetical characters.
  8. PRINT CHR$(147) clears the screen. That’s muscle memory. I may not have typed it in nearly 30 years, but I recognized it instantly when I saw it in the code.
  9. Courier looks like a futuristic font by comparison to what these books show the code as. This code looks almost like it came straight off the dot matrix printers where you needed to tear the sprockets off the side of the pages…
  10. “LET” was not necessary on the C=64, which is why it looks so unusual to me here. Today, “LET” is the keyword you use in Swift to define a constant.

In twenty years, I’m sure I’ll look back at today’s Ruby or Perl or Swift and laugh at it, too. C’est la vie.

Core Elixir Follow-Up: List.delete_all

Three updates from the List.delete_all post a couple weeks back:

Naming is Hard

Yeah, that’s a fair point. A better name for the function might be List.delete_all_of, maybe? (“Delete all of the 5s from this list.”) It’s tough to be descriptive and terse at the same time. Nobody wants to type List.delete_all_values_from_this_list_that_equal_this. We’re not Objective-C with XCode to autocomplete all of that for us.

I poke fun of Objective-C sometimes, but I admit that it’s helped me to make lengthier and more descriptive variable names that I’ve appreciated more than once six months later… I do, however, use Ruby’s underscore syntax over CamelCase to make those variable and function names. In Perl.

I’m a heretic.

Refactoring

I had a pull request from Daniel Garcia, who made a smart observation about my original List.delete_all code. Here’s what I started with:

  def delete_all(list, value) do
    delete_all(list, value, [] ) |> Enum.reverse
  end

  defp delete_all([ h | [] ], value, end_list) when h === value do
    end_list
  end

  defp delete_all([ h | [] ], _value, end_list) do
    [h|end_list]
  end

  defp delete_all([h|t], value, end_list) when h === value do
    delete_all(t, value, end_list)
  end

  defp delete_all([h|t], value, end_list) do
    delete_all(t, value, [h|end_list])
  end

I didn’t think too much about it. I got something to work and stopped there, because I knew I’d be working on the problem in different styles. Still, there’s an obvious pattern matching issue here that I should have noticed. Take a look at these two functions, in particular:

  defp delete_all([ h | [] ], value, end_list) when h === value do
  defp delete_all([ h | t  ], value, end_list) when h === value do

You can pattern match inside the arguments. If you’re looking for the case where h and value are the same thing, you don’t need to put that in the guard clause. You can match it inside the argument list:

  defp delete_all([ value | [] ], value, end_list) do
  defp delete_all([ value | t  ], value, end_list) do

Now, look at that and realize that in one major case, it’s the same function. When the tail is an empty list, the first version will be triggered instead of the second. Can we combined those two into one? Yes, if the base case (the one that returns the final results) is rewritten to look for just an empty list.

Those middle three functions can then be combined down into two:

  def delete_all(list, value) do
    delete_all(list, value, []) |> Enum.reverse
  end

  defp delete_all([], value, end_list) do
    end_list
  end

  defp delete_all([value|t], value, end_list) do
    delete_all(t, value, end_list)
  end

  defp delete_all([h|t], value, end_list) do
    delete_all(t, value, [h|end_list])
  end

Your variants of the private function handle the cases where (1) the value is the same as the head, (2) the two are different, and (3) you have an empty list. That’s a lot more straight forward and obvious than my initial version was, where you had alternate versions of the same function depending on a guard statement that was redundant and the base case was one step removed from the end of the actual list. It just plain old makes more sense.

Reduce It Again

I wrote up a basic reduce function to do the same thing, admitting that I thought it might be done cleaner somehow.

In jumped Kash Nouroozi with a gist to change my function —

def delete_all(collection, value) do
  Enum.reduce( collection, [ ], fn(x, acc) ->
    case x !== value do
      true  -> [x | acc]   # Not the value, add it to the list
      false -> acc         # Matches the value, so don't add it
    end
  end)  |> Enum.reverse
end

— to something more elegant using foldr that doesn’t even need the reverse at the end:

def delete_all(collection, value) when is_list(collection) do
  List.foldr collection, [ ], fn
    x, acc when x == value ->
      acc
    x, acc ->
      [x|acc]
  end
end

I understand this new bit of code, but I’m afraid explaining it in graphic detail will have to wait for another day. I am working on a foldl/foldr edition of Core Elixir for some point in the future. So stay tuned there.

Thanks once again to Daniel and Kash for their contributions/pull requests/gists.

If you have any comments, questions, complaints, criticisms, or corrections, catch me on Twitter, @AugieDB. Or make a pull request on Github! That Twitter handle and Github ID is the same as my GMail account, if you want to deal with it more quietly. I want these articles to be factually correct and will update them as necessary.

(14)

Core Elixir: File.cd and Friends

We’ve talked briefly about the File library in the past when we discussed File.stat and, of course and not confusingly, File.Stat.

This week, we return to the File library to look at how we might change the current working directory in Elixir. It’s pretty straightforward, but there’s one neat twist to it.

Change Your Directory

There might come a time in your code where you will want to change your working directory. File.cwd will tell you what that directory currently is, but it is File.cd/1 that will set you in a different directory. You tell it the directory to change to, and it will either return an :ok, or an :error with the appropriate POSIX-compliant error message.

More succinctly, the official Elixir documentation says this:

cd(Path.t) :: :ok | {:error, posix}

Same thing.

Here it is in action:

iex> File.cd("/tmp")
:ok

iex> File.cwd
{:ok, "/tmp"}

Now, since this is Core Elixir, let’s look at the implementation details.

Yup, It’s an Erlang Wrapper

The first clue that we’re wrapping Erlang here is that the source code uses the alias F. Looking at the top of the file, we see where that goes:

 alias :file, as: F

Here’s the code, then:

  def cd(path) do
    F.set_cwd(IO.chardata_to_string(path))
  end

:file.set_cwd is the Erlang command to set the current working directory. The only trick is that you have to stringify the path name so that Erlang will deal with it. That’s not so much of a trick as it is Elixir 101 at this point.

As usual, there is also the cd! version of the function. Instead of just returning the error message and carrying on its merry way, it blows the whole thing up:

iex> File.cd("/tmp/this_directory_does_not_exist")
{:error, :enoent}

iex> File.cd!("/tmp/this_directory_does_not_exist")
** (File.Error) could not set current working directory to /tmp/this_directory_does_not_exist: no such file or directory
    (elixir) lib/file.ex:1087: File.cd!/1

That latter error message appears in all red text, by the way, in case you questioned just how serious it was.

The source for this is, as you might expect, fairly similar to File.cd, but with an extra layer added on. (See lines 3 – 7, in particular.)

  def cd!(path) do
    path = IO.chardata_to_string(path)
    case F.set_cwd(path) do
      :ok -> :ok
      {:error, reason} ->
          raise File.Error, reason: reason, action: "set current working directory to", path: path
    end
  end

The source stringifies the path name first, then runs F.set_cwd (which is also basically File.cd now) and pattern matches the results. If all is good, it returns :ok. If something went horribly wrong, it pattern matches on the :error, prints out the reason , and blows stuff up.

It’s just a case statement, though. It’s nothing we haven’t seen before.

##One More Thing…

There’s a File.cd!/2 which I find the most fascinating function of all. This one takes a directory and a function. It changes into that directory, runs that function, and then resets your current working directory to where it was before you ran the command.

That’s pretty neat.

iex> File.cwd
{:ok, "/home/vagrant/augiedb/elixir"}

iex> File.ls
{:ok,
 [".DS_Store", ".iex",  "card_game", "cards",  "cards.exs", "chapter13",  "dose",   "elixir", "Elixir.Card.beam", "Elixir.CardPoints.beam", "Elixir.Chip.beam",
  "Elixir.Factorial.beam", "Elixir.Gcd.beam", "Elixir.Guard.beam",
"factorial1.exs", "filechange", ...]}

iex> File.cd!("fileutils", fn() -> File.ls end)
{:ok,
 [".git", ".gitignore", "Augie", "config", "lib", "mix.exs", "README.md",
  "t.txt", "test", "_build"]}

iex> File.cwd
{:ok, "/home/vagrant/augiedb/elixir"}

You can see that we end in the same directory as we started, despite using a cd command in the middle there. You can also see that there are two completely different directory listings given.

Let’s see how it works:

  def cd!(path, function) do
    old = cwd!
    cd!(path)
    try do
      function.()
    after
      cd!(old)
    end
  end

I almost laughed when I saw this code. It just strikes me as funny how terse it is. It’s the most succinct code I’ve seen in Elixir to date. Nothing fancy. It’s like a baby learning to speak. Everything looks like a two word sentence.

“Mama. Dada. Try do.”

That’s mostly because we’re at a slightly higher level of abstraction here. This is File.cd!/2 using File.cd/1 to do the work of changing directories. Much like with File.cd!/1 using File.cd/1, you don’t need to repeat all that code again for File.cd!/2. It’s already done for you; use it. Plus, the function that File.cd!/2 is running is neatly saved in a variable, function, so you don’t have to look at all that code. It’s all building up on itself.

Here’s how it works:

File.cd!/2 first grabs the current working directory and saves it so it knows where to go back to later.

Then, it changes to the new directory, failing out if that doesn’t work.

Next, it runs the function before changing back to the original directory, no matter what. The try do/after construction just means that even if the first statement fails, the statement in the after section will still run.

Note that there is no File.cd/2 (without the !). This is code that will either work, or blow up. There is no half measure on this one.

##One Last Piece of Trivia

File.cd and all of its variant arities aren’t used anywhere else in the File library.

Hey, they call it “trivia” for a reason…

If you have any comments, questions, complaints, criticisms, or corrections, catch me on Twitter, @AugieDB. Or make a pull request on Github! That Twitter handle and Github ID is the same as my GMail account, if you want to deal with it more quietly. I want these articles to be factually correct and will update them as necessary.

(13)

Death to Tech Blogs?

From Jean-Louis Gassée’s “Monday Note” blog comes this gem:

Too many sites are just echo chambers, they rewrite news releases,
add strong adjectives and adverbs, and a bit of spin.

In the current talk of ad blocking and punishing the kinds of websites that weigh down our browsers and network connections with far too many Javascript inserts, this is the one ugly truth that’s going overlooked.

There are too many copycat blogs and websites that do no real new reporting. They’re just clickbait that copies everyone else.

So if a bunch of sites go under, is that really a bad thing? Not for those sites who provide nothing new…

The Power Mac G5

Boy, this article couldn’t have been much better timed. It’s a look back at the Power Mac G5 desktop computer, which was my first Apple computer. I wish they still made it, because I’d buy another today. The fans were incredibly loud, and I had to upgrade from mine when one of them basically died, but I liked how easy it was to add or remove things on the inside. Alas, the Pentium PC chip proved to be the ultimate limiting factor…

Also see: