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

Haskellだと問題1が一番難しいともっぱらの噂の問題をやってみました。

問題1

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

再帰のコードが一番簡単なので、まずはそれから。

sumRec :: Num a => [a] -> a
sumRec [] = 0
sumRec (x:xs) = x + sum xs

ではついに一番難しいforループとwhileループのコードを書いてみましょう。
まず問題になるのが、Haskellにはfor文もwhile文もないというところです。まずはforループを作らなければなりません。そもそもforループ、whileループというのが、何を示すのか？というのがあんまり自明ではないのですが、C言語でのforループとwhileループだと考えましょうか。

for :: Monad m => a -> (a -> Bool) -> (a -> a) -> (a -> m ()) -> m ()
for init cond incr body = go init where
  go cur
    | cond cur = do
        body cur
        go $ incr cur
    | otherwise =
        return ()

C言語のforとまったく同じインターフェースにしようとすると、あまりにも煩雑になってしまうし、なぜHaskellをやっているんだ…。という気持ちになってきてしまったので、ループ変数は一つ固定で、ループ変数を更新できるのはforの3つ目の引数に限定しました。あとcontinueとbreakの機能も使わないので考えません。これで、なんとかシンプルなインターフェースと実装におさまりました。

次にこれを使ってsumを実装していきます。

おそらく、普通にC言語で配列の中身を合計するコードは次のようなものになると思います。

int sum(int *p, int n)
{
    int ret = 0;
    for (int i = 0; i < n; i++)
        ret += p[i];
    return ret;
}

これを大体一対一に翻訳していくと、次のようなHaskellコードが得られます。

import Control.Monad.ST
import Data.STRef

sumFor :: Num a => [a] -> a
sumFor xs = runST $ do
  r <- newSTRef 0
  for 0 (< length xs) (+1) $ \i -> do
    modifySTRef r (+ xs !! i)
  readSTRef r

STモナドを使っているので、全体は純粋な関数になります。STモナド便利ですね。

modifySTRef という関数は、ある変数に入っている値を、与えた関数で更新します。この場合は (+ xs !! i) を与えているので、配列のi版目の値をSTRef vに加算するという処理になります。

この実装には問題があって、xs !! i がリストのi版目の値の参照なのですが、これがiに比例した時間がかかってしまうので、トータルでは長さの2乗に比例した時間がかかってしまいます。常識的に考えてこんな実装は受け入れられないので、この部分をなんとかしましょう。

一番簡単なのは、添え字アクセスを定数時間で行えるデータ構造を使うことです。Haskellだとvectorがその目的に使えます。リストからVectorへは、fromListという関数で変換することができます。

import qualified Data.Vector as V
import Data.Vector ((!))

sumFor2 :: Num a => [a] -> a
sumFor2 xs = runST $ do
  let v = V.fromList xs
  r <- newSTRef 0
  for 0 (< V.length v) (+1) $ \i -> do
    modifySTRef r (+ v ! i)
  readSTRef r

最初にリストから配列を作っている部分と、ループの内部で、リストの代わりに配列から要素にアクセスしている部分以外は、前の実装と同じです。

別の方法でリストへの配列アクセスをなくすことも考えられます。Cの実装から離れて、ループ変数を配列自体にしてみましょうか。

sumFor3 :: Num a => [a] -> a
sumFor3 xs = runST $ do
  r <- newSTRef 0
  for xs (not . null) tail $ \ys -> do
    modifySTRef r (+ head ys)
  readSTRef r

forのループ変数の初期値として、入力のリストそのものを与えています。ループ継続条件は、not . null で、これはそのリストに要素がまだ残っているかを調べています。ループ変数の更新はtailで、これで先頭の要素を捨てています。ループの中身は、そのループ変数の先頭を、変数に足し合わせています。headやtailやnullはすべて定数時間で実行できるので、これで実行時間の問題は解決しました。

forループというのが、広義にforeachも含むと考えれば、もう少しすっきりとした実装にできます。

HaskellではforM_が大体foreachのようなものなので、次のように書くこともできます。

