急勾配の判定

30分プログラム、その587。急勾配の判定をやってみる。

有限の長さの数列で，各要素の値が，その要素の後ろにある残りの列に含まれるすべての要素の和よりも大きい列を「急勾配の列」ということにします（空列の和は0とします）．

任意の長さ（ただし有限の長さの）数列を与えられたとき，それが「急勾配の列」であるかどうかを判定する述語関数を定義してください．

必須ではありませんが，効率についてコメントがあれば面白いかもしれませんね．

QuickCheckでリファクタリング - みずぴー日記でやってように、

1. 定義通りの(効率の悪い)関数を書く
2. 効率を意識した関数を書く
3. QuickCheckで、同じ挙動をするかを確認する

という流れでやってみた。QuickCheck便利だわ。

使い方

-- 効率が悪いやつ
*Main> isSuperInc [3,1]
True

-- 効率が良いやつ
*Main> isSuperInc2 [3,1]
True

-- 同じ挙動をするかチェック
*Main> quickCheck $ \xs -> isSuperInc xs == isSuperInc2 xs
OK, passed 100 tests.

ソースコード

import Test.QuickCheck

-- trival
isSuperInc :: [Int] -> Bool

isSuperInc [] = True
isSuperInc (x:xs) = isSuperInc xs && x > (sum xs)

-- reverse
isSuperInc2 :: [Int] -> Bool
isSuperInc2 xs =
    let ys   = reverse xs
        sums = scanl (+) 0 ys
    in
      and $ zipWith (>) ys sums

-- quick check
prop = quickCheck $ \xs -> isSuperInc xs == isSuperInc2 xs

参考

• 過去の30分プログラム
• http://ja.doukaku.org/248/