Hacker News Reader

Comment by innguest | Hacker News Reader

Can you say a few things about the parts that don't make sense to you? That would help me identify what beginners struggle with, as I'm developing tutorials for that reason.

View on HN

It's simple: the very concept of the program.

I want to write a program that reads one text file, and outputs another.

Let's say the first file contains a list of emails, one email per line.

The second file should contain the list of email domains in the first file, one line per email domain.

Procedurally, I would simply declare a list, read the file of emails, line by line, split each one on the @ symbol, and if the part on the right was not already on the list, I would add it to the list.

At the end, I would write the list to a new file, one line per item in the list.

How would one do that using functional programming?

Ok so here's one way to solve that problem in FP:

We define what we have first (after all this is mathematics):

EmailList = a list of Email

Email = a string that goes "something" then "@" then "domain"

Now what we want:

DomainList, no duplicates.

Ok so no we're set up. We want a function that takes us from an EmailList to DomainList, as defined above. There are no objects so we simply say the relationships between things. I will introduce the tools we need:

map = takes a function and a list and applies that function to every element of the list, returning a new list.

We use map over EmailList with the function extractDomain which we will write later (it's trivial to do without mutation so I won't show here).

So now we have a list of domains, but there might be duplicates.

So now I have DomainList(with duplicates) and I want DomainList(without duplicates), so I want a function from DomainList to DomainList.

Well, what's the difference between what I have and what I want? What I have has too much, and I want less (ie. the list I have has too many domains (duplicates) and I want fewer (unique)).

filter = takes a list and a function. That function it takes, that you will supply to filter, we'll call f. Function f takes one list element (so filter will call f for every element) and it must return a boolean to mean whether that element should go into the new list, or if it should not go into the list.

So we could use filter to go from a DomainList with too much, to a DomainList with fewer things. However each time our function f is called, we don't know if this function has already been called before with that same domain; and because we don't have state to change a variable to keep a tally, it seems impossible.

So let's approach the problem in a different way. One thing we could do is sort the list, then group adjacent similar items, then map over the list taking the first element of each item. But we won't do that.

We need something more generic than filter. Let's look at fold.

fold = takes a list, a function f, and a starting point z (that we call 'zero'). For each element of the list, it calls your supplied function f with the current element and the zero; but then, it would be useless because it would be the same zero all the time. So what fold does, to be useful, is that whatever the result of calling your function f with a list item and the zero is, THAT value (so the value the call to yourFunctionF(list_item, zero) returns) will be the next 'zero'. So now we have a little machine called fold that can thread something we have through its inner mechanism and play along with us.

Using that we can say the zero is the list of elements we've seen so far.

So now our DomainList -> DomainList function will be a fold. That fold will take a the DomainList we have, and a zero that will be the empty list (to start with!) and a function f. That function f will simply check if the item is inside zero. If it is, then simply return zero (because that will be the zero for the next call to f!); if it's not, then return a new zero with that item added to it.

Now we've achieved the goal without any mutation (ie. without us talking/concerning ourselves with any mutation. of course there's lots of mutation going on in RAM but the point is not to eliminate that!)

Does that help?

Sadly, no.

It's like I asked for a tuna sandwich and you explained how to build the engine of the fishing boat to go catch the tuna off the coast of Baja.

I feel like I need a masters in computer science to understand what you wrote.

let me see:

# Python:

domains = []

emails = open("file_with_emails.txt","r").readlines()

for email in emails:

____domain = email.split("@")[1]

____if domain not in domains:

________domains.append(domain)

out = open("file_with_domains.txt","w")

for domain in domains:

____out.write(domain)

out.close()

input:

joe@msn.com

mike@aol.com

tim@aol.com

sam@hotmail.com

output:

msn.com

aol.com

hotmail.com

Simple no?

I think the main difficulty in converting your example to a functional style is how to express the idea of a for loop which builds up a result as it goes along, without using a mutable variable to store this result. Here's an attempt to explain how that the ideas in the parent are helpful in solving that problem.

You can think of the body of a for loop in python as the body of a function. In that case, a for loop is like the built-in map function, which applies that function to every element of the list. So convert your for loop into:

  def body(email):
    domain = email.split("@")[1]
    if domain not in domains:
        domains.append(domain)

And instead of a for loop we can use the standard function, 'map'.

  domains = []
  map(body, emails)

Now, obviously the data here isn't immutable. But what if, instead of changing 'domains' every time the function is called, we passed in the current value of 'domains', and returned a changed value, like so:

  def body(domains, email):
    domain = email.split("@")[1]
    if domain not in domains:
        return domains + [domain]
    else:
      return domains

Then, we could apply this function to each element of the list in turn, passing the current list of domains at each stage to the body. This is the standard function 'reduce' in Python (which the parent calls by its other common name, 'fold'):

  domains = reduce(body, emails, [])

