練習問題3-9,10,11,12
Real World Haskell―実戦で学ぶ関数型言語プログラミングBryan O'Sullivan,John Goerzen,Don Stewart
オライリージャパン / ￥ 3,990 ()
在庫あり。
3-12はわからなかったので、酔いどれコードを参考にした。というかほとんど写経。
量子男のささいなログにも書いてあったけど3-11の使いどころがいまいちわからない。この場合もリスト全部じゃなくて最後のほうだけチェックすればいいような気がした。
-- 3-9,3-10,3-11
data Direction = CounterClockwise | Clockwise | Straight deriving (Show,Eq)
type Pos = (Float,Float)
calcpos :: Pos -> Pos -> Pos -> Direction
calcpos a b c | iprod > 0 = CounterClockwise
| iprod < 0 = Clockwise
| iprod == 0 = Straight
where iprod = ((fst a) - (fst b)) * ((snd c) - (snd b))
- ((snd a) - (snd b)) * ((fst c) - (fst b))
directions :: [Pos] -> [Direction]
directions [] = []
directions (x:[]) = []
directions (x:y:[]) = []
directions (x:y:z:zs) = calcpos x y z : directions (y:z:zs)
-- 3-12
sortCoordinate :: [Pos] -> [Pos]
sortCoordinate ps = sortBy cmp ps
where cmp a b | snd a < snd b = LT
| snd a > snd b = GT
| fst a < fst b = LT
| fst a > fst b = GT
| otherwise = EQ
sortAngle :: Pos -> [Pos] -> [Pos]
sortAngle p ps = sortBy cmp ps
where cmp a b = compare (cot b) (cot a)
where cot c = (fst c - fst p) / (snd c - snd p)
gsort :: [Pos] -> [Pos]
gsort ps = let csort = sortCoordinate ps
lower = head csort
in lower : sortAngle lower (tail csort)
isCounterClockwise :: [Direction] -> Bool
isCounterClockwise [] = False
isCounterClockwise (x:xs) | x == CounterClockwise = True
| otherwise = isCounterClockwise xs
scan :: [Pos] -> [Pos] -> [Pos]
scan [] (y1:y2:ys) = scan [y1,y2] ys
scan xs [] = xs
scan xs (y:ys) | isCounterClockwise (directions (xs++[y])) = scan (init xs) (y:ys)
| otherwise = scan (xs++[y]) ys
graham :: [Pos] -> [Pos]
graham xs = scan [] $ gsort xs
-- データ生成用
randX :: [Float]
randX = randomRs (-100,100) (mkStdGen 5)
randY :: [Float]
randY = randomRs (-100,100) (mkStdGen 3)
randPoss :: Int -> [(Float,Float)]
randPoss n = take n $ zip randX randY