Semigroup - haskell-shoen

Semigroup

結合則を満たすような演算を持つ型のクラス。

code:haskell

class Semigroup a where

(<>) :: a -> a -> a -- infixr 6

-- デフォルト実装あり

sconcat :: NonEmpty a -> a

stimes :: Integral b => b > a -> a

stimes n xはxをn個連結する関数で、愚直にx <> x <> x ... とするのではなく、let x2 = x <> x in let x4 = x2 <> x2 in x4 <> x2 <> xのように賢く組み合わせてくれる。これを応用すればフィボナッチ数列のn番目の値をΟ(log n)で計算することができる。

code:haskell

import Data.Semigroup

data Mat22 = Mat22 !Int !Int !Int !Int

instance Semigroup Mat22 where

Mat22 a b c d <> Mat22 p q r s = Mat22

(a * p + b * r)

(a * q + b * s)

(c * p + d * r)

(c * q + d * s)

fib :: Int -> Int

fib n = let Mat22 _ x _ _ = stimes n (Mat22 0 1 1 1) in x