Lazy dynamic programming in OCaml?

Learning
,
1

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
2

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