Functional Algorithm Design/Programming Woes

General Prog (Archived)
,
1

To explain my background, I’m a college student studying computer science who has been programming in Java for most of my programming career (~5 years). In the last two years, Elixir has become my preferred language for the projects that I do outside of school since I mostly do web applications. To be honest, Phoenix, not Elixir itself and functional programming, drew me to this ecosystem. I wanted to learn a web framework which was productive, up and coming, real-time, and interesting, and Phoenix was exactly that for me. I’ve started to enjoy Elixir as a language more and more as I’ve used it over the past two years, to the point I am at now where I’m very comfortable programming in it.

Because of this progression, I tend to write all my web applications in Elixir and some other things also in Elixir. However, for highly structural projects, I find that I think better in OO so I sometimes use Java for those purposes. Java has its ups and downs but having done it for so long I’m most comfortable with it and OOP as a language and way of structuring programs.

Recently, I started taking an algorithms class in school. I find algorithms very interesting, and I know a decent amount about them from. However, one of the first algorithms I was introduced to was the Gale-Shapely algorithm for solving the stable marriage problem. Initially, I spent about 20 minutes trying to implement the algorithm in Elixir before I gave up. I really despise admitting to this because it makes me feel like there is a ceiling which I have reached with functional programming as a paradigm in general and by extension Elixir but when designing or implementing an algorithm, my brain thinks in OOP, and its nearly impossible for me to translate that to functional programming in practice. This is very difficult for me to come to terms with because outside of this I love Elixir/Phoenix a lot and I want to be able to use it for everything that I need to program.

From using Elixir (and some Scala) I’ve been able to get much better at thinking in functional, implementing solutions functionally, using functional paradigms, and using functional programming in practice. However, the fact remains that when I theorize about programming (and especially algorithms), it is much more intuitive, natural, and easy for me to do so in an OOP paradigm. I feel like I’m pushing myself to try and do all of these things functionally in Elixir, when I could do them 3x faster in Java. I don’t like that feeling. Functional programming feels like a chore because I have to “translate” from natural programming/OOP design first.

I think algorithms in general are a serious pain point for functional programming because almost all of them are designed for languages like Java/Python and not functional languages like Elixir. Does anyone else feel this way? I can’t imagine I’m alone here. Also, does anyone have any resources that they recommend for trying to get into the mindset of thinking functionally in particular in reference to algorithms? I don’t have much trouble writing most practical things functionally but when it comes to algorithms, I just get lost. That’s why I don’t think introductory “think functionally” material would help me here, I need functional algorithms material.

Sorry for what looks like a long ramble but this subject has been on my mind for a while and it has festered enough that I want to get my difficulty out there and see if others have suggestions/resources to help me.

Thanks for reading :smile:

4 Likes
2

Yes, this is true. FP is too different from “traditional” imperattiv languages, so you can’t take imperativ algorithms and just implement them 1:1 in FP.

And if you do, its often highly inefficient. For FP there are more specialised algorithms for equivalent problems available. Often at least.

So you really don’t need to worry.

I haven’t looked at your marriage algorithm yet though, and I can’t say if it is implementable in FP or not. Someone else has to do that, as I have a full schedule today.

3 Likes
3