You could think of 'reduce' in python being implemented like:

  def reduce(func, l, currentResult):
    for item in list:
      currentResult = func(currentResult, item)
    return currentResult

Or, it could also be implemented recursively, which means it wouldn't need to use mutation internally:

  def reduce(func, l, currentValue):
    if len(l) == 0:
      return currentValue
    else:
      return reduce(func, l[1:], func(currentValue, l[0]))

Many for loops that build up a result can be expressed instead using 'reduce', so reduce is one of the most important building blocks of functional programming.

Except you'd never write it like that in idiomatic Python. Your reduce's repeated list copying/appending/searching kills performance. Instead you would do something like this:

domains = set( email.split('@')[-1] for email in open(path) )

He's pretending python compiles to something sane. FP spoils you with great compilers.

This is a great explanation and I hope it will help your parent commenter realize that, while different and not trivial, this stuff really isn't dark magic and really doesn't require a master's degree level of study to grok.

I think my comment is going to be that, from reading the parent, I understand that functional programming moves the code to the data and not the data through the code.

I can't do the mental gymnastics to think about the code that way.

When I think about the purpose of the code, the result of the code, before the code has been written, I do this by "compiling and running" in my head. Of course, there's no actual compiling. There's just thinking.

When I reason about the code, either code I'm going to write, code I wrote, or code other people wrote, I execute the code in my head.

I'm currently building a web-scraping system, to look information on partner web site. I'm using python 3, selenium, pyodbc to sql server. I'm also developing the same in C# (3.5) using the webbrowser component in systems.forms. It's got a lot of moving parts, lots of languages involved. I read the documentation for the tools, then I assemble in my head, essentially "running the code" in my head, and then, once all the edge cases are dealt with (are there iframes, popups, ajax async calls, flash and pdfs) then I design on paper, with boxes, and then, later, later, if it all works in my head, then I code it.

Can't do that if I can't reason in my head about what the program is going to do, exactly.

Functional Programming, for me, does not fit in my mental model, so I can't use it, regardless of actual implementation.

This is partially because you're shoe horning functional ideas into an imperative language. When you have no choice but to use maps and folds you quickly build up mental models of how to do what you normally do with for loops: accumulate (fold), transform (map), or generate (zipWith).

The problem with your approach is it produces this mess:

http://qt-project.org/doc/qt-4.8/widgets-analogclock.html

When you could instead say just what you mean in functional programming:

http://elm-lang.org/edit/examples/Intermediate/Clock.elm

The most important skill for a programmer is to be able to learn new things. Especially when they're there to help you.

In functional style, but still in Python (given that python method calls are equivalent to function calls with an additional first argument of the receiver object, and indexing is equivalent to a method call) -- this uses mutable objects, but doesn't actually rely on mutating them:

  addEmail = lambda |doms,email| doms.union([email.split("@")[1]])
  domains = reduce(set(),addEmail,open("file_with_emails.txt","r")))
  open("file_with_domains.txt","w").writelines(domains)

(Loses order because of use of set for deduplication; you could do it with a list and keep order, but then addEmail becomes more complex, and I don't think its strictly necessary to illustrate the general process. Also, its not clear to me that order-preservation is really part of the intended function here or just an artifact of the implementation. Note that this could be a one-liner, its just split up into three lines with two as assignments for readability.)

And, more how I'd really write it in Python (which is also functional, though perhaps less obviously so, and leverages Python set comprehensions):

  domains = { email.split("@")[1] for email in open("file_with_emails.txt","r") }
  open("file_with_domains.txt","w").writelines(domains)

> this uses mutable objects, but doesn't actually rely on mutating them

That is actually a really good compromise and a style I tend to stick to when coding Ruby/Rails.

That right there, that's beautiful. I love list comprehensions.

That's actually not simple at all because it assumes an implementation, that is, a machine with RAM that changes.

For instance, what does = mean between domain and email.split ? Who is equal to who? That question is a question that students sometimes have. You have to explain that Time is implicit in the code, and that an equal sign works by making the thing on the left equal to what the thing on the right was just before this line. So now there's a concept of Time and that's how things start to get very complicated, because it is implicit in your code.

Then, what does ".append" mean? I mean, you call append, but now you don't assign the result to any variable? And what would it mean if you said domains = domains.append(domain), then we really need to have a talk about the hidden Time.

So it only seems simple because it's familiar to you; so in fact I believe it's not simple at all.

But this I believe it's simple, and my fishing boat engine above would've benefited from this:

https://www.fpcomplete.com/tutorial-preview/4217/4k7kq6jGUE

If you look at that code (you can also click play to run it) and then look at the explanation again, could you please tell me what doesn't seem simple?

Edit: let's not forget your Python example uses a map, disguised as a for loop. That for is a keyword, but backstage it's just map where email is the element, emails is the list, and everything you write inside that scope is the function that gets passed the element each time (except in your case the function (i.e. the loop body) can also see the whole list, which is prone to bugs).

"Edit: let's not forget your Python example uses a map, disguised as a for loop"

Mmmm, really? A map? Like Google maps? Like a paper map? unfamiliar terminology.

Seriously, I learned how to use for loops in 1984. Been using them ever since. Maybe that's the problem. Too old to learn new tricks.

It's not unfamiliar, you got it right, the map I'm talking about is exactly like that maps you described, in that they both contain directions (all the possible origin-destination relationships between all the places) and you can draw arrows from one place to another (thereby defining a "route" that represents the act of starting to walk from point A and arriving at point B). If you cared to learn you would benefit a lot from it.

Oh, but the moral of the story is that because the computer understands those maps, then I can simply tell it what I have (point A, origin) and what I want (point B, destination) without telling it how to do it. Then the computer goes and writes that code for me! The same code you're now still writing manually. Because you don't want to learn a new "trick". :)

