実例によるPureScript 6 章

型クラスの章。型クラスとそのインスタンスの関係は、普通のオブジェクト志向言語のクラスとインスタンスが一個上にずれている感じ。

1. (簡単)前章の showShape関数を使って、 Shape型に対しての Showインスタンスを定義してみましょう。

これは book に答えがあるが。

instance shapeShow :: Show Shape where
  show shape = showShape shape

1. (簡単)次のnewtypeは複素数を表します。

newtype Complex = Complex
{ real :: Number
, imaginary :: Number
}
Complexについて、 Showと Eqのインスタンスを定義してください。

instance showComplex :: Show Complex where
  show (Complex c) = show c.real <> " + " <> show c.imaginary <> "i"

instance eqComplex :: Eq Complex where
  eq (Complex a) (Complex b) = a.real == b.real && a.imaginary == b.imaginary

1. `Eq a`と `Eq (Array a)`のインスタンスを再利用して、型 `NonEmpty a`に対する `Eq`インスタンスを書いてみましょう。

2. (やや難しい)Semigroupインスタンスを Arrayに再利用して NonEmpty aの Semigroupインスタンスを作成しましょう。

3. (やや難しい)NonEmptyの Functorインスタンスを書いてみましょう。

instance nonEmptyEq :: (Eq a, Eq (Array a)) => Eq (NonEmpty a) where 
  eq (NonEmpty x1 xs1) (NonEmpty x2 xs2) = eq x1 x2 && eq xs1 xs2

instance nonEmptySemigroup :: Semigroup (Array a) => Semigroup (NonEmpty a) where
  append (NonEmpty x1 xs1) (NonEmpty x2 xs2) = NonEmpty x1 (xs1 <> [x2] <> xs2)

instance nonEmptyFunctor :: Functor NonEmpty where
  map f (NonEmpty x xs) = NonEmpty (f x) (map f xs)

4. (やや難しい)Ordのインスタンスを持つ型 aがあれば、他の値より大きい新しい 無限の値を追加することができます。

data Extended a = Finite a | Infinite

`a`の `Ord`インスタンスを再利用して、 `Extended a`の `Ord`インスタンスを書いてみましょう。

Eq インスタンスも要るはず。

instance eqExtended :: (Eq a) => Eq (Extended a) where
  eq Infinite Infinite = true
  eq (Finite a) (Finite b) = eq a b
  eq _ _ = false

instance ordExtended :: (Ord a) => Ord (Extended a) where
  compare Infinite Infinite = EQ
  compare Infinite (Finite _) = GT
  compare (Finite _) Infinite = LT
  compare (Finite a) (Finite b) = compare a b

5. (難しい)NonEmptyの Foldableインスタンスを書いてみましょう。ヒント：配列の Foldableインスタンスを再利用してみましょう。

instance nonEmptyFoldable :: Foldable NonEmpty where
  foldr f init (NonEmpty x xs) = foldr f init ([x] <> xs)
  foldl f init (NonEmpty x xs) = foldl f init ([x] <> xs)
  foldMap f (NonEmpty x xs) = foldMap f ([x] <> xs)

6. (難しい)　順序付きコンテナを定義する(そして Foldableのインスタンスを持っている)ような型構築子 fが与えられたとき、追加の要素を先頭に含めるような新たなコンテナ型を作ることができます。

data OneMore f a = OneMore a (f a)

このコンテナ OneMore fもまた順序を持っています。ここで、新しい要素は任意の fの要素よりも前にきます。この OneMore fの Foldableインスタンスを書いてみましょう。

instance foldableOneMore :: Foldable f => Foldable (OneMore f) where

これは NonEmpty をより一般化したものということかな。

instance foldableOneMore :: Foldable f => Foldable (OneMore f) where
  foldr func init (OneMore x fx) = func x (foldr func init fx)
  foldl func init (OneMore x fx) = func (foldl func init fx) x
  foldMap func (OneMore x fx) = (func x) <> (foldMap func fx)

oneMore1 :: OneMore Array Int
oneMore1 = OneMore 1 [2, 3, 4, 5]

> foldl (-) 0 oneMore1
-15

> foldr (-) 0 oneMore1
3

> foldMap show oneMore1                                                
"12345"

1. (やや難しい) 整数の空でない配列の最大値を求める部分関数を定義します。あなたの関数の型は Partial => Array Int - > Intでなければなりません。 unsafePartialを使ってPSCiであなたの関数をテストしてください。 ヒント：Data.Foldableの maximum関数を使います。

partialMax :: Partial => Array Int -> Int
partialMax xs =
  case maximum xs of
    Just a -> a

使ってみる。

> import Partial.Unsafe (unsafePartial)
> unsafePartial partialMax [1, 2, 3]   
3

2. (やや難しい) 次の Actionクラスは、ある型の動作(action)を定義する、多変数型クラスです。

