For example, this hard-level problem and its C++ solution. There are 5 states involved. I find the imperative code relatively easy to understand, and I can’t imagine solving it without mutability and loops.
1 Like
Not to say that solutions without them aren’t worth considering, but it’s worth noting that OCaml has mutability and loops.
2 Likes
Yeah, but I was wondering if algorithm problems can be solved elegantly in the functional style.
State can be transformed by folds, etc, elegantly (although perhaps not with great performance). Have you tried solving the problem you referenced?
1 Like
Functional Programming can be superb for coding algorithm problems!
The famous Trapping Rain Water problem can be solved elegantly in a few folds in a FP language.
Thanks to Algebraic Data Types and pattern-matching, implementing algorithms on trees and lists is a breeze (e.g. the implementation of a tree reversal in two lines of code).
However, some algorithms do require state and mutability for efficiency (dynamic programming, doubly-linked lists, trees with links to parents and iterators over trees, many algorithms in computational geometry, etc.). That’s why I believe that OCaml is the best language for solving coding algorithm problems because it supports solutions in both styles: FP and with hassle-free mutability.
It’s pity popular coding platforms like LeetCode don’t accept solutions in OCaml 
6 Likes
I don’t leetcode myself, but for every instance a leetcode problem + solution (usually in C++) was shared with me and I solved it with OCaml or Haskell etc, the solution came out much simpler than what was originally shared.
I’m inclined to believe leetcode doesn’t provide support for these langs because they’d trivialize some of the “tricky” imperative steps and edge-cases in the problems in question, turning the solution into a formalization of the problem description.
That said, leetcode is vast and many of its (especially harder) problems probably won’t benefit much from using a saner programming language to solve. Take my anecdote as you will, but I encourage you to go through your old solutions and try to comparatively solve them in your favorite FP language, hopefully OCaml :P.
2 Likes
Here is my take. I didn’t try to optimize anything (I’m sure one could make it much shorter), on the other hand I tried to make it pedagogical. In particular you see that using functional structures, one can very closely match the description of the rules of the game in the syntax of the door function.
(* https://leetcode.ca/2023-03-02-2534-Time-Taken-to-Cross-the-Door/ *)
(* We see that the list of people willing to ENTER and the list of people
willing to EXIT have a FIXED ORDERING throughout the algorithm. Hence it's a
good idea to work with these lists. That's why we introduce new data
structure and convert the imposed arrays [arrival] and [state] into these new
data. *)
type person = {
id : int;
arrival : int (* time *) }
type direction = Enter | Exit | Wait
(* 'Wait' is not strictly necessary, it could be replaced by 'Exit'; we use it
for clarity. *)
(* Take the input required by the exercise and return two ordered lists: the
list of persons wanting to enter, and the list of persons wanting to exit. *)
let make_lists arrival state =
List.mapi (fun id arrival -> { id; arrival }) (Array.to_list arrival)
|> List.partition_map (fun p ->
if state.(p.id) = 0 then Either.Left p else Either.Right p)
(* Return the next pair of persons who may compete at the door at this time. *)
let next_pair time list1 list2 =
let next = function
| [] -> None, []
| x::rest as list ->
if x.arrival <= time then Some x, rest else None, list in
(next list1, next list2)
let cross p time = (p.id, time)
(* Return the final list of crossing persons. *)
let rec door last_dir time entering exiting crossed =
if entering = [] && exiting = [] then crossed
else match next_pair time entering exiting with
| (None, _), (None, _) -> (* no one at the door *)
door Wait (time+1) entering exiting crossed
| (Some p, entering), (None, _) -> (* one entering person *)
door Enter (time+1) entering exiting (cross p time :: crossed)
| (None, _), (Some p, exiting) -> (* one exiting person *)
door Exit (time+1) entering exiting (cross p time :: crossed)
| (Some p1, new_entering), (Some p2, new_exiting) -> (* competition! *)
begin
match last_dir with
| Wait
| Exit ->
door Exit (time+1) entering new_exiting (cross p2 time :: crossed)
| Enter ->
door Enter (time+1) new_entering exiting (cross p1 time ::crossed)
end
(* Convert the crossed list into the required format *)
let result crossed =
let n = List.length crossed in
let res = Array.make n 0 in
List.iter (fun (id, time) -> res.(id) <- time) crossed;
res
let run arrival state =
let entering, exiting = make_lists arrival state in
door Wait 0 entering exiting []
|> result
(* Example 1 *)
let arrival = [|0;1;1;2;4|];;
let state = [|0;1;0;0;1|];;
run arrival state;;
(* Example 2 *)
let arrival = [|0;0;0|];;
let state = [|1;0;1|];;
run arrival state;;
5 Likes
Amazing and eye-opening for me!
I tried but couldn’t do it elegantly. I’m studying sanette’s code.
Like other commenters, I think FP (even without mutability, loops) is a fine way to code complex algorithms, and it’s often useful to do b/c the FP version makes apparent the invariants and reasoning that in an imperative version must be extracted by careful reading. So for instance, whereas in a loop, you have to figure out which variables are modified thru each iteration, with a tail-recursive function you don’t bother – the arguments to the function at each recursive call-site tell you how the loop-carried variables change.
Etc.
It’s really valuable to learn the “FP way” of programming, for precisely this reason. I learned it before FP was popular, and I’m sure there are better books today, but the pivotal book for me was Peter Henderson’s Functional Programming. It’s ancient, certainly out-of-print, and anyway surely there are better books these days.
There’s an FP koan about this: Functional Programming Koans, in OCaml by Doug Bagley — Translated by humans
The Koan of Side Effects
A student of FP came to Daniel de Rauglaudre and asked how to achieve FP Nature. Daniel replied, “to achieve FP Nature, you must learn to program without side effects and other imperative features”. So the student went away to learn how to program in this style. He studied very hard so he could rid his programs of references and for-loops. He struggled to only use let bindings and let rec loops. One day, in order to find inspiration, he was studying the code of the Masters, and in reading the source of Camlp4, he saw a number of uses of references and for-loops! He rushed back to Daniel de Rauglaudre and exclaimed, “How can you tell me not to use imperative features when you use them yourself!” Daniel measured the student carefully in his gaze and replied, “But I already know how to program without side-effects.” At that moment the student was enlightened.
3 Likes
It relates to an academic area called program calculation. You should refer to the masterpiece of Richard Bird. See https://en.wikipedia.org/wiki/Bird%E2%80%93Meertens_formalism.
2 Likes