Explaining Functional Programming to Eight-Year-Olds | Hacker News Reader

Explaining Functional Programming to Eight-Year-Olds

prog21.dadgum.com

38 pointsekiru10 comments

I think the difficulty in explaining this is that you have to "inject" a value in at the start (indeed the Smalltalk equivalent is called inject:). Without injection, the function amounts to:

   a1 op a2 op a3 op ... op an

where op is some binary operation. Executing op can either start from the left or right, so you have a left-fold or right-fold respectively. In Unify ATM I've defined the functions:

   (fold iv ar f)
   (foldr ar iv f)
   (foldn ar f)
   (foldrn ar f)

Where: -r = right fold, -n = no injected value ar = an array (Unify uses arrays not lists) f = a function taking 2 arguments iv = an injection value

Although it might be better to cut the functions down to 2, and make iv an optional argument:

   (fold f ar vararg iv)
   (foldr f ar vararg iv)

Alternately I could use 'reduce' for the injectionless, and 'inject' for the injectionful versions of the function.

left-fold and right-fold are not the only two. If you're dealing with commutative and associative operators, you can group them up in a binary (or n-ary) hierarchy for parallel execution as well ... and is there a name for that?

map is obviously parallelized in a purely functional language. My opinion is that fold, otoh, is better limited to use with commutative and associative operators for clarity and transparent parallelization. That way, you don't have to think about whether you need to use a left or a right fold, or indeed a parellel fold.

Other "iterations" can be expressed using explicit recursion using an accumulator ... again, for clarity.

> left-fold and right-fold are not the only two. If you're dealing with commutative and associative operators, you can group them up in a binary (or n-ary) hierarchy for parallel execution as well

Unify isn't a functional language, nor do I particularly care about execution speed at present -- I'm writing it to test a concept I call Viewability. Having said that, the next version of Unify may well be more functional than the current one, and if so it could havre a way of tagging operators as commutative or associative, so the compiler can produce efficient code.

> map is obviously parallelized in a purely functional language

It's obviously parallelisable. It can only actually be parallelised if you have more than one CPU.

> My opinion is that fold, otoh, is better limited to use with commutative and associative operators for clarity and transparent parallelization.

I think it makes more sense in those cases, yes.

In fact you could make fold a method with multiple implementations depending on the type of function, e.g:

   /* version that works with any function */
   (fold ((Function f) ar) ...)

   /* version that requires a function that is associative
      and commutative, and can do appropriate optimisations */
   (fold ((AssComFunction f) ar) ...)

and is there a name for that?

In Clojure its preduce, I believe (for parallel reduce; in Intel Threading Building Blocks its called parallel_reduce).

In k, a similar operation is called "peach", for "parallel each", though (as with J and APL) most of the operations already have an implicit map/loop built-in.

I'm pretty sure I wasn't smart enough to understand that when I was eight years old.

You might surprise yourself.

I am not a programmer of any singular talent, but I understood foldl when I was 9. I understood it in terms of Pascal and iteration, but the knowledge was there.

What really bothers me about this article is that at no point are there actually any eight year-olds. It's one thing to say "An eight year-old could understand this", and another to have a loose transcript of an actual conversation, à la "Explaining REST to my Wife" ( http://tomayko.com/writings/rest-to-my-wife ) or "The Socratic Method", where the author teaches binary to third graders ( http://www.garlikov.com/Soc_Meth.html )

The thing about folds is that they build upon more fundamental concepts. If you understand recursion — which you must if you want to do FP — they're not too weird. But most people have trouble thinking recursively, so the simple implementation of a fold is confusing.

I think the name doesn't help either. People understand "reduce" more intuitively than "fold".

insert is fold, just underspecified (what happens on 1- or 0-element lists? in what direction does the operator associate?). The only difference in comprehensibility is in the language being used to describe the operation - which is certainly a good thing to take note of if you're trying to teach FP, but it's not as if the operation itself is somehow less-comprehensible.

Reply on news.ycombinator.com