Help with anagram example

I’m having trouble understanding how the Anagram example in chapter 3 works exactly. (Page 54.) I’ve run the example and it works just like in the book. So I know I’m misunderstanding something. That’s really bugging me because up until that point I was doing just fine with the material.

I haven’t had problems in the past with understanding list comprehensions, and I’m generally ok with recursion, but the combination in Erlang is confusing the heck out of me. It’s even hard for me to phrase the question, so please bear with me.

When I first looked over the code I expected 3 permutations. When I saw the result was 6 permutations I was confused. It took me a long time to understand that, in the case of perms(“123”), the top level perms call somehow considers H as “1” twice while allowing the “inner” perms call to evaluate to emit both of it’s list values for T (which will be “23” and “32”).

My question is, how does H “know” to stay anchored to a value of “1” while T takes on those two different values so that perms will eventually emit both “123” and “132”?

Am I missing something really basic, or is this as mind bending as it seems?

Thanks,

Matt

Matt,

I am also learning Erlang and I blogged about the perms function, so please check it out and maybe that will help you understand what is going on (or at least what I think is going on).

I basically used substitution to fully expand out the function calls/recursion. Try evaluating the following in an Erlang session:

You will get:

[2,3,4,11,12,13,21,22,23]

So in effect, you are right that X “anchors” itself at 1 while Y goes through 1, 2 and 3.

Hi Peter.

Thanks! Your blog posts cover everything I went through last night. In fact, your last expansion is actually almost identical to what I worked out in my text editor. So unfortunately you’ve gone right up to the point where I got confused. Your post did help me think more about the problem though, and I’ve made good progress.

Thoughts I had tonight:

Why haven’t I run into this problem with list comprehensions in other languages?

I realized that every example of list comprehensions I had seen was trivial, with a single dependent variable. I had never seen a multi-variable list comprehension before. My model for list comprehension has always been equivalent to a single foreach loop. Which isn’t correct beyond trivial cases.

What does this look like in Lisp?

I don’t use Lisp but it is the only functional language I’ve had any exposure to. Google led me to an article on list comprehensions where a complex comprehension is rewritten with nested for loops. That seems to be a model that actually works for me.

What does a multi-variable list comprehension like perms() output if you give it several explicit lists?

Sure enough, after thinking in terms of nested for loops, when I coded a simple 3 variable list comprehension in Erlang the output matched my prediction. So I feel I’m back on solid footing again.

But I’m still stuck with the problem of the syntactic sugar obscuring behavior. I don’t see how I am supposed to comprehend (pardon the pun) this behavior by looking at the code. Certainly in the future I’ll know what’s going on, hopefully. But how many people look at something like this (especially those of us from the imperative world) and just give up?

I think if the recursion hadn’t been in the example I probably wouldn’t have stumbled so hard. An example (like you posted in your reply Peter) with two explicitly different lists would not have caused the confusion. I can’t fault a tough example though. I learned a lot.

So thanks again, and sorry for the novel-length reply!!

Matt

But I’m still stuck with the problem of the syntactic sugar obscuring behavior. I don’t see how I am supposed to comprehend (pardon the pun) this behavior by looking at the code. Certainly in the future I’ll know what’s going on, hopefully. But how many people look at something like this (especially those of us from the imperative world) and just give up?

A good question to ask. I did not know what to expect coming out of that code until I ran it and reverse engineered how it should work. I also find the comparison to nested for loops helpful. Maybe, as you suggest, this was just a “tough love” approach to get us to learn on our own…

After some time away I think it’s more likely author perspective: Joe is an fp guy. If another fp guy saw this example he would probably yawn and move on. Similarly there are some awkward imperative examples in the book. So it’s just a different POV and there are some corner cases where that difference is confusing.

Btw, I later saw a footnote in SICP that explains that map() in Scheme works this same way with multiple lists. Perhaps if I had actually read SICP maybe I would have yawned too. :)