Edited at

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

More than 3 years have passed since last update.

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

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で、これで先頭の要素を捨てています。ループの中身は、そのループ変数の先頭を、変数に足し合わせています。headtailnullはすべて定数時間で実行できるので、これで実行時間の問題は解決しました。

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