I found that Elixir by itself isn’t enough to counter my 20+ years of imperative and OOP indoctrination, so over the past years I’ve had to throw Clojure, Erlang and Haskell at it (to counter all those accumulated C, C++, Java, C# habits somehow).

Right now dabbling in ReasonML/BuckleScript is having a definite effect on how I use ECMAScript.

But the un-learning can feel like a slow and painful process - but all you can really do is chip away at it one day at a time.

It’s a problem if you perceive it as a ceiling - more likely you’re simply getting impatient - just keep at it. The important thing is to strive to understand more today than you did yesterday.

I need functional algorithms material.

There is Okasaki’s Purely Functional Data Structures (Book) and Bird’s Pearls of Functional Algorithm Design but they are hardly entry level material.

7 Likes
4

As a general tip for problems like this, I would say start very very simple with the data representation. The natural reflex coming from OOP is to wrap everything in structs and modules (Couple, Person, etc.), but it’s counter-productive to do that too early because the big picture becomes hidden in the details.

For the marriage thing for instance you could start with a list of tuples {man_id, woman_id} to store who proposed to whom, and a similar list of engaged couples. That’d let you get a first inefficient but correct version of the algorithm. Try to use lots of small functions (e.g. is_free?(proposals, person)) to manipulate the data. Then later you can refine the representation and get fancier with maps or records. At that point the overall structure of the program shouldn’t change much, you’d just reimplement the small helpers as you refine the representation.

I don’t really have a book to recommend on this topic, but I learned a lot from reading code in the Erlang and Elixir language repos. The Erlang compiler does complex algorithms with very basic components like recursive functions, lists and tagged tuples; it feels very different from typical OO programs. Elixir’s repo is also interesting because the code is so clean and well documented.

6 Likes
5

Few things, first, FP is not too different from traditional imperative languages, an FP language is just a language where functions are first class values (just like ML languages have modules as first class values, which Elixir has too, or OOP languages have Objects as first class values, which Elixir also has too via Actors).

Second, Elixir is a more pure OOP language than Java could ever hope to be. An Actor in Elixir (called a Process) is the perfect form of an object from an OOP world as it has perfect data hiding, message passing (which java fakes with method calls), etc… Java and C++ and C# and all those are not OOP languages, they are kind of diminutive OOP languages. Languages that do OOP far far more properly are of course Elixir/Erlang, Lisp, Smalltalk, etc…

Third, what is tripping you up is not the FP or ML or OOP I would bet you, but rather the immutability aspect, you should focus on making that part click well and how to ‘mutate’ state via passing it around instead of mutating memory values. Elixir is not a language that has first-class memory (which Java and C++ and C# and such have), but rather the memory is abstracted out and is conceptually immutable once defined (called ‘binding’ in these style languages).

7 Likes
6

I think you have captured what I’ve been trying to say pretty perfectly, and I appreciate your response and clarity. It really does seem like immutability is what is tripping me up, I think I just strongly associate that with FP.

1 Like
7

Thank you for the recommendations! I’m struggling with these concepts in practice but I really do want to persevere because many other aspects of FP and Elixir especially have really clicked for me and I want to be able to say the same for immutability and FP. Those resources look like exactly what I’m looking for, I will absolutely be checking those out :smile:

8

It might be worth taking a small set of men and women and stepping through what the structures would look like line by line.

Mapping the transformation as it goes through the process has always helped me when shifting my thinking.

3 Likes
9

Wrote a sample implementation of it:

I think there are two things that may be confusing: immutability and structuring of the code.

For understanding immutability better there’s no way except exercise. You just gotta write those recursive algorithms from time to time. Going through some traditional things like folds, binary trees, AVL trees will definetly help. Okasaki’s book is classic, but somewhat hard to read. This is another book that might help, and it’s easier to follow than Okasaki:

https://www.amazon.com/Algorithms-Functional-Programming-Approach-International/dp/0201596040

It really does get easier with the experience :slight_smile:

A lot of people use OOP as a way to structure programs, but you have superior tools now: decent module system, structs with comparison logic already implemented, Actors & Supervison trees where you need them. Ability to easily create, traverse, and pattern match data directly is also invaluable. And yeah, sometimes a function is all you need.

There’s also sort’s of an “algorithm for writing algorithms” that I personally use:

  1. Start with expressing your input state. In this case it’s 2 lists of Preference structs.
  2. Think how the answer will look. In this case, it’s a list of matching tuples {man_id, woman_id}.
  3. Consider “super-structure” of the algorithm you want to implement. If you see iteration, you already know that this can be expressed as either direct recursion or use of Enum.map, Enum.reduce, etc. What data do you need to maintain for each step? What’s your termination condition? In this case we terminate when we don’t have unengaged men anymore. We need to maintain lists of men and women with the statuses of their engagements and previous proposals. You can represent that as another struct, or you can just add required fields to Preference.
  4. Now you can apply the usual top-down approach. One advice: prefer expressing retrieval of values / changing them as separate functions for non-trivial algorithms. This way you can more easily change the data layout later if’ll you need to. And, of course, don’t concentrate too much on performance early on: it’s easier to optimize simple code than to fix bugs in the complex code :slight_smile:
  5. Write some tests, if needed - benchmark and optimize step-by-step.

P.S. State representation is usually critical. For this particular problem, I can think of some other ways of representing it:

  • You can express preferences as 2D array M of tuples. For x being the man id, and y being the woman id, M[x, y] is a tuple {male_preference, female_preference}, where both male_preference and female_preference are positive integers corresponding to the places they have in each other preference lists.
  • (stretching it in this case, but true for general case) You can express each man and woman as an actor

The same goes for the results. These choices have significant impact on both clarity and performance of the solution.

4 Likes