# Lazy dynamic programming in OCaml?

Hi,

I just started out learning OCaml, so I apologise if this is too basic a question for this Discourse.

In an effort to get a grip on OCaml’s handling of laziness, I wanted to implement the min coin change problem. Here is a basic solution in Haskell:

``````import Data.List
import Data.Array

change :: [Int] -> Int -> [Int]
change coins value = memo ! value
where
memo :: Array Int [Int]
memo = array (0, value) [(n, getVal n) | n <- [0 .. value]]

getVal :: Int -> [Int]
getVal 0 = []
getVal v = uncurry (:) . head . sortOn (length . snd) \$
[ (i, memo ! (v - i)) | i <- takeWhile (<= v) coins ]

main :: IO ()
main = print \$ change [1, 4, 15, 20, 50] 23
``````

I thought this was a nice problem because the code is still pretty basic, but it prominently features mutual recursion of `memo` and `getVal`. I haven’t managed to implement this in OCaml, hence this cry for help. My basic attempt was something along the lines of

``````open Core

let change coins value =
let rec memo = lazy (Array.of_list_map (List.range 0 value) ~f:get_val)
and get_val = function
| 0 -> []
| v -> List.(sort (map ~f:(fun i -> (i, memo.(v - i)))
(* ^^^^^ argh *)
(take_while coins ~f:(fun x -> x <= v)))
~compare:(fun (_, a) (_, b) ->
Int.compare (List.length a) (List.length b)))
|> (fun xs -> let (a, b) = List.hd_exn xs in List.cons a b)
in (Lazy.force memo).(value)
``````

but of course this doesn’t work, because of the marked spot; `memo` is lazy, and would need to be forced in order for its value to be usable. The computation of `get_val` itself should be lazy, so forcing a value there doesn’t sound advisable—and an `Exception: Lazy.Undefined.` upon evaluation seems to agree with me. However, even if `get_val` was lazy, I feel like the compiler would still force me to evaluate `memo` here, because I’m accessing a value via the array syntactic sugar, and laziness is being kept track of at the type level. This leaves me a bit confused, and unsure what to do.

1 Like

Indeed each cell of the array needs to be independently lazy. So for instance

``````(* using stdlib, not Core *)

let rec take_while ~f = function
| [] -> []
| x :: tl ->
if f x then x :: take_while ~f tl
else []

let change coins value =
let rec memo = lazy (Array.init (value+1) (fun i -> lazy (compute_val i)))
and get_val i = Lazy.force (Lazy.force memo).(i)
and compute_val = function
| 0 -> []
| v ->
let xs =
List.sort
(fun (_, a) (_, b) -> List.compare_lengths a b)
(List.map (fun i -> (i, get_val (v - i)))
(take_while coins ~f:(fun x -> x <= v)))
in
let (a, b) = List.hd xs in
a :: b
in
get_val value

let test coins value =
assert (value = List.fold_left (+) 0 (change coins value))

let () = test [1; 4; 15; 20; 50] 23
``````

Note that semantically we don’t need the whole `memo` to be lazy (it’s immediately forced after all), but `let rec memo = Array.init ...` fails the syntactic check of OCaml `let rec`.

The computation of get_val itself should be lazy, so forcing a value there doesn’t sound advisable

That sounds incorrect. `get_val` is called when we need the actual value, and it is expected that some other values may need to be computed to get it. The calls to `get_val` are the ones that need to be done lazily.

Also `head . sort` may be efficient on haskell lazy lists, but in ocaml you may want to use a dedicated `min_elt` function instead.

1 Like