class Monoid m <= Action m a where
act :: m -> a -> a
actはモノイドがどうやって他の型の値を変更するのに使われるのかを説明する関数です。この動作が　モノイドの連結演算子に従っていると期待しましょう。

act mempty a = a
act (m1 <> m2) a = act m1 (act m2 a)
この動作は Monoidクラスによって定義された操作を順守します。

たとえば、乗算を持つ自然数のモノイドを形成します。

newtype Multiply = Multiply Int

instance semigroupMultiply :: Semigroup Multiply where
append (Multiply n) (Multiply m) = Multiply (n * m)

instance monoidMultiply :: Monoid Multiply where
mempty = Multiply 1
このモノイドは、文字列の何度かの繰り返しとして文字列に対して動作します。このアクションを実装するインスタンスを作成します。

instance repeatAction :: Action Multiply String
このインスタンスが上記の法則を満たしているか確かめましょう。

 0 以下の繰り返しは "" を返すものとする。

instance repeatAction :: Action Multiply String where
  act (Multiply n) s | n < 1 = ""
                     | otherwise = applyN ((<>) s) (n - 1) s

> act (Multiply 3) "hoge" 
"hogehogehoge"

> act (Multiply 0) "hoge"
""

> act ((Multiply 2) <> (Multiply 3)) "hoge"
"hogehogehogehogehogehoge"

> act (Multiply 2) (act (Multiply 3) "hoge")
"hogehogehogehogehogehoge"

> act (Multiply 1) "hoge"                   
"hoge"

3. (やや難しい) インスタンス Action m a => Action m（Array a）を書いてみましょう。ここで、 配列上の動作は要素の順序で実行されるように定義されるものとします。

instance arrayAction :: Action m a => Action m (Array a) where
  act m = map (act m)

> act (Multiply 3) ["hoge", "fuga", "foo"]
["hogehogehoge","fugafugafuga","foofoofoo"]

4. (難しい) 以下のnewtypeが与えられたとき、 Action m (Self m)のインスタンスを書いてみましょう。ここで、モノイド mは連結によって自身に作用するものとします。

newtype Self m = Self m

instance selfAction :: Monoid m => Action m (Self m) where
  act a (Self b) = Self (b <> a)

instance showSelf :: Show a => Show (Self a) where
  show (Self a) = "Self: " <> show a

> act (Multiply 3) (Self (Multiply 2))
Self: Multiply 6

5.（難しい）多変数型のクラス Actionの引数は、いくつかの関数従属性によって関連づけられるべきですか。それはなぜでしょうか。

多分関連づける必要はない、と思う。Stream の例のように stream と element が配列と要素の関係であるという制約はないはずなので。

2. (やや難しい) 同値性の近似として hashEqual関数のハッシュ同値性を使い、配列が重複する要素を持っているかどうかを調べる関数を書いてください。ハッシュ値が一致したペアが見つかった場合は、 ==を使って値の同値性を厳密に検証することを忘れないようにしてください。 ヒント：Data.Arrayの nubBy関数を使用してみてください。

hasDuplicate :: forall a. Hashable a => Array a -> Boolean
hasDuplicate xs = length xs > length removed
  where
    removed = nubByEq (\a b -> (hashEqual a b) && (a == b)) xs

> hasDuplicate [1, 2, 3, 2]
true

> hasDuplicate [1, 2, 3, 65536]
false

3. (やや難しい) 型クラスの法則を満たす、次のnewtypeの Hashableインスタンスを書いてください。

newtype Hour = Hour Int

instance eqHour :: Eq Hour where
eq (Hour n) (Hour m) = mod n 12 == mod m 12
newtypeの Hourとその Eqインスタンスは、12進数である型を表します。したがって、1と13は等しいと見なされます。そのインスタンスが型クラスの法則を満たしていることを証明してください。

instance hashHour :: Hashable Hour where
  hash (Hour n) = hash (mod n 12)

> import Data.Hashable (class Hashable, hashEqual, hash)
> hashEqual (Hour 1) (Hour 1)                           
true

> hashEqual (Hour 2) (Hour 14)
true

> hashEqual (Hour 2) (Hour 1) 
false

4. (難しい)Maybe、 Either、 Tupleの Hashableインスタンスが型クラスの法則を満たしていることを証明してください。

以下のような実装になっている。各パターンで a, b が Hashable なので、a, b が同じ値なら hash 関数が返す値も同じになっている、と言える、ハズ。

instance hashMaybe :: Hashable a => Hashable (Maybe a) where
  hash Nothing = hashCode 0
  hash (Just a) = hashCode 1 `combineHashes` hash a

instance hashTuple :: (Hashable a, Hashable b) => Hashable (Tuple a b) where
  hash (Tuple a b) = hash a `combineHashes` hash b

instance hashEither :: (Hashable a, Hashable b) => Hashable (Either a b) where
  hash (Left a) = hashCode 0 `combineHashes` hash a
  hash (Right b) = hashCode 1 `combineHashes` hash b