LoginSignup
65

More than 5 years have passed since last update.

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

Last updated at Posted at 2015-06-01

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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
65