「ソフトウェアエンジニアならば1時間以内に解けなければいけない5つの問題」をStandard MLでやってみた

tanakhさんの記事に触発されて、僕もMLで解いてみました。
OCamlで書いてもあまり新規性が無いのでStandard MLです。
ここに書いてあるコードはSML/NJ v110.78で動作を確認しました。

問題1

forループ、whileループ、および再帰を使用して、リスト内の数字の合計を計算する3つの関数を記述せよ。

(SML '97の範囲では)SMLにfor文は無いように見えるのでC言語のforのように振る舞う関数を定義します。

fun for { init = i, cond = c, succ = s, body = b } =
  (i ();
   while c () do
     (b ();
      s ()))

fun sumFor l0 =
  let
    val sum = ref 0
    val l = ref []
  in
    for
      { init = fn () => l := l0,
        cond = fn () => not (null (!l)),
        succ = fn () => l := tl (!l),
        body = fn () => sum := !sum + hd (!l) };
    !sum
  end
(* 
- sumFor [1, 1, 4, 5, 1, 4];
val it = 16 : int
*)

副作用やレコードを気軽に扱えるのはSMLの良いところですね。
while文を使う実装は前の実装をinliningすれば得られます。

fun sumWhile l0 =
  let
    val sum = ref 0
    val l = ref l0
  in
    while not (null (!l)) do
      (sum := !sum + hd (!l);
       l := tl (!l));
    !sum
  end
(*
- sumWhile [1, 9, 1, 9];
val it = 20 : int
*)

再帰はまぁ自明ですね。退屈なので意味もなく末尾再帰で書いてます。

fun sum acc [] = acc
  | sum acc (n :: ns) = sum (n + acc) ns
val sum = sum 0
(*
- sum [8, 1, 0];
val it = 9 : int
*)

問題2

交互に要素を取ることで、2つのリストを結合する関数を記述せよ。例えば [a, b, c]と[1, 2, 3]という2つのリストを与えると、関数は [a, 1, b, 2, c, 3]を返す。

Standard ML Basis LibraryにはListPair.mapという便利そうな関数があるのでこれを使います。
SMLの標準ライブラリはOCamlのすとっどりぶと比べると結構充実しているように見えるんですよね。実際は全然充実してない訳ですが。

fun interleave (xs, ys) =
  List.concat (ListPair.map (fn (x, y) => [x, y]) (xs, ys))
(*
- interleave ([1, 2, 3], [9, 8, 7]);
val it = [1,9,2,8,3,7] : int list
*)

リストの長さが異なる場合の動作が微妙な感じもしますが、日本語の紹介記事には細かく指定されてなかったので深入りしません。英語の文章を読むのは疲れるので。
ちなみに、カリー化されていないのはSML特有のコーディング規約です。

問題3

最初の100個のフィボナッチ数のリストを計算する関数を記述せよ。定義では、フィボナッチ数列の最初の2つの数字は0と1で、次の数は前の2つの合計となる。例えば最初の10個のフィボナッチ数列は、0, 1, 1, 2, 3, 5, 8, 13, 21, 34となる。

SMLでも頑張ればstreamを作れなくもないですが、疲れるので実直に実装しましょう。

fun fibList acc (f0, f1) 0 = rev acc
  | fibList acc (f0, f1) n = fibList (f0 :: acc) (f1, f0 + f1) (n - 1)
val fibList = fibList [] (0, 1)
(*
- fibList 10;
val it = [0,1,1,2,3,5,8,13,21,34] : int list
*)

例によって末尾再帰です。

問題4

正の整数のリストを与えられたとき、数を並び替えて可能な最大数を返す関数を記述せよ。例えば、[50, 2, 1, 9]が与えられた時、95021が答えとなる

貪欲法を使って解くところですが、SMLの標準ライブラリにはリストをソートする関数が存在しないので、SML/NJ Libraryの関数を使ってお茶を濁すことにします。

fun decimal acc n =
  if n = 0 then acc
  else decimal (n mod 10 :: acc) (n div 10)
val decimal = decimal []

val maxPerm =
  foldl (fn (d, n) => 10 * n + d) 0
  o List.concat
  o ListMergeSort.sort (fn (ms, ns) => hd ms < hd ns)
  o map decimal

(*
- maxPerm [50, 2, 1, 9];
val it = 95021 : int
*)

問題5

1,2,…,9の数をこの順序で、”+”、”-“、またはななにもせず結果が100となるあらゆる組合せを出力するプログラムを記述せよ。例えば、1 + 2 + 34 – 5 + 67 – 8 + 9 = 100となる

最後だけやたら難しくないですか？
とりあえず有り得る式を全て文字列で列挙して、評価して100になるものを総当たりで探索しています。
演算子に優先順位が無くて助かりました。

local
  fun intOfString s = getOpt (Int.fromString s, 0)
  fun eval' m [] = m
    | eval' m ("+" :: n :: ns) = eval' (m + intOfString n) ns
    | eval' m ("-" :: n :: ns) = eval' (m - intOfString n) ns
in
  fun eval (n :: tokens) = eval' (intOfString n) tokens
end

fun solve n =
  (map #1
  o List.filter (fn (_, v) => v = 100)
  o map (fn s => (s, (eval o String.tokens Char.isSpace) s))
  o map (foldl (fn (opr, form) => form ^ opr) "1")
  o map (fn ops =>
      ListPair.map (fn (n, opr) => opr ^ n)
        (List.tabulate (n, fn i => Int.toString (i + 2)), ops))
  o foldl (fn (xs, yss) =>
      List.concat
        (map (fn x =>
          map (fn ys => x :: ys) yss) xs)) [[]])
    (List.tabulate (n, fn _ => [" + ", " - ", ""]))

(*
- solve 8
val it =
  ["1 + 2 + 3 - 4 + 5 + 6 + 78 + 9","1 + 2 + 34 - 5 + 67 - 8 + 9",
   "1 + 23 - 4 + 5 + 6 + 78 - 9","1 + 23 - 4 + 56 + 7 + 8 + 9",
   "12 + 3 + 4 + 5 - 6 - 7 + 89","12 + 3 - 4 + 5 + 67 + 8 + 9",
   "12 - 3 - 4 + 5 - 6 + 7 + 89","123 + 4 - 5 + 67 - 89",
   "123 + 45 - 67 + 8 - 9","123 - 4 - 5 - 6 - 7 + 8 - 9","123 - 45 - 67 + 89"]
  : string list
*)

local結構便利ですね。