Experiments in Functional Programming


#1

I’ve been reading about functional programming lately. It’s quite alluring, but it often seems impractical. Particularly the “no statements” thing. I had some time at work today, so I tried to write a generic functional utility to replace loops. Yes, all loops.

const loop = (
    int = 0,
    test = x => x < 0,
    next = (x, y) => [...y, x],
    iter = x => x + 1,
    acc = [],
    data = null
  ) => test(int, acc, data) ?
  loop(
    iter(int, acc, data),
    test,
    next,
    iter,
    next(int, acc, data),
    data
  ) :
  acc;

For a simple case using the default parameters, it’s actually kind of elegant.

//exhibit a

const arr = [];

for (let x = 0; x < 3; x++) {
  arr.push(x);
}

arr; //[0, 1, 2]

//exhibit b

loop(0, x => x < 3); //[0, 1, 2]

It’s slightly less elegant, but still useful, for more interesting cases.

//exhibit b

const fizzBuzz = () => loop(
  1,
  x => x <= 100,
  (x, y) => [
    ...y,
    x % 3 === 0 && x % 5 === 0 ? "FizzBuzz" :
    x % 3 === 0 ? "Fizz" :
    x % 5 === 0 ? "Buzz" :
    x
  ]
);

fizzBuzz(); //[1, 2, "Fizz"...]

//exhibit c

const ticTacToe = () => loop(
  0,
  x => x < 3,
  (x, y) => [...y, loop(
    0,
    x => x < 3,
    (x, y) => [...y, 0]
  )]
);

ticTacToe(); /*[
                 [0, 0, 0],
                 [0, 0, 0],
                 [0, 0, 0]
               ]*/

Just for fun, because this is apparently what I do for fun, I decided to try something more complex. This is a utility function from my dungeon crawler game.

//exhibit e

const findRange = (yx, bounds = [2, 4, 6, 6, 7, 7, 8, 8, 8, 8, 8, 7, 7, 6, 6, 4, 2]) => {

  //get radius around index

  const range = [];
  const ymax = (bounds.length - 1) / 2;

  for (let i = -ymax; i < ymax + 1; i++) {

    const xmax = bounds[i + ymax];

    for (let j = -xmax; j < xmax + 1; j++) {
      range.push([yx[0] + i, yx[1] + j]);
    }

  }

  return range;

};

findRange([21, 42]); /*[
                         [13, 40],
                         [13, 41],
                         [13, 42]...
                       ]*/

//exhibit f

const findRange = (yx, bounds = [2, 4, 6, 6, 7, 7, 8, 8, 8, 8, 8, 7, 7, 6, 6, 4, 2]) => loop(

  //get radius around index

  (-((bounds.length - 1) / 2)),
  (x, y, z) => x < z.ymax + 1,
  (x, y, z) => loop(
    (-z.bounds[x + z.ymax]),
    (x, y, z) => x < z.xmax + 1,
    (x, y, z) => [...y, [z.yx[0] + z.x, z.yx[1] + x]],
    void 0,
    y,
    Object.assign(z, {
      x: x,
      xmax: z.bounds[x + z.ymax]
    })
  ),
  void 0,
  void 0,
  ({
    yx,
    bounds,
    ymax: (bounds.length - 1) / 2
  })

);

findRange([21, 42]); /*[
                         [13, 40],
                         [13, 41],
                         [13, 42]...
                       ]*/

God, that’s awful. It’s also about 50 times slower than the original. It’s only 5 times slower using Array.prototype.push instead of ..., but that introduces mutation. I invite anyone reading this to take a stab at writing a better utility.

The rules:

  1. No libraries
  2. No statements (const doesn’t count)
  3. No mutation
  4. Pure functions only

#2

Would you still count the following even though I use let and return? It does get rid of two extra remainder calculations.

const fizzBuzz = () => loop(
  1,
  x => x <= 100,
  (x, y) => {
    let z = x % 3 === 0 ? 'Fizz' : x
    return [...y, 
      x % 5 === 0 ? (isNaN(z) ? z : '') + 'Buzz' : z
    ]
  }
);

#3

That’s a clever way to do it. Return is maybe not “distilled water” pure, but this is JavaScript. Let implies state, but in your example, it’s just caching an operation.

I did figure this out for tic tac toe:

const filledArray = (length, filler) => loop(
  0,
  x => x < length,
  (x, y) => [...y, filler]
);

const ticTacToe = () => filledArray(3, filledArray(3, 0));

I was actually hoping someone could improve on loop itself. Do you have any ideas?


#4

