# Lazy dynamic programming in OCaml?

**URL:** <https://discuss.ocaml.org/t/lazy-dynamic-programming-in-ocaml/12807>\
**Category:** Learning\
**Tags:** dynamic-programming, lazy\
**Created:** [August 12, 2023, 2:32pm UTC](https://discuss.ocaml.org/t/lazy-dynamic-programming-in-ocaml/12807 "2023-08-12T14:32:33Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![Solid](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/solid/32/4616_2.png) [@Solid](https://discuss.ocaml.org/u/Solid)\
**Post date:** [August 12, 2023, 2:32pm UTC](https://discuss.ocaml.org/t/lazy-dynamic-programming-in-ocaml/12807/1 "2023-08-12T14:32:33Z")

</div>

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](https://en.wikipedia.org/wiki/Change-making_problem). Here is a basic solution in Haskell:

```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

```ocaml
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.

---

<div class="post-metadata">

**Author:** ![SkySkimmer](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/skyskimmer/32/1672_2.png) [@SkySkimmer](https://discuss.ocaml.org/u/SkySkimmer)\
**Post date:** [August 12, 2023, 3:40pm UTC](https://discuss.ocaml.org/t/lazy-dynamic-programming-in-ocaml/12807/2 "2023-08-12T15:40:24Z")

</div>

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

```auto
(* 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.