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…