Just to cover this point:

  1. You’re referring to imperative loops here: my primary language is one without loops, and I’ve never needed one (and if for some wierd reason it was necessary, I could just write a macro that added it to the language). They’re not necessary because:
  2. Functional languages are generally declarative rather than imperative, so for your loop replacement, you could use reduce on the array. Basically once you have defined that works like fold (left and right), for which for JS is reduce, you can generally do anything you want to a list.
  3. No statements implies everything is an expression. All this does is make things [generally] simpler; if everything were an expression in JS, a loop (in this case I’ve used a for…of, but all the same) would just look like:
const myLoop = for (const something of blah blah) { /* do stuff you would normally do */ }

This is what the do block proposal is for; I don’t think it’ll happen, but that would allow everything to be an expression: https://github.com/tc39/proposal-do-expressions/blob/master/README.md


#5

I’m beginning to understand that the popular literature (read: Medium articles) oversimplifies things. It’s easy to see how functions can replace loops for existing arrays. What I’m stuck on is how you’re supposed to get the array in the first place. filledArray above could be replaced with (length, filler) => Array(length).fill(filler), but for more complex cases, like findRange, there’s an awful lot of hoop jumping to get the same result.


#6

There’s a construct common in other functional languages called unfold, which is more formally known as an anamorphism (and fold or reduce as it’s known in javascript is a catamorphism).

It doesn’t exist in standard JS, but you can emulate it in a sense with the yield keyword.

You shouldn’t imo focus too much on trying to shoehorn idioms from other styles into what you write. If a “purely functional with no loops” pattern doesn’t work for the piece of code you’re currently writing, don’t use it! If a map or a reduce makes the code more elegant, then use it!


#7
  1. Via recursive functions (as you tried above) that build the list incrementally. You can do this in JS but you don’t really want to as it’ll be very slow.
  2. Via range functionality, normally a data structure with associated methods. JavaScript is very limited w/r/t this; most libraries like Lodash provide a range function but they normally just create a list of values.
  3. Via spme form of stream functionality, so generate values in some arbitrary pattern via a some seed function, or just literally stream stuff (say lines of a text file) in value by value. JavaScript generators can do this, as @gebulmer said.
  4. Don’t. This is the most common, because in reality most of what you do (in any programming language) is take some data and transform it into some other data. You normally already have the data structure, you just need to iterate through it.

I get where you’re coming from, it’s just in practice what you’re talking about is generally a non-issue. Plus you’re generally going to use a higher order function anyway.

Edit: also, re your original idea. In practise (not helpful to you exploring the ideas, just how it would be implemented in a working system) would be totally fine to put a loop inside the function; it’s fine for the function to be a black box. You can’t work to a complete level of mathematical purity in practise. For example, there are mutable data structures in probably the most pure functional language, Haskell, and you can construct mutable references that will work like mutable variables. (+ Basically what @gebulmer said)


#8

@gebulmer

Thanks for the tip. I found this article that talks about unfold. Rest assured, I have no intention of replacing all my loops with loop. This is just intellectual curiosity. I’ll definitely be making more use of the standard library, though.

@DanCouper

I can accept the black box idea. At first I didn’t see the point of declarative programming: you’re just putting the implementation details somewhere else. Then I realized that was the point. Also the code reuse thing.

Out of curiosity, what is your primary language?


#9

Bear in mind this is exactly the same idea as encapsulation in class-based OO programming - the end user sees the interface, but not how it works. May not be very ‘functional’ underneath, but the end user should only see a function that behaves the same if given the same input.

Most real world stuff you think about declaratively - “make a sandwich” vs “go through every step needed specific to the environment you’re in”. It’s then easy to snap together actions “make a sandwich then clean the kitchen then go to the park”.

Also, what gebulmer said about idioms from other langs is important. For example, a lot of stuff written about functional programming in JS makes a big deal of currying. You get currying for free in several functional languages: F#/Haskell/Ocaml/Other ML languages’ functions all take one and only one argument. But JS isn’t like that, functions can have any number of arguments, and there’s not really a way to enforce things the way they can be enforced via the type system in those languages (Flow and Typescript are both fantastic, but they’re not a replacement). Currying is a neat trick, but that’s about it in JS (imo, unless someone can convince me otherwise, the focus on it in most functional tutorials is a bit pointless).

Elixir/Erlang. Also at current job use Elm for all frontend work rather than just JS. Plus use some Rust, which has functional idioms.


#10

It seems to me that all languages strive to be declarative in terms of the problems in their domain. Even assembly languages are declarative in that sense. Functional utilities just take things a step further, in a slightly meta direction.

I read somewhere that a “language-oriented” approach is often more useful than trying to rigidly adhere to a paradigm. I think the main things from functional programming that are applicable in JavaScript are pure functions, immutable data, and function composition.


#11

Yeah, I suppose so. Sometimes imperative is useful, sometimes functional is useful, sometimes OO structure is useful, etc. Generally functional approach works well when you have some data and you want to perform a series of transformations on it, kinda like a factory production line. Financial services use FP quite heavily as one example; it helps that they’re mainly hiring mathematicians so a language that actually behaves normally w/r/t to that is probably helpful.

