Subscribed unsubscribe Subscribe Subscribe

一辺の長さがsの正n角形

Haskell

The Haskell School of Expressionの問題.一辺の長さがsである正n角形の各頂点を求める.書きやすさのため複素平面で考える.

正n角形の内角は\pi(1-\frac{2}{n})なので,各頂点で\theta=\pi-\pi(1-\frac{2}{n})だけ回転させていけばよい.

各頂点v_iv_{i-1}rotate(i\theta, v_1)を足したものになる.ただし,i\in[1..n-1]rotate(r, v)は点vrだけ反時計回りに回転する関数とする.

こういう前の値を利用して次の値を計算するものはストリームで短く書ける.

type Vertex = Complex Float
type Side   = Float

regularPolygon :: Int -> Side -> [Vertex]
regularPolygon n s = take n vertices
    where theta    = pi-interiorAngle n
          vertices = 0:+0:zipWith (+) vertices addends
          addends  = s:+0:map (rotate theta) addends

interiorAngle :: Int -> Float
interiorAngle n = pi*(1-2/fromIntegral n)

rotate :: Radius -> Vertex -> Vertex
rotate r = (*(cos r:+sin r))

verticesが各頂点,addendsは次の頂点を求めるときに用いるrotate(i\theta, v_1)の点を表す.もうちょっとまともな名前が欲しい.verticesとaddendsがトップレベルではなくてwhere節の中に入っているのには理由がある.トップに持ち上げるとvertices theta s,addends theta sというように関数になってしまうためメモ化ができなくなってしまう.where節の中に入れればただのリストになりO(n)のステップ数で計算できる.

main :: IO ()
main = do
  (n:s:_) <- getArgs
  mapM_ print $ regularPolygon (read n) (read s)

として実行すると

$ ./Polygon 3 1
0.0 :+ 0.0
1.0 :+ 0.0
0.49999994 :+ 0.8660254
$ ./Polygon 5 1
0.0 :+ 0.0
1.0 :+ 0.0
1.3090171 :+ 0.9510565
0.5000002 :+ 1.5388418
(-0.30901688) :+ 0.95105684

たぶんうまくいってる.