FOP/ex12.1 - 大久保弘崇

12.1△

(自信なし)
型宣言なしで関数定義されていると仮定すると、evalの主型は関数定義のそれぞれの等式に対して次のように推論されると思われる。

eval Zero = 0	Term Int→Int
eval (IsZero e) = eval e==0	Term Bool→Bool

この両者から eval :: Term τ→τ とは推論できない。

12.2×

12.3

eq :: Type t -> t -> t -> Bool
eq (RInt) i j = i == j
eq (RChar) c d = c == d
eq (RList _) [] [] = True
eq (RList t) (x:xs) (y:ys) = eq t x y && eq (RList t) xs ys
eq (RList _) _ _ = False
eq (RPair ra rb) (a, b) (c, d) = eq ra a c && eq rb b d
 

cmp :: Type t -> t -> t -> Ordering
cmp (RInt) i j = compare i j
cmp (RChar) c d = compare c d
cmp (RList _) [] [] = EQ
cmp (RList _) (_:_) [] = GT
cmp (RList _) [] (_:_) = LT
cmp (RList t) (x:xs) (y:ys) = case cmp t x y of
  LT -> LT
  EQ -> cmp (RList t) xs ys
  GT -> GT
cmp (RPair ra rb) (a, b) (c, d) = case cmp ra a c of
  LT -> LT
  EQ -> cmp rb b d
  GT -> GT
 

12.4×

12.5△

compress

uncompressBase :: Int -> [Int] -> (Int,[Int])
uncompressBase w ks = (foldr (\ x s -> s * 2 + x) 0 (take w ks), (drop w ks))
uncompressInt = uncompressBase 32
uncompressChar ks = (chr n, ls) where (n, ls) = uncompressBase 7 ks
 
uncompress :: Type t -> [Int] -> t
uncompress t ks = fst (uncompress' t ks)
uncompress' :: Type t -> [Int] -> (t,[Int])
uncompress' RInt ks = uncompressInt ks
uncompress' RChar ks = uncompressChar ks
uncompress' (RList _) (0:ks) = ([], ks)
uncompress' (RList t) (1:ks) = (v:vs, ms) where
  (v ,ls) = uncompress' t ks
  (vs,ms) = uncompress' (RList t) ls
uncompress’ (RPair ra rb) ks = ((u,v), ms) where
  (u,ls) = uncompress' ra ks
  (v,ms) = uncompress' rb ls
 

parse

0と1の並びを解釈するuncompressと、アスキー文字の並びを解釈するparseには計算する内容に本質的な違いはない。
ただ面倒さがparseの方が圧倒的に大きい。なのでパス。

12.6

補助データ型を用いずに作ると、デコード側が

uncompressType' :: [Int] -> (Type t, [Int])
uncompressType' (0 : 0 : 0 : ks) = (RInt, ks)

のようになる。ここで RInt :: Type Int でありこれは型宣言の Type t より狭くなるので型エラーとなる。

data Rep where Rep :: Type t → Rep
 
compressRep :: Rep → [Int]
compressRep (Rep RInt) = [0,0,0]
compressRep (Rep RChar) = [0,0,1]
compressRep (Rep (RList ra)) = 0 : 1 : 0 : compressRep (Rep ra)
compressRep (Rep (RPair ra rb)) = 0 : 1 : 1 : compressRep (Rep ra) + + compressRep (Rep rb)
compressRep (Rep RDyn) = [1,0,0]
 
uncompressRep′:: [Int] → (Rep, [Int])
uncompressRep′(0 : 0 : 0 : ks) = (Rep RInt, ks)
uncompressRep′(0 : 0 : 1 : ks) = (Rep RChar, ks)
uncompressRep′(0 : 1 : 0 : ks) = case uncompressRep′ks of
  (Rep ra, ks′) → (Rep (RList ra), ks′)
uncompressRep′(0 : 1 : 1 : ks) = case uncompressRep′ks of
  (Rep ra, ks′) → case uncompressRep′ks′of
    (Rep rb, ks′′) → (Rep (RPair ra rb), ks′′)
uncompressRep′(1 : 0 : 0 : ks) = (Rep RDyn, ks)
 

コメント