sumForEach :: Num a => [a] -> a
sumForEach xs = runST $ do
  r <- newSTRef 0
  forM_ xs $ \x ->
    modifySTRef r (+ x)
  readSTRef r

さて、次はwhileをなんとかしましょう。whileは、一般的にループ継続条件のみをとるので、forよりも抽象化が効かなくて、より手続的なコードを強いられることになると思います。

while :: Monad m => m Bool -> m () -> m ()
while cond body = do
  b <- cond
  when b $ do
    body
    while cond body

純粋な値では条件式を変化させる手段がないので、必然的にBoolを返すモナドで受けることになります。

sumWhile :: Num a => [a] -> a
sumWhile xs = runST $ do
  let v = V.fromList xs
  r <- newSTRef 0
  i <- newSTRef 0
  while (readSTRef i >>= return . (< V.length v)) $ do
    i' <- readSTRef i
    modifySTRef r (+ v V.! i')
    modifySTRef i (+1)
  readSTRef r

これを使って、ループ変数iをインクリメントしながらリストの最後まで処理するようなコードを書けば、sumが完成します。これにもいくつかバリエーションは考えられますが、とても退屈な繰り返しになるだけなので、省略します。

さて、Haskellは最強の手続き型言語と言われることもあって、例えばここで書いたようなforやwhileのような、手続きに関する手続きを簡単に書くことができて、C言語のforやwhileに囚われなければ、いくらでもループの抽象化を考えて実装することができます。たいていの場合、うまくぴったりはまるもっと別の方法があると思うので、はっきり言ってこのようなコードをsumで書く必要は全くないのですが、実際問題道具というのはあればあるほどいいというのがHaskellコミュニティーではよく言われていますので、こういうのもあるいはぴったりはまるところが、別の問題ではあるかもしれません。

このあたりに、いろんなループの実装例があるので、見てみると面白いかもしれません。

問題2

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

最難問が終わったので、あとはもう消化ですが、一応やっておきます。

interleave :: [a] -> [a] -> [a]
interleave [] ys = ys
interleave (x:xs) ys = x : interleave ys xs

一つ目の要素の先頭から一つ値をとって、あとはリストを入れ替えて再帰すれば、シンプルに書けます。

問題3

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

Haskellと言えばフィボナッチみたいな、遅延リストを利用した超有名なワンライナーがありますが、わかりづらいので、愚直な実装を書きました。

fib100 :: [Integer]
fib100 = take 100 $ go 0 1 where
  go a b = a : go b (a + b)

問題4

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

これは問題の要件がかなり不明なんですが、4要素程度の入力ならば、全通り試すコードで大丈夫です。

problem4 :: [Integer] -> Integer
problem4 xs = maximum $ do
  xs <- permutations xs
  return $ read $ concatMap show xs

リストの要素数に対して指数関数的な時間がかかるので、リストの要素数が10程度で限界が来ると思います。

たぶんこの問題は貪欲に左右を入れ替えて、大きくなれば入れ替えたほうが常によくなると思うので、そういう並び順にソートして連結するだけで大丈夫だと思います。

problem4_2 :: [Integer] -> Integer
problem4_2 xs =
  read $ concat $ sortBy (\a b -> compare (b ++ a) (a ++ b)) $ map show xs

問題5

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

9文字の数字の間に入れる8つの演算子を全通り試しても3^8=6561通りしかないので、しらみつぶしで十分なので、やるだけですね。Haskellだと比較的楽だと思います。

問題2で作った関数（ここだとinterleave）を用いて、数字と演算子を交互に並べるというのができるんですが、これはそういうことをするのを見越してのことなんでしょうか？

problem5 :: [String]
problem5 = do
  ops <- replicateM 8 "+- "
  let expr = filter (not . isSpace) $ interleave ['1'..'9'] ops
  guard $ calc ('+':expr) == 100
  return expr

calc :: String -> Int
calc "" = 0
calc (op:ss) =
  let (num, rest) = span isDigit ss
  in (if op == '+' then 1 else -1) * read num + calc rest