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


http://www.softantenna.com/wp/software/5-programming-problems/

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

## 問題1

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

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

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

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

```hs
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言語で配列の中身を合計するコードは次のようなものになると思います。

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

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

```hs
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`という関数で変換することができます。

```hs
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の実装から離れて、ループ変数を配列自体にしてみましょうか。

```hs
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のようなものなので、次のように書くこともできます。

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

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

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

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

```hs
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コミュニティーではよく言われていますので、こういうのもあるいはぴったりはまるところが、別の問題ではあるかもしれません。

[このあたり](http://hackage.haskell.org/package/monad-loops-0.4.2.1/docs/Control-Monad-Loops.html)に、いろんなループの実装例があるので、見てみると面白いかもしれません。

# 問題2

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

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

```hs
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と言えばフィボナッチみたいな、[遅延リストを利用した超有名なワンライナー](https://wiki.haskell.org/The_Fibonacci_sequence#Canonical_zipWith_implementation)がありますが、わかりづらいので、愚直な実装を書きました。

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

# 問題4

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

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

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

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

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

```hs
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`）を用いて、数字と演算子を交互に並べるというのができるんですが、これはそういうことをするのを見越してのことなんでしょうか？

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