That still made no sense, sorry.

> Mmmm, really? A map? Like Google maps? Like a paper map? unfamiliar terminology.

No, a map like the Python built-in function "map". Though, really, the for loop in your Python sample isn't a map done as a for loop, its a reduce done as a for loop. (Again, like the Python built-in "reduce".)

You can learn these tricks, but it's ok if you don't want to, as long as you don't mind that many of us like doing things this way, and recognize that you may well run into these concepts in other peoples' code at some point.

Thanks. I looked at the code you provided. it makes still very little sense to me.

You're right though that my using python language features like lists and file open and loops is like function, but I understand those, so I can use them.

Also, a machine with RAM that changes. Well, yes, and files that change too. I'm completely ok with that.

For completeness, I should add that I don't know what "reduce" means in this context.

https://docs.python.org/2/library/functions.html#reduce

Reduce (also frequently called "fold") turns a list of items into a single item (of maybe the same type or maybe a different type). It does this based on a function that tells you how to update that single item as it looks at each list item in turn.

For instance:

    def fn(a,b):
        return str(b) + a + str(b)

    reduce(fn, [1,2,3], "0")

That says:

    Start with "0" (we call this the accumulator value)
    Read the first element of the list (1)
    Pass "0" and 1 to fn
        Turn 1 into "1"
        Stick it on the front and back of "0"
        Return "101".
    Use "101" as our new accumulator value.

    Read the next element of the list (2)
    Pass "101" and 2 to fn
        Turn 2 into "2"
        Stick it on the front and back of "101"
        Return "21012".
    Use "21012" as our new accumulator value.

    Read the next element of the list (3)
    Pass "21012" and 3 to fn
        Turn 3 into "3"
        Stick it on the front and back of "21012"
        Return "3210123".
    Use "3210123" as our new accumulator value.

    Notice that we've reached the end of the list, return our latest accumulator value.

Using clojure:

  (ns my.namespace
    (:require [clojure.string :as str]))

  (->> (str/split (slurp "/home/deadghost/fake-emails") #"\n")
       (map #(second (str/split % #"@")))
       set
       (str/join "\n")
       (spit "/home/deadghost/new-file"))

Read entire file, split by newlines into a vector, split each element by @ and take the second part of each split, convert to set to remove duplicates, join set elements with newline and spit to new file.

Clear as mud?

One way in P6:

    say ~ m/ '@' (.*) / for lines

Ignoring the regex for now (the `/.../` bit), this reads as say (`say`) the string (`~`) that matches (`m`) for each of (`for`) the lines (`lines`).

Note that lists (`lines` returns a list) are lazy by default in P6. So the above code will start producing results immediately and continue without exhausting RAM even if the input is infinite.

The `/ ... /` bit above is a "regex". It means match the symbol '@' and return all the following characters of that line. P6 regexes are far more powerful than P5 regexes. P6 regexes can work together to comprise arbitrarily complex parsing grammars. The main P6 compiler, Rakudo, parses input source code using a P6 grammar.

There are of course many more ways:

     say lines.map: { m/ '@' /; $/.postmatch ~ "\n" }

In this instance `lines` is treated as an "object" (a `List` in this case) on which the `map` "method" is called. `map` calls the block of code (the `{...}` bit) against each element in its invocant, ie against each line. The block of code matches a '@' and returns whatever follows it ("postmatch") with a newline appended. (`$/` refers to "the match object"; it's one of three symbolically named variables in P6 as against the dozens in Perl 5.)

Wow, that looks like what was trying to come out of Perl. Very cool snippet!

By the way, for those who think programs like that are too simplistic, and not a good showcase for all the FP goodness, maybe that's part of the problem. I work in the corporation, and I we do simple things.

Reply on news.ycombinator.com