急勾配の判定 in Haskell DouKaku?

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

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

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

$ が多くてうっとうしいけど。

1
2
3

import List

steep xs = and $ zipWith (>) xs $ map sum $ tail $ tails xs

1	isSteelyList xs = and $ zipWith (>) xs $ tail $ scanl (-) (sum xs) xs

mapAccumの遅延評価が良くわかりませんが...

1
2
3

import Data.List (mapAccumR)

isSteep = and . snd . mapAccumR (\acc x -> (acc+x, x > acc)) 0

import Maybe

isKyukoubai xs = isJust $ foldr f (Just 0) xs  where
  f x b = do
    s <- b
    if (x > s) then Just (s+x) else Nothing
{-
> isKyukoubai [4,2,1]
True
> isKyukoubai [2,2,1]
False
> isKyukoubai [undefined,2,2,1]
False
-}

末尾再帰になってる？

isKyukoubai xs = f [] xs  where
  f ys (x:xs) = f (x:ys) xs
  f ys [] = g 0 ys
  g s (y:ys)
    | y > s     = g (s+y) ys
    | otherwise = False
  g _ [] = True

効率や末尾再帰や遅延評価や見易さやら考えてたら
#8896 の reverse版になりました。

1 2	isKyukoubai xs = and $ zipWith (>) ys $ scanl (+) 0 ys where ys = reverse xs

DouKaku?

急勾配の判定

Posted feedbacks - Haskell

Index

Feed

Other

Link

Pathtraq