リストの並び in Haskell DouKaku?

数値のリストがあります。リストのサイズは N です。
ls[0]がリストの先頭要素、ls[N-1]が最後の要素です。

問題: 入力として与えられたリストが次の条件を満たすかどうかを求めてください。

for (int i = 0; i < N-1; i++) {
  ls[i] != ls[i+1] である
  ls[i] < ls[i+1] なら、ls[i] < ls[k] である(for all k = i+1 to N-1)
  ls[i] > ls[i+1] なら、ls[i] > ls[k] である(for all k = i+1 to N-1)
}

N の範囲は 3 <= N <= 50000 です。実行例を示します。

> check([1, 5, 4, 2])
True
> check([1, 2, 3])
True
> check([825, 102, 811, 140, 812, 125, 263])
False
> check([824, 102, 811, 140, 810, 155, 263])
True
> check([5, 4, 3, 2, 1])
True
> check([4, 2, 5, 3, 1])
False

import Data.List

check :: [Int] -> Bool
check xs = all foo $ tails xs
 where
  foo []     = True
  foo (x:xs) = all (EQ /=) &&& ((1 >=) . length . group) $ map (compare x) xs

(&&&) :: (a -> Bool) -> (a -> Bool) -> (a -> Bool)
(p &&& q) x = if p x then q x else False

Haskell の方がきれいに書けますね。

import Data.List

check (x:xs) = (all (< x) xs || all (> x) xs) && check xs
check []     = True

import Maybe

check [] = True
check xs = isJust $ check' $ reverse xs  where
  check' (x:xs) = foldl (\b x -> b >>= f x) (Just(x,x)) xs
  f x (l,h) | x < l = Just (x,h)
            | x > h = Just (l,x)
            | otherwise = Nothing

-∞ と ∞ と foldr を使って書き直し。

import Maybe

data Z = NegInf | Finite Integer | PosInf deriving (Eq,Ord)
 
check xs = isJust $ foldr ((=<<).f.Finite) (Just(PosInf,NegInf)) xs  where 
  f x (l,h) | l <= x && x <= h = Nothing
            | otherwise        = Just (min x l, max x h)

DouKaku?

[topic] リストの並び

Posted feedbacks - Haskell

Index

Feed

Other

Link

Pathtraq