天泣記

OCaml で、配列の要素になんか関数を適用して、その関数が成功したらその結果を返す、という関数を書きたいことがあった

これは高階関数で、'a array 型の配列と、その要素を受け取って 'b option 型の値を返す関数 f を受け取る。配列の最初の要素から順に f に与えて、f が None を返したら次の要素に進む。最初に Some x を返したらそれを返す、というものである。なお、最後まで Some が返されなかったら None を返す。

let array_find_map (f : 'a -> 'b option) (s : 'a array) : 'b option = ...

さて、どうやって実装するか

配列なのでとりあえず for ループでやるか、と考えて、ループの途中で脱出するのは例外を使えばいいだろう、ということで、以下を書いた

let array_find_map (f : 'a -> 'b option) (s : 'a array) : 'b option =
  let exception Found of 'b option in
  try
    for i = 0 to Array.length s do
      let v = f s.(i) in
      match v with
      | None -> ()
      | Some _ -> raise (Found v)
    done;
    None
  with Found v ->
    v

しかしこれはエラーになる

Error: The type variable 'b is unbound in this type declaration.

どうも、例外の引数は多相型にはできないぽい

まぁ、再帰を使えば例外を使わずに書けるからいいけど

let array_find_map (f : 'a -> 'b option) (s : 'a array) : 'b option =
  let n = Array.length s in
  let rec aux i =
    if i < n then
      let v = f s.(i) in
      match v with
      | None -> aux (i+1)
      | Some _ -> v
    else
      None
  in
  aux 0

でも、ループで書けないのは気になる。検索すると、Locally abstract types なるものを使えるようだ

The OCaml Manual, Locally abstract types

以下のようにしたら通った

let array_find_map (type a b) (f : a -> b option) (s : a array) : b option =
    let module M = struct exception Found of b option end in
    try
      for i = 0 to Array.length s do
        let v = f s.(i) in
          match v with
        | None -> ()
        | Some _ -> raise (M.Found v)
      done;
      None
    with M.Found v ->
      v

しかし、これが通るんならなんで最初のが通らんのだ、意味もなく module が必要でよろしくない、と思ったが、試すと module を使わなくてもいいようだ

let array_find_map (type a b) (f : a -> b option) (s : a array) : b option =
    let exception Found of b option in
    try
      for i = 0 to Array.length s do
        let v = f s.(i) in
          match v with
        | None -> ()
        | Some _ -> raise (Found v)
      done;
      None
    with Found v ->
      v

とすると、最初のが通らないのは、単に型変数のスコープから外れているから、というだけの話なのかな

天泣記

2022-01-30 (Sun)