A major FP criticism of imperative code like:

for (var i = 0; i++; i < 10) {
  // do stuff
}

is this: It says: i = 0. It also says i = i + 1. And also that i = 1. And also that i = 2. And so on, and that doesn’t really make sense, it’s like saying 1 = 2 (and yes, it does actually make sense because = means assignment, not equals, but anyway). If you have immutable data, you can’t use an imperative loop because an imperative loop is a nonsensical abstraction.

And everything is a function, f takes a value and returns another value, so statements are doubly nonsensical because they don’t really do anything; they dont accept values and they don’t return values.

Yeah. JS kinda lends itself to a functional style. Don’t change state, don’t mutate data, that’s not too difficult. What’s normally immediately apparent is that, with FP, it is much much much easier to test and reason about programs; immutability and pure functions do this, and you get that benefit straightaway in JS.

But you can’t really get close to other things you normally get, like very good type systems (ML/Haskell/etc), algebraic data types, pattern matching (basically every FP language, + most moden languages implement it now [C#7, Kotlin, Swift for example]) without fiddly boilerplate. Not that it necessarily matters much for most small things in JS, but it makes it even more difficult than it already is to build big, safe applications that you can reason about.


#12

Yeah, I thought JavaScript was functional until I had to write a project in Scheme. Where like you said, everything is an expression and recursion is the only way to solve things, unless you use set to bind variables, which we were not allowed to do. Also, I’m impressed with your knowledge of the different prog lang paradigms and when to use them


#13

Interesting. I hadn’t thought about it in that much depth. I did spend a day annoying my coworkers with trick questions like “If you add one to two, what happens to two?” It was somewhat of a realization for me.

The testing thing is probably why functional programming is seeing such enthusiastic adoption. I think, as beginners, we love the freedom and expressive power of JavaScript, then as we get more experienced (right around the time we learn we’re supposed to be writing tests), we realize it’s really a curse.

I read somewhere that in Haskell (and possibly others), you sometimes don’t even need to hand write tests–they can be generated automatically.

It seems slightly baffling that functional programming has only recently come into the limelight.

Do you think it’s worthwhile for an aspirant web developer to learn something like Elm or ClojureScript, or is it better to focus on something widely used like React/Redux? The disadvantage I see is that anything non-standard is harder for companies to maintain.


#14

Not quite so baffling. Lisp I guess is the first widely [ish] used FP language, and possibly could have won over C, but:

  1. It’s a bit wierd.

  2. There is a focus on writing very well designed software (vs writing stuff that Just Basically Works in C - see this speech, The Rise of Worse is Better). Choice quotes:

    [Scheme is] the diamond-like jewel … takes forever to design, but it is quite small at every point along the way. To implement it to run fast is either impossible or beyond the capabilities of most implementors.

    [re Common Lisp] First, the right thing needs to be designed. Then its implementation needs to be designed. Finally it is implemented. Because it is the right thing, it has nearly 100% of desired functionality, and implementation simplicity was never a concern so it takes a long time to implement. It is large and complex. It requires complex tools to use properly. The last 20% takes 80% of the effort, and so the right thing takes a long time to get out, and it only runs satisfactorily on the most sophisticated hardware.

  3. Memory and storage used to be very expensive. If you’re buying computing equipment to build and run software, you’re gonna go with something that makes best use of that.

Re other functional languages:

  1. They’re weird.

  2. They were, and mostly still are, quite academic and/or specialised, and very math-oriented. Extreme examples:

    life←{↑1 ⍵∨.∧3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂⍵}
    

    That is the Game of Life in APL. That’s the entire, fully functioning program. You need a special keyboard to type APL btw. Here’s a program that finds the prime numbers between 1 and an arbitrary max number R in a successor language to APL, called K:

    2_&{&/x!/:2_!x}'!R
    

    K was written under license for a Swiss bank; it’s primarily used for financial trading calculations, so in a sense it’s not really for traditional programmers at all, it’s for [mathematicall trained] financial analysts. That and APL are designed so that an entire program can be written in a line or two (APL allows someone to write entire complex algorithms on a blackboard).
    Those are extreme examples, but I think this is kinda the image some people have of functional programming though - inscrutable one-liner math gibberish.

  3. They’re often historically [very] slow, and needed advanced equipment to run well. This didn’t/doesn’t matter as much for academic research, but it matters in the real world. Financial institutions again: they can afford to spend $millions on super fast equipment that mitigates any speed issues (or they can simply pay programmers very large amounts of money to write new proprietary languages that are faster).

  4. Memory is now very very cheap, and persistant data structures have been found that are fast, so the speed issue is kinda gone, and research into FP has borne fruit. Note this is what Haskell is: a long-running research project into FP that happens to have real-world applications. But the end result seems to be more that non-FP languages have (slowly) begun to adopt the best parts of pure FP languages. And when people think about FP languages there’s kinda now this entrenched idea that they are slow (which isn’t really true).

  5. The great purported benefit of FP is that immutability/pure functions allow you to easily parallelise work across multiple physical cores, which should make things faster and more efficient. Buuut the problem with this is that the entire system then has to be written to take advantage of this; if any part of the system cannot be parallelised, then the system can only go as fast as that part (Amdahl’s Law). Possibly good example: if you have, say, a AAA game with spiffy graphics, you want to slam most things sequentially through a single really, really fast process. You can’t really parallelise too much because for one thing, you can’t guarantee as easily that things will go in timing order (there are solutions to this though). Anyway, purported benefits of FP w/r/t to parallelisation are maybe overstated or don’t matter that much in the real world, or people just don’t really care that much.

You could be talking about one of two things here: either the type system, or quickcheck.

QuickCheck is a piece of software that, given a seed that generates mounds of data, and a test case, will generate test suites. You still have to write tests (although you have to write far fewer), and they are significantly harder to write. You are testing the general properties of a piece of code, not the specifics - like say function add(a, b) { return a + b; } - assuming this always takes numbers of some kind, does this work for every single possible number you can input? I’m busy learning a version of it in Elixir (here’s the introduction to the book I’m reading on it, it gives a good overview of what property-based testing is), and it is phenomenal, there are versions of it for most languages, and I would seriously recommend it. But it is hard to write those tests - the tests themselves end up being super simple, it’s just the thinking up of good tests takes a while, and the approach is taking a while to click for me at the minute.

strongly typed functional languages (ML/Haskell/OCaml/F#/Elm) have type systems that blow away most other languages and remove entire classes of bugs. The compiler can check the entire program for errors before it builds in a much more comprehensive way than, say, Java or C# can. This removes the need for a whole class of tests. It also generally means that if the program compiles, it runs (vs JS, which breaks all the time). As an example, we have big Elm codebases in place for all our applications for about two years, and we’ve had one (1) runtime error in that time, and that was caused by a freak set of external events. The last place I worked had a huge JS codebase for front end, and at any one point in time at least some of the publicly deployed codebase would be in error (albeit mainly from our code interacting badly with JavaScript the clients were injecting - advertising/click tracking/a-b testing stuff etc).

Note Swift and Rust have similar type systems, and they’re not really functional languages, though Rust uses a lot of ideas from ML, but then that goes back to other languages taking ideas from FP. Also regarding type systems:

Strong type sytems make languages much more expressive than JS. They are extra cognative overhead, and they do make things harder up front (but easier in the long-run?), but being able to design data types then ensure they are correct in the language makes those language far, far more expressive than JS can possibly be (seven [weak] types, count em, that’s yr lot).

Yes, definitely. I can’t say anything about ClojureScript (people I know who have used it love it, but I’ve not - it is literally just Clojure though, and a Lisp, and @EddieCornelious could probably explain a bit better what that’s like). But by all means play around with Elm. It’s a very small language, it works very well. Even if you never use it again, you’ll learn a lot about structuing programs from it. TBH I don’t think it will ever be widely used, but the ideas from it are so good that they will gradually get absorbed into other things. Redux is based on it, for example. The compiler is amazing, particularly w/r/t the polite error messages. However, the type system will be extremely painful at first. Those excellent error messages start to seem ridiculously passive aggressive.

For example, you want to get the first element of a list. So there’s a head function that does that, great. So you use that and try to pass that value to something and…your program doesn’t compile. And the issue is that Elm can’t guarantee that that list won’t be empty. Instead of giving you a value, it gives you the value wrapped in something called Maybe, which says maybe this contains a value, maybe it doesn’t. And you have to decide how to handle that. This is actually extremely great (there are no null values in the language), but it’s jarring when you first start to hit these issues.

Edit: this is so good:

https://aphyr.com/posts/341-hexing-the-technical-interview

https://aphyr.com/posts/342-typing-the-technical-interview

Also Gary Bernhardt on various things but mainly types (video, about 20mins), is very much worth a watch:

https://www.destroyallsoftware.com/talks/ideology

and a v good article from him on types: https://www.destroyallsoftware.com/compendium/types?share_key=baf6b67369843fa2


#15

I’m glad we have people like you in the community. It’s invaluable when experienced developers have the time/inclination/patience to engage in dialogues like this. I regret that I have nothing to add, but there’s enough there to keep me busy for some time.

Property-based testing sounds extremely promising, and it looks like there’s several implementations for JavaScript. (I’m famously bad at listening to warnings.) I was flirting with the idea of experimenting with Elm once I finish the FCC curriculum. I guess I’ll have to.