Recursion Is Necessary, Part II: Dynamic Programming

(See also: Part 1 and Part 3.)

(Note: You can find the completed LFE code from this post here: https://github.com/danieljaouen/dynamic-programming-in-lfe , as well as the translated Elixir code here: https://github.com/danieljaouen/dynamic-programming-in-elixir .)

Today, I am revisiting everyone’s favorite topic from college: Dynamic Programming! Get your LFE skills ready because we are about to hit the ground running!

First, create a new LFE project with a main function by typing the following into your terminal:

rebar3 new lfe-main dynamic-programming-in-lfe

That should create the appropriate files and directory structure that we need. Next, add the following to your scripts/main.lfe:

(defun main (args)
  (let* ((g (digraph:new))
         (source (digraph:add_vertex g 'source))
         (sink (digraph:add_vertex g 'sink))
         (v1 (digraph:add_vertex g 'v1))
         (v2 (digraph:add_vertex g 'v2))
         (v3 (digraph:add_vertex g 'v3))
         (e1 (digraph:add_edge g source v1 (dynamic-programming-in-lfe:make-cost-function 1)))
         (e2 (digraph:add_edge g source v2 (dynamic-programming-in-lfe:make-cost-function 2)))
         (e3 (digraph:add_edge g v1 sink (dynamic-programming-in-lfe:make-cost-function 3)))
         (e4 (digraph:add_edge g v2 sink (dynamic-programming-in-lfe:make-cost-function 4)))
         (e5 (digraph:add_edge g v3 sink (dynamic-programming-in-lfe:make-cost-function 1))))
    (case (dynamic-programming-in-lfe:lowest-cost-path g source sink)
      ((tuple 'ok path cost) (lfe_io:format "Path: ~p~nCost: ~p~n" `(,path ,cost)))
      ((tuple 'error msg) (lfe_io:format msg '())))))

From our main function, we can see that we are first creating a DAG, then creating a group of vertices, then a group of edges, and then finally calling dynamic-programming-in-lfe:lowest-cost-path.

Now, let’s take a look at src/dynamic-programming-in-lfe.lfe. We first start out with a my-min function, which will come in handy later (Edit: I clarified the errors here in an update :) )

(defun my-min (lst)
  (if (== lst [])
    #(error "Empty list passed to my-min")
    (lists:foldl
     (lambda (x y)
       (if (< (element 3 x) (element 3 y))
         x
         y))
     (hd lst)
     (tl lst))))

Next, we create a make-cost-function function:

(defun make-cost-function (n)
  (lambda ()
    n))

Now, we get into the meat of things. It is time to create our lowest-cost-path-helper function:

(defun lowest-cost-path-helper (g source sink)
  (if (== source sink)
    (tuple 'ok (list source) 0)
    (let ((in-edges (digraph:in_edges g sink)))
      (if (== in-edges [])
        (tuple 'error "Cannot reach source from current path")
        (clj:->> in-edges
                 (lists:map (lambda (edge) (calculate-current-path g source edge)))
                 (lists:filter (lambda (x) (== (element 1 x) 'ok)))
                 (my-min))))))

First, we check to see if the source is equal to the sink. If it is, we return #(ok [source] 0). If it isn’t, then we get the in_edges for our sink. If that list is empty, we return from the function with an #(error msg) tuple. Otherwise, we call the Clojure threading macro on in-edges, pipe it to a lists:map (to recursively call lowest-cost-path-helper on the left vertex from the edge), a lists:filter (to filter out any :error tuples we might have calculated), and then finally to my-min. We note here that the lists:map calls out to calculate-current-path, which recursively calls back to lowest-cost-path-helper. You can find its definition below.

(defun calculate-current-path (g source edge)
  (let (((tuple e v1 v2 cost-fn)
         (digraph:edge g edge)))
    (case (lowest-cost-path-helper g source v1)
      ((tuple 'ok path cost)
       (tuple 'ok `(,@path ,v2) (+ cost (funcall cost-fn))))
      ((tuple 'error msg)
       (tuple 'error msg)))))

Finally, we define our lowest-cost-path function:

(defun lowest-cost-path (g source sink)
  (if (not (digraph_utils:is_acyclic g))
    (tuple 'error "Graph is not acyclic")
    (let ((result (lowest-cost-path-helper g source sink)))
      (case result
        ((tuple 'ok path cost)
         (tuple 'ok path cost))
        ((tuple 'error msg)
         (tuple 'error "No path from source to sink"))))))

Here, we check to make sure the graph is acyclic. If it isn’t, we return an error that the graph is not acyclic. If it is, we have a case expression: if the first element of result is 'ok, we return an ok tuple with the path and calculated cost.

Then, we of course need to export our functions at the top of the file:

(defmodule dynamic-programming-in-lfe
  (export
   (lowest-cost-path 3)
   (make-cost-function 1)))

And that’s it! You can find the complete source code here: https://github.com/danieljaouen/dynamic-programming-in-lfe

Enjoy!

(More